转载

队列

如何理解队列

队列与栈做比较，就是队列是先进先出，队列本身就像一个管子一样。

队列

先进先出就是一个典型的队列。队列的应用十分广泛，特别是具有额外特性的队列，比如循环队列，阻塞队列，并发队列等，这些都是偏底层系统，框架，中间件的开发，都是有队列的身影，比如高性能的队列Disruptor、Linux环形缓存等。Java concurrent 并发包利用ArrayBlockingQueue 来实现公平锁等

如何实现一个队列

队列最基本的操作是 入队enqueue（） ，放一个数据到对尾； 出队dequeue（） ，从队头取出一个元素。用数组实现的队列就是 顺序队列 ，用链表实现的队列就是 链式队列 。

顺序队列

一个最基础的顺序队列实现（使用golang）

type Queue struct {
    Items   []string  // 数组:items  数组大小:n
    Cnt     int
    Head    int       // Head 队头下标  Tail 队尾下标
    Tail    int
}

// 初始化一个大小为 capacity 的数组
func (q *Queue) Init(capacity int) {
    q.Items = make([]string,capacity)
    q.Cnt = capacity
    q.Head,q.Tail = 0,0
}

// 入队
func (q *Queue) Enqueue(item string) bool {
    if q.Tail == q.Cnt {  // Tail 到尾部了
        if q.Head == 0 {  // 真的没空间了
            return false
        }else {           // 数据搬移
            for i := q.Head;i < q.Tail; i++ {
                q.Items[i - q.Head] = q.Items[i]
            }
            q.Tail = q.Tail - q.Head
            q.Head = 0
        }

    }
    q.Items[q.Tail] = item
    q.Tail++
    return true
}

// 出队
func (q *Queue) Dequeue() (string,bool) {
    if q.Head == q.Tail {
        return "",false
    }
    ret := q.Items[q.Head]
    q.Items[q.Head] = ""
    q.Head++
    return ret,true
}

这种利用数组的队列是最基础的队列。

顺序队列的分支（循环队列）

在上面的例子中，在tail=n的时候会进行一次数组搬移的操作，这样的入队操作其实在性能上是有一定的影响的，如果使用了循环队列，那么就不会存在数据搬移动的操作了。

循环队列

也就是说当tail到数组的尾部时候，会将新的元素重新放进数组头（前提是队列的head指针已经不再指向数组头了）

其实这样的代码看起来十分的简单，但是想要写出没有bug的代码，需要注意两点的判断 队满的状态 （tail == cnt）， 队空的状态 （head == tail）。

如上图的队满情况下，tail=3 , head =0 . 而 cnt = 4 。总结规律就是(3+1)%4 =0, 也就是 (tail + 1)%cnt = head 就代表队满了。

上图的Full 明明在下标为3 的位置没有存放数据，这是因为循环队列就是会浪费一个数组的存储空间。仔细想一想就明白为什么了，注意还要判断队空呢

下面就是一个循环队列的 golang 代码

// 循环队列
type CircularQueue struct {
    Items []string
    Cnt   int
    Head  int
    Tail  int
}

func (cq *CircularQueue) Init(capacity int) {
    cq.Items = make([]string,capacity)
    cq.Cnt = capacity
    cq.Head,cq.Tail = 0,0
}

// 入队操作
func (cq *CircularQueue) EnQueue(item string) bool {
    // 判断是否队满
    if (cq.Tail + 1) % cq.Cnt == cq.Head {
        return false
    }
    cq.Items[cq.Tail] = item
    cq.Tail = (cq.Tail + 1) % cq.Cnt
    return true
}

// 出队操作
func (cq *CircularQueue) DeQueue() (string,bool) {
    // 判断是否队空
    if cq.Head == cq.Tail {
        return "", false
    }
    ret := cq.Items[cq.Head]
    cq.Head = (cq.Head + 1) % cq.Cnt
    return ret,true
}

实际的运用

在实际的运用中，队列的出境率身份的高，因为队列就是一个典型的 生产者 和 消费者 模型，但是在高并发的场景下，在 并发队列 中，一定要在 EnQueue 和 DeQueue 上加锁，实际上基于数组的循环队列，利用了CAS原子操作，可以实现非常高效的并发队列，循环队列比普通的并发队列和链式队列应用的更多。循环队列也更为广泛。

原文 https://studygolang.com/articles/23070

正文到此结束