在go语言中数据结构之队列数组实现示例代码

Go  /  管理员 发布于 2年前   299

数据结构-队列描述：遵循先进先出原则的线性表，其插入与删除操作分别在表的两端进行，

进行插入操作的是队尾 (back/rear)，删除操作的是队首 (front)。

队列数组实现优化思路及代码示例：

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

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)。

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

那么就继续优化

back = a[front+size]%arryLen即 location(i)=location(front+i)%arrLen

很明显，如果这样的话，我们就可以将数组看出一个环了。

进站出站都是围着这个环来做，这也就不是普通的队列了，是循环队列了。

这里我们对 front 的定义做了点改动，不再是删除的节点，而是该节点的前一个节点

这样的话，我们也可以通过 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
}