# 数据结构 队列

## 定义

``````
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`

`back = a[front+size]`

`location(i)=location(front+i)`

`back = a[front+size]%arryLen`

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

``````
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

}
``````

### 链表实现

``````
queue= &node{

Val:val,

}
``````

``````
back.Next :=  &node{

Val:val,

Next:nil,

}

back = back.Next
``````

``````

// 指向链首

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

``````
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

}
``````

## 总结

github

y1nhui

3周前 评论
yinhui （楼主） 3周前
yinhui （楼主） 3周前

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

3周前 评论
yinhui （楼主） 3周前

1周前 评论
yinhui （楼主） 1周前
yinhui （楼主） 1周前

6

2

3

2