队列（queue）原理

客官°小女子只卖身不卖艺 2022-07-15 12:49 44阅读 0赞

像栈一样，队列（queue）也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端。就像排队一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人。如图1，描述了一个队列模型。

队列（Queue）与栈一样，是一种线性存储结构，它具有如下特点：

1.  队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构。
2.  在队尾添加元素，在队头删除元素。

[回到顶部][Link 1]

# 1.2 队列的相关概念 #

队列的相关概念：

1.  队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头。
2.  入队：队列的插入操作。
3.  出队：队列的删除操作。

例如我们有一个存储整型元素的队列，我们依次入队：\{1，2，3\}  
![610439-20160130151820974-712348880.png][]

添加元素时，元素只能从队尾一端进入队列，也即是2只能跟在1后面，3只能跟在2后面。  
如果队列中的元素要出队：  
![610439-20160130151830318-592472607.png][]

元素只能从队首出队列，出队列的顺序为：1、2、3，与入队时的顺序一致，这就是所谓的“先进先出”。

## 1.3 队列的操作 ##

队列通常提供的操作：

1.  入队： 通常命名为push()
2.  出队： 通常命名为pop()
3.  求队列中元素个数
4.  判断队列是否为空
5.  获取队首元素

## 1.4 队列的存储结构 ##

队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构。  
本文中，我们以数组、链表为底层数据结构构建队列。

# 2.基于数组的循环队列实现 #

以数组作为底层数据结构时，一般讲队列实现为**循环队列**。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作：  
![610439-20160130152004193-1945216114.png][]

可能有人说，把队首标志往后移动不就不用移动元素了吗？的确，但那样会造成数组空间的“流失”。  
我们希望队列的插入与删除操作都是O(1)的时间复杂度，同时不会造成数组空间的浪费，我们应该使用循环队列。  
所谓的循环队列，可以把数组看出一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。  
![610439-20160130152048146-364086587.png][]

[Link 1]: http://www.cnblogs.com/QG-whz/p/5171123.html#_labelTop
[610439-20160130151820974-712348880.png]: /images/20220715/a8da216d31a245e1b339a758a5b7ad9e.png
[610439-20160130151830318-592472607.png]: /images/20220715/911c640373f54625aa7ff63bce25e1fc.png
[610439-20160130152004193-1945216114.png]: /images/20220715/731fc10ba99a4949ac3c6e0b93481393.png
[610439-20160130152048146-364086587.png]: /images/20220715/10518fa0cc4c4739bef291c098d190d8.png