队列存储性能和查询复杂度（一文了解队列queue的实现原理）

队列存储性能和查询复杂度（一文了解队列queue的实现原理）队列有单向队列(queue)和双向队列(deque)之分，本文重点讲述单向队列。队列 Insert(Q n 1 x) Delete(Q 1) //一个口插入，另一个口删除举例：线性表 Insert(L i x) 1≤i≤n 1 Delete(L i) 1≤i≤n //任意位置插入和删除栈 Insert(S n 1 x) Delete(S n) //同一个口插入和删除

大家在学习编程时或程序开发中，经常提到数据结构中的“队列”和“栈”。那么他们分别具有什么结构特点？底层实现原理是什么？他们在STL中是如何实现的呢？都有哪些应用场景呢？

书接上文<数据结构的栈(stack)是如何实现的？>，本文讲解数据结构中的队列(queue)。

1.引言

栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。

通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

举例：

线性表 Insert(L i x) 1≤i≤n 1 Delete(L i) 1≤i≤n //任意位置插入和删除

栈 Insert(S n 1 x) Delete(S n) //同一个口插入和删除

队列 Insert(Q n 1 x) Delete(Q 1) //一个口插入，另一个口删除

2.队列的定义和特点

队列有单向队列(queue)和双向队列(deque)之分，本文重点讲述单向队列。

2.1.单向队列(queue，本文简称队列)：

是一种先进先出(First In First Out FIFO)的数据结构。它有两个出口，形式如下图所示。

图片来自<STL源码剖析>

queue允许新增元素、移除元素、从最底端加人元素、从最顶端取出元素。但除了最底端可以加入、最顶端可以取出外，没有任何其它方法可以存取queue的其它元素。换言之，queue不允许有遍历行为。

将元素推入queue的操作称为push 将元素推出queue的操作称为pop。

定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表

队尾(rear)——允许插入的一端

队头(front)——允许删除的一端

特点：先进先出(FIFO)

单向队列示意图：

2.2.双向队列(deque)：

deque是一种双向开口的连续线性空间(STL中vector也是连续线性空间，但是vector是单向开口，即主要在后面进行插入)。所谓双向开口，意思是可以在头尾两端分别做元素的插人和删除操作，如下图所示。

图片来自<STL源码剖析>

vector当然也可以在头尾两端进行操作（从技术观点)，但是其头部操作效率奇差，无法被接受。

STL的deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量(capacity)观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque是不会发生的。也因此，deque没有必要提供所谓的空间保留(reserve)功能。

也因此，STL的deque提供的迭代器内部实现特别复杂。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL sort算法），再复制回deque。

双向队列示意图：

STL的deque内部空间结构示意图：

图片来自<STL源码剖析>

图片来自<STL源码剖析>

3.queue的实现原理

队列分为“链队列”和“顺序结构队列”两类。

3.1.链队列

利用单向链表存储数据元素、也可以使用STL的list进行实现。

链队列结构定义：

//结点类型

typedef struct QNode

{

QElemType data;

struct QNode *next;

} QNode *QueuePtr;

// 链队列类型

typedef struct {

QueuePtr front; // 队头指针

QueuePtr rear; // 队尾指针

} LinkQueue;

示意图：

3.2.顺序结构队列

可以用普通的一维数组实现，也可以使用STL的deque进行实现。

下面咱们先以一维数组为底层结构的方式进行讲解。

示意图：

定义一个一维数组sq用于存储数据，定义front和rear两个指针用于控制入队和出队操作。

以一维数组为底层结构的队列处理方式

一维数组机构存在的问题：

设数组大小为M，则：

当front=0 rear=M时，再有元素入队发生溢出——真溢出

当front≠0 rear=M时，再有元素入队发生溢出——假溢出

解决方案:

1. 队首固定，每次出队剩余元素向下移动——浪费时间，效率低
2. 发生假溢出时再移动
3. 循环队列

• 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear==M 则令rear=0;
• 实现：利用“取模”运算
• 入队： sq[rear]=x; rear=(rear 1)%M;
• 出队： x=sq[front]; front=(front 1)%M;
• 队满、队空的判定条件

循环队列示意图：

循环队列运行效果示例：

全出队后队空状态，入队后队满状态

循环队列发现问题：

当前无法区分队列是满还是空！

• 队空的判断条件：front==rear
• 队满的判断条件：front==rear

解决对策：

1.另外设一个标志以区别队空、队满

2.少用一个元素空间：

队空：front == rear

队满：(rear 1)% M == front

红框表示新输入的数据，此时为队满状态

4.STL中的queue实现

对于queue，在STL中是如何实现的呢？又有哪些特点呢？

①SGI STL以deque作为缺省情况下的queue底部结构。(对应前面提到的“顺序结构队列”)

以某种既有容器为底部结构，将其接口改变，使其符合“先进先出”的特性，形成一个queue是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其底端的出口和前端的入口，便轻而易举地形成了一个queue。因此，SGI STL便以deque作为缺省情况下的queue底部结构，queue的实现因而非常简单，源代码十分简短。

template <class T class Sequence = deque<T> >

class queue {

friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x const queue& y);

friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x const queue& y);

public:

typedef typename Sequence::value_type value_type;

typedef typename Sequence::size_type size_type;

typedef typename Sequence::reference reference;

typedef typename Sequence::const_reference const_reference;

protected:

Sequence c;// 底层容器

public:

// 以下完全利用 Sequence c 的操作，完成 queue 的操作。

bool empty() const { return c.empty(); }

size_type size() const { return c.size(); }

reference front() { return c.front(); }

const_reference front() const { return c.front(); }

reference back() { return c.back(); }

const_reference back() const { return c.back(); }

// deque 是两头可进出，queue 是末端进，前端出（所以先进者先出）。

void push(const value_type& x) { c.push_back(x); }

void pop() { c.pop_front(); }

};

template <class T class Sequence>

bool operator==(const queue<T Sequence>& x const queue<T Sequence>& y) {

return x.c == y.c;

}

template <class T class Sequence>

bool operator<(const queue<T Sequence>& x const queue<T Sequence>& y) {

return x.c < y.c;

}

②queue没有提供迭代器

queue所有元素的进出都必须符合“先进先出”的条件，只有queue顶端的元素，才有机会被外界取用。queue不提供走访功能，也不提供迭代器。

③可以使用list作为queue的底层容器。(对应前面提到的“链式结构队列”)

除了deque之外，Iist也是双向开口的数据结构。上述queue源代码中使用的底层容器的函数list都具备。因此，若以list为底部结构并半封闭其头端开口，一样能够轻易形成一个queue。

测试代码：

参考文章最后的附录。

测试程序运行效果：

分别使用STL的deque、list作为stack的底层容器，进行同样数据的入栈和出栈。

注意：STL的vector不能作为STL stack的底层容器，因为queue的pop()函数最终使用的"pop_front"不是 "std::vector" 的成员。

附录：

测试代码源码。

#include <iostream>

#include <queue>

#include <list>

#include <vector>

#include <algorithm>

using namespace std;

template <class T class Sequence = deque<T> >

void queue_fun_test(queue<T Sequence>& list_queue)

{

cout << " " << __FUNCTION__ << endl;

//入队列

list_queue.push(1);

list_queue.push(2);

list_queue.push(3);

list_queue.push(4);

list_queue.push(5);

list_queue.push(6);

list_queue.push(7);

if (true != list_queue.empty())

{

cout << " 队列内元素个数:" << list_queue.size() << endl;

cout << " 当前队列头" << list_queue.front() << endl;

}

cout << endl << " 元素依次出队列:" << endl;

// 元素依次出队列

while (true != list_queue.empty())

{

// 打印队列顶元素

cout << " " << list_queue.front() << "出队列!" << endl;

// 出队列

list_queue.pop();

}

}

//以deque作为缺省情况下的queue底部结构

void queue_fun_deque_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int> list_queue; //创建queue

queue_fun_test(list_queue);

}

//以list作为queue底部结构

void queue_fun_list_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int list<int>> list_queue; //创建queue

queue_fun_test(list_queue);

}

/*

//vector是不能作为STL queue底部结构的

void queue_fun_vector_test()

{

cout << endl << __FUNCTION__ << endl;

queue<int vector<int>> list_queue; // error C2039: "pop_front": 不是 "std::vector<int std::allocator<int>>" 的成员

queue_fun_test(list_queue);

}

*/

int queue_main(int argc char* argv[])

{

queue_fun_deque_test();

queue_fun_list_test();

//queue_fun_vector_test();

return 0;

}

---

原创不易，欢迎关注、转发、收藏！