队列

如何理解队列

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

队列

队列

先进先出就是一个典型的队列。队列的应用十分广泛,特别是具有额外特性的队列,比如循环队列,阻塞队列,并发队列等,这些都是偏底层系统,框架,中间件的开发,都是有队列的身影,比如高性能的队列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

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 队列

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址