数据结构-队列

数据结构 队列

定义

队列:遵循先进先出原则的线性表。其插入与删除操作分别在表的两端进行。进行插入操作的是队尾(back/rear),删除操作的是队首(front)

常见方法:


type  Queue  interface {

 Empty() bool

 Size() int

 // 返回队首值

 Front() (interface{}, bool)

 // 返回队尾值

 Back() (interface{}, bool)

 // 返回并删除队首元素

 Pop() (interface{}, bool)

 // 将元素插入队尾

 Push(interface{}) bool

}

实现

基于定义,编写数组与链表实现的队列

数组实现

在编写数组实现之前,我们首先需要思考一个问题。

front、back、size的关系应该是什么。

基于定义,首先想到

front = a[0],back=a[size-1]

也就是

location(i)=i

如果是这样的话,我们每次进行插入操作,只需要直接将a[size]写入值即可,也就是一个 O(1) 操作

但是删除的话,我们就需要将全部元素向前移动一位,这样的话就是O(n)

那如果更改一下呢

back = a[front+size]

location(i)=location(front+i)

用图像表示的话如下:

xvqo7t.png

手绘,字丑,意会即可

如此操作的话,无论是pop还是push,都只是移动指针而不是元素,也就都是O(1),代价就是这个队列的空间会不断被浪费

那么就继续优化

back = a[front+size]%arryLen

location(i)=location(front+i)%arrLen

很明显,如果这样的话,我们就可以将数组看出一个环了。进站出站都是围着这个环来做,这也就不是普通的队列了,是循环队列了

可见图(这里我们对front的定义做了点改动,不再是删除的节点,而是该节点的前一个节点)

xvqI0I.png

这样的话,我们也可以通过 front = back 来判断队列为空

不过有个问题,就是大家想一下就会发现,如果我们给队列完全填满了,他也会是front = back

这是不行的,所以我们需要在加一条限制,队列的最大容量是 arryLen - 1 每次push前做一次检测,如果发现当前容量已经是最大容量了,需要进行一次扩容(arryLen = arryLen*2) 才可以进行push

明确了这些后,就可以开始编码了。


type  ArrayQueue  struct {

QueueFront int

    QueueBack  int

    Array      []interface{}

    QueueSize  int

}

func  New() *ArrayQueue {

 array := make([]interface{}, 4)

 return &ArrayQueue{

QueueFront: 0,

        QueueBack:  0,

        Array:      array,

        QueueSize:  0,

    }

}

func (q *ArrayQueue) Empty() bool {

 // return q.queueFront == q.queueBack

 return q.QueueSize == 0

}

func (q *ArrayQueue) Size() int {

 return q.QueueSize

}

func (q *ArrayQueue) Front() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 return q.Array[q.QueueFront+1], true

}

func (q *ArrayQueue) Back() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 return q.Array[q.QueueBack], true

}

func (q *ArrayQueue) Pop() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 front := (q.QueueFront + 1) % len(q.Array)

 val := q.Array[front]

q.Array[front] = nil

 q.QueueFront = front

    q.QueueSize--

 return val, true

}

func (q *ArrayQueue) Push(val interface{}) bool {

 if q.Size() == len(q.Array)-1 {

 q.Array = append(q.Array, make([]interface{}, len(q.Array))...)

    }

 back := (q.QueueBack + 1) % len(q.Array)

    q.Array[back] = val

 q.QueueBack = back

    q.QueueSize++

 return  true

}

链表实现

基于单链表实现同样要区分一下哪里是队列头,哪里是队列尾

首先我们需要两个指针,front与back 分别指向头与尾

如果是插入操作的话,无论哪一端是队尾都是很简单的

如果头节点是队尾:


queue= &node{

    Val:val,

    Next:head,

}

如果链表结尾是队尾:


back.Next :=  &node{

Val:val,

Next:nil,

}

back = back.Next

可见他们都是O(1)操作,但是删除操作就不一样了。

假设是头节点为队尾,那么删除操作需要先遍历到队尾前一个节点,随后断开链。

而链尾是队尾的情况只需要让 front = front.Next 就可以轻松断开

所以我们定义这个链表实现的队列,头节点处为队首,尾节点处为队尾


type  LinkedQueue  struct {

 // 指向链首

    QueueFront *chainNode

    QueueBack  *chainNode

    QueueSize  int

}

type  chainNode  struct {

    Val  interface{}

    Next *chainNode

}

func (q *LinkedQueue) Empty() bool {

 /*

        if q.QueueBack == q.QueueBack && q.QueueFront == nil {

            return true

        }

        return false

    */

 return q.QueueSize == 0

}

func (q *LinkedQueue) Size() int {

 return q.QueueSize

}

func (q *LinkedQueue) Front() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 return q.QueueFront.Val, true

}

func (q *LinkedQueue) Back() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 return q.QueueBack.Val, true

}

func (q *LinkedQueue) Pop() (interface{}, bool) {

 if q.Empty() {

 return  nil, false

    }

 val := q.QueueFront.Val

 q.QueueFront = q.QueueFront.Next

    q.QueueSize--

 return val, true

}

func (q *LinkedQueue) Push(val interface{}) bool {

 node := &chainNode{

        Val: val,

    }

 if q.Empty() {

 q.QueueFront = node

} else {

 q.QueueBack.Next = node

    }

 q.QueueBack = node

    q.QueueSize++

 return  true

}

应用

应用方面仍然使用leetcode题目作为演示

字符串中的第一个唯一字符

leetcode

送一个长度为n的字符串(只有小写字母),要求返回第一个无重复字符串的索引。

这里解法是先写一个长度为26的数组。从a[0]到a[25]分别代表a-z

将它们的值置为n,代表还未检索到。

创建一个队列,之后开始检索字符串。每检索到一个字符串便将对应的a[x]的值置为该字符串的索引,并且将索引与字节的结构体送入队列。

如果发现已经有索引了,就开始清空队列,一直清到队首的结构体没有被检索。

一直到将字符串检索完,如果这是队列非空,则队首的值是唯一的,如果为空则说明无唯一字符,返回-1

代码实现:


type  pair  struct {

    ch  byte

pos int

}

func  firstUniqChar(s string) int {

 n := len(s)

 alpbabet := make([]int, 26)

 for  i, _ := range alpbabet {

        alpbabet[i] = n

    }

 q := []*pair{}

 for  i := range s {

 b := s[i]

 index := b - 'a'

 if alpbabet[index] == n {

 q = append(q, &pair{

                ch:  b,

                pos: i,

            })

            alpbabet[index] = i

} else {

alpbabet[index] = n + 1

 for  len(q) != 0 {

 index := q[0].ch - 'a'

 if alpbabet[index] == n+1 {

 q = q[1:]

} else {

 break

                }

            }

        }

    }

 if  len(q) > 0 {

 return q[0].pos

    }

 return -1

}

总结

本文完成了对队列的定义与代码实现,并且就队列完成了一道leetcode题目

其实最开始想引用参考书籍里的例子,但多为应用题或之前章节题目的部分的改进,叙述过多,所以并未使用。

这次学习与博文撰写期间,周末公司外出团建,耽搁时间略多,虽然回来后还是有些晕车想吐,所幸还是写出了这篇文章,没有在计划开启的第二个星期就失败

代码单元测试可见github
github

本作品采用《CC 协议》,转载必须注明作者和本文链接
y1nhui
讨论数量: 8

图裂了

1年前 评论
yinhui (楼主) 1年前
yinhui (楼主) 1年前

back = a[front+size] 看不明白 front 不是返回队首的值吗

1年前 评论
yinhui (楼主) 1年前

file

这里 back = a [front+size]%arryLen 没有看明白,能具体举例说明一下吗

1年前 评论
yinhui (楼主) 1年前
yinhui (楼主) 1年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!