C++ Stacks(堆栈) 和 Queues(队列)的基本用法

一、栈

1. 栈的定义

栈(stack)是限定仅在表的一端进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶(stack top)，另一端称为栈底(stack bottom)，不含任何数据素的栈称为空栈。

如图1-1所示，栈中有三个素，插入素（也称为入栈、进栈、压栈）的顺序是a1、a2、a3。当需要删除素（也称为出栈、弹栈）时只能删除a3，换言之，任何时刻出栈的素都只能是栈顶素，即最后入栈者最先出栈，所以栈中素除了具有线性关系外，还具有后进先出(last in first out)的特性。

注意点：栈只是对线性表的插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。也就是说，出栈可随时进行，只要某个素位于栈顶就可以出栈。例如，三个素按a、b、c的次序依次进栈，且每个素只允许进一次栈，则所有素都出栈后，可能的出栈序列有abc、acb、bac、bca、cba五种。

2. 栈的顺序存储结构及实现

栈的顺序存储结构称为顺序栈。顺序栈本质上是顺序表的简化，唯一需要确定的是用数组的哪一端表示栈底。通常把数组中下标为0的一端作为栈底，同时附设变量top指示栈顶素在数组中的位置。设存储栈的数组长度为StackSize，则栈空时栈顶位置top = -1；栈满时栈顶位置top = StackSize - 1。入栈时，栈顶位置top加1；出栈时，栈顶位置top减1。栈的操作的示意图如图1-2所示。

根据栈的操作定义，容易写出顺序栈基本操作的算法，且时间复杂度均为O(1)。

（1）构造函数——顺序栈的初始化

初始化一个空的顺序栈只需要将栈顶指针top置为-1。

SeqStack::SeqStack() { top = -1; }

（2）析构函数——顺序栈的销毁

顺序栈是静态存储分配，在顺序栈变量退出作用域时自动释放顺序栈所占存储单。因此，顺序栈无须销毁，析构函数为空。

SeqStack::~SeqStack() { }

（3）入栈操作

在栈中插入素x只需将栈顶位置top加1，然后在top的位置填入素x。

void SeqStack::Push(int x) { if(top == StackSize) { throw "上溢"; } data[++top] = x; }

（4）出栈操作

出栈操作只需要取出栈顶素，然后将栈顶位置top减1。

int SeqStack::Pop() { int x; if(top == -1) { throw "下溢"; } x = data[top--]; return x; }

（5）取栈顶素

取栈顶素只是将top位置的栈顶素取出并返回，并不修改栈顶位置。

int SeqStack::GetTop() { int x = data[top]; return x; }

（6）判空操作

顺序栈的判空操作只需判断top是否等于-1。

bool SeqStack::Empty() { return top == -1; }

（7）顺序栈的使用

#include<iostream> using namespace std; const int StackSize = 10; class SeqStack { public: SeqStack(); // 构造函数 ~SeqStack(); // 析构函数 void Push(int x); // 入栈操作 int Pop(); // 出栈操作 int GetTop(); // 取栈顶素 bool Empty(); // 判断栈是否为空 private: int data[StackSize]; // 存放栈素的数组 int top; // 栈顶素在数组中的下标 }; SeqStack::SeqStack() { top = -1; } SeqStack::~SeqStack() { } void SeqStack::Push(int x) { if(top == StackSize) { throw "上溢"; } data[++top] = x; } int SeqStack::Pop() { int x; if(top == -1) { throw "下溢"; } x = data[top--]; return x; } int SeqStack::GetTop() { int x = data[top]; return x; } bool SeqStack::Empty() { return top == -1; } int main() { int x; // 定义顺序栈变量s SeqStack s{}; // 入栈 s.Push(15); s.Push(10); s.Push(20); // 取栈顶素 cout << "当前栈顶素：" << s.GetTop() << endl; // 出栈 try { x = s.Pop(); cout << "执行一次出栈操作，删除素：" << x << endl; } catch(char *str) { cout << str << endl; } // 判空操作 if(s.Empty()) { cout << "栈为空" << endl; } else { cout << "栈非空" << endl; } return 0; }

3. 栈的链接存储结构及实现

栈的链接存储结构称为链栈(linked stack)，通常用单链表表示。因为只能在栈顶执行插入和删除操作，显然以单链表的头部作栈顶是最方便的。通常将链栈表示成如图1-3的形式。

链栈的基本操作本质上是单链表基本操作的简化，由于插入和删除操作仅在单链表的头部进行，因此，算法的时间复杂度均为O(1)。

（1）构造函数——链栈的初始化

由于链栈不带头结点，初始化一个空链栈只需将栈顶指针top置为空。

LinkStack::LinkStack() { top = new Node; // 生成头节点 top->next = NULL; // 头节点的指针域置空 }

（2）析构函数——链栈的销毁

链栈是动态存储分配，在链栈变量退出作用域之前要释放链栈的存储空间。

LinkStack::~LinkStack() { Node *q = NULL; while(top != NULL) { // 释放链栈的每一个节点的存储空间 q = top; top = top->next; delete q; } }

（3）入栈操作

链栈的插入操作只需处理栈顶的情况，其操作示意图如图1-4所示。

void LinkStack::Push(int x) { // 将节点s插在栈顶 Node<int>* s = NULL; s = new Node<int>; s->data = x; s->next = top; top = s; }

（4）出栈操作

链栈的删除操作只需处理栈顶的情况，其操作示意图如图1-5所示。

int LinkStack::Pop() { Node<int>* p = NULL; int x; if(top == NULL) { throw "下溢"; } x = top->data; p = top; // 暂存栈顶素 top = top->next; // 将栈顶节点摘链 delete p; return x; }

（5）取栈顶素

取栈顶素只需返回栈顶指针top所指结点的数据域，并不修改栈顶指针。

int LinkStack::GetTop() { if(top == NULL) { throw "下溢异常"; } return top->data; }

（6）判空操作

链栈的判空操作只需判断top指针是否为空。

bool LinkStack::Empty() { if(top == NULL) { return true; } else { return false } }

（7）链栈的使用

#include<iostream> using namespace std; struct Node { int data; // 数据域 Node *next; // 指针域 }; class LinkStack { public: LinkStack(); // 构造函数 ~LinkStack(); // 析构函数 void Push(int x); // 入栈操作 int Pop(); // 出栈 int GetTop(); // 取栈顶素 bool Empty(); // 判空操作 private: Node* top; // 栈顶指针即链表的头指针 }; LinkStack::LinkStack() { top = new Node; // 生成头节点 top->next = NULL; // 头节点的指针域置空 } LinkStack::~LinkStack() { Node *q = NULL; while(top != NULL) { // 释放链栈的每一个节点的存储空间 q = top; top = top->next; delete q; } } void LinkStack::Push(int x) { // 将节点s插在栈顶 Node* s = NULL; s = new Node; s->data = x; s->next = top; top = s; } int LinkStack::Pop() { Node* p = NULL; int x; if(top == NULL) { throw "下溢"; } x = top->data; p = top; // 暂存栈顶素 top = top->next; // 将栈顶节点摘链 delete p; return x; } int LinkStack::GetTop() { if(top == NULL) { throw "下溢异常"; } return top->data; } bool LinkStack::Empty() { if(top == NULL) { return true; } else { return false; } } int main() { int x; // 定义链栈变量s LinkStack s{}; // 入栈 s.Push(15); s.Push(10); s.Push(20); // 取栈顶素 cout << "当前栈顶素：" << s.GetTop() << endl; // 出栈 try { x = s.Pop(); cout << "执行一次出栈操作，删除素：" << x << endl; } catch(char *str) { cout << str << endl; } // 入栈 try { cout << "请输入待插入素："; cin >> x; s.Push(x); } catch(char *str) { cout << str << endl; } // 判空操作 if(s.Empty()) { cout << "栈为空" << endl; } else { cout << "栈非空" << endl; } return 0; }

4. 顺序栈和链栈的比较

顺序栈和链栈基本操作的时间复杂度均为O(1)，因此唯一可以比较的是空间性能。初始时顺序栈必须确定一个固定的长度，所以有存储素个数的限制和浪费空间的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个素需要一个指针域，从而产生了结构性开销。作为一般规律，当栈的使用过程中素个数变化较大时，应采用链栈，反之，应该采用顺序栈。

	顺序栈	链栈
时间复杂度	O(1)	O(1)
栈的大小	固定	不固定，可动态调整
空间开销	存在存储素个数的限制和浪费空间的问题	每个素需一个指针域，产生结构开销
适用场景	使用过程中素个数变化不大	使用过程中素个数变化较大

5. 两栈共享空间

在一个程序中，如果同时使用具有相同数据类型的两个顺序栈，最直接的方法是为每个栈开辟一个数组空间，这样做的结果可能出现一个栈的空间已被栈满而无法再进行插入操作，同时另一个栈的空间仍有大量剩余而没有得到利用的情况，从而造成存储空间的浪费。可用充分利用顺序栈单向延伸的特性，使用一个数组来存储两个栈，让一个栈的栈底位于该数组的始端，另一个栈的栈底位于该数组的末端，每个栈从各自的断点向中间延伸，如图1-6所示。其中，top1和top2分别为栈1和栈2的栈顶位置，StackSize为整个数组空间的大小，栈1的底位于下标为0的一端；栈2的底位于下标为StackSize - 1的一端。

在两栈共享空间中，由于两栈相向增长，浪费的数组空间就会减少，同时发生上溢的概率也会减少。但是，只有当两个栈的空间需求有相反的关系时，这种方法才会奏效，也就是说，最好一个栈增长时另一个栈缩短。

设整形变量i只取1和2两个值。当i = 1时，表示对栈1操作；当i = 2时表示对栈2操作。

（1）构造函数

BothStack::BothStack() { top1 = -1; top2 = StackSize; }

（2）析构函数

BothStack::~BothStack() { }

（3）入栈操作

当存储栈的数组中没有空闲单时为栈满，此时栈1的栈顶素和栈2的栈顶素位于数组中的相邻位置，即top1 = top2-1。另外，当新的素插入栈2时，栈顶位置top2不是加1而是减1.。

void BothStack::Push(int i, int x) { if(top1 == top2 - 1) { // 栈满 throw "上溢"; } if(i == 1) { // 栈1 data[++top1] = x; } else { // 栈2 data[--top2] = x; } }

（4）出栈操作

当top1 = -1时栈1为空，当top2 = StackSize时栈2为空。另外，当从栈2删除素时，栈顶位置top2不是减1而是加1。

int BothStack::Pop(int i) { int x; if(i == 1) { // 栈1 if(top1 == -1) { // 空栈 throw "下溢"; } x = data[top1--]; } else { // 栈2 if(top2 == StackSize) { // 空栈 throw "下溢"; } x = data[top2++]; } return x; }

（5）取栈顶素

int BothStack::GetTop(int i) { if(i == 1) { // 栈1 if(top1 == -1) { throw "下溢异常"; } else { return data[top1]; } } else { // 栈2 if(top2 == StackSize) { throw "下溢异常"; } else { return data[top2]; } } }

（6）判空操作

bool BothStack::Empty(int i) { if(i == 1) { // 栈1 if(top1 == -1) { return true; } else { return false; } } else { // 栈2 if(top2 == StackSize) { return true; } else { return false; } } }

（7）两栈共享空间的使用

#include<iostream> using namespace std; const int StackSize = 100; class BothStack { public: BothStack(); // 构造函数 ~BothStack(); // 析构函数 void Push(int i, int x); // 入栈操作，将素i压入栈i int Pop(int i); // 出栈操作，对栈i执行出栈操作 int GetTop(int i); // 取栈i的栈顶素 bool Empty(int i); // 判断栈i是否为空栈 private: int data[StackSize]; // 存放两个栈的数组 int top1, top2; // 两个栈的栈顶指针 }; BothStack::BothStack() { top1 = -1; top2 = StackSize; } BothStack::~BothStack() { } void BothStack::Push(int i, int x) { if(top1 == top2 - 1) { // 栈满 throw "上溢"; } if(i == 1) { // 栈1 data[++top1] = x; } else { // 栈2 data[--top2] = x; } } int BothStack::Pop(int i) { int x; if(i == 1) { // 栈1 if(top1 == -1) { // 空栈 throw "下溢"; } x = data[top1--]; } else { // 栈2 if(top2 == StackSize) { // 空栈 throw "下溢"; } x = data[top2++]; } return x; } int BothStack::GetTop(int i) { if(i == 1) { // 栈1 if(top1 == -1) { throw "下溢异常"; } else { return data[top1]; } } else { // 栈2 if(top2 == StackSize) { throw "下溢异常"; } else { return data[top2]; } } } bool BothStack::Empty(int i) { if(i == 1) { // 栈1 if(top1 == -1) { return true; } else { return false; } } else { // 栈2 if(top2 == StackSize) { return true; } else { return false; } } } int main() { int x; BothStack s; cout << "对15执行栈1的入栈操作, "; s.Push(1, 15); cout << "当前栈1的栈顶素为：" << s.GetTop(1) << endl; // 15 cout << "对10执行栈2的入栈操作, "; s.Push(2, 15); cout << "当前栈2的栈顶素为：" << s.GetTop(2) << endl; // 15 try { x = s.Pop(1); cout << "对栈1执行一次出栈操作，删除素" << x << endl; // 15 } catch(char *str) { cout << str << endl; } try { cout << "请输入待入栈素："; cin >> x; s.Push(2, x); } catch(char *str) { cout << str << endl; } if(s.Empty(1)) { cout << "栈1为空" << endl; // 栈1为空 } else { cout << "栈1非空" << endl; } if(s.Empty(2)) { cout << "栈2为空" << endl; } else { cout << "栈2非空" << endl; // 栈2非空 } return 0; }

6. C++ Stacks(堆栈)常用的API

头文件：#include<stack>

（1）empty

语法：bool empty();

如果当前栈为空，empty()函数返回true，否则返回false。

（2）pop

语法：void pop();

pop()函数移除堆栈中最顶层素。

（3）push

语法：void push(const TYPE &val);

push()函数将val值压栈，使其成为栈顶的第一个素。

（4）size

语法：size_type size();

size()函数返回当前堆栈中的素数目。

（5）top

语法：TYPE &top();

top()函数返回对栈顶素的引用。

（6）使用示例

#include<iostream> #include<stack> using namespace std; int main() { stack<int> s; // 入栈操作 s.push(5); s.push(10); s.push(15); // 获取栈的大小 int size = s.size(); cout << "栈当前的大小为：" << size << endl; // 3 // 判空操作 if(s.empty()) { cout << "栈为空" << endl; } else { cout << "栈非空" << endl; // 栈非空 } // 获取栈顶素 cout << "当前栈顶素为：" << s.top() << endl; // 15 // 出栈操作 s.pop(); cout << "出栈后新的栈顶素为：" << s.top() << endl; // 10 return 0; }

二、队列

1. 队列的定义

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表，允许插入（也称入队、进队）的一端称为队尾，允许删除（也称为出队）的一端称为队头。图2-1所示的一个有5个素的队列，入队的顺序为a1、a2、a3、a4、a5，出队的顺序依然是a1、a2、a3、a4、a5，即最先入队者最先出队。所以队列中的素除了具有线性关系外，还具有先进先出(first in first out)的特性。

2. 队列的顺序存储结构及实现

2-1. 顺序队列的存储结构

队列的顺序存储结构称为顺序队列。假设队列有n个素，顺序队列把队列的所有素存储在数组的前n个单。如果把队头素放在数组中下标为0的一端，则入队操作相当于追加，不需要移动素，其时间性能为O(1)，但是出队操作的时间性能为O(n)，因为要保证剩下的n - 1个素仍然存储在数组的前n - 1个单，所有素都要向前移动一个位置，如图2-2(c)所示。

如果放宽队列的所有素必须存储在数组的前n个单这一条件，就可以得到一种更为有效的存储方法，如2-2(d)所示。此时入队和出队操作的时间性能都是O(1)，因为没有移动任何素，但是队列的队头和队尾都是活动的，因此，需要设置队头、队尾两个位置变量front和rear，入队时rear加1，出队时front加1，并且约定：front指向队头素的前一个位置，rear指向队尾素的位置。

2-2. 循环队列的存储结构

在循环队列中，随着队列的插入和删除操作，整个队列向数组的高端移过去，从而产生了队列的“单向移动性”。当素被插入到数组中下标最大的位置之后，数组空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫作假溢出，如图2-3(a)所示。

解决假溢出的方法是将存储队列的数组看成是头尾相接的循环结构，即允许队列直接从数组中下标最大的位置延续到下标最小的位置，如图2-3(b)所示，这可以通过取模操作来实现，设存储队列的数组长度为QueueSize，操作语句为rear = (rear + 1) % QueueSize。队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列中，队空的条件为：front = rear。队满的条件为：（rear + 1) % QueueSize = front。

根据队列的操作定义，容易写出循环队列基本操作的算法，其时间复杂度均为O(1)。

（1）构造函数——循环队列的初始化

初始化一个空的循环队列只需将队头front和队尾rear同时指向数组的某一个位置，一般是数组的最高端，即rear = front = QueueSize - 1。

CirQueue::CirQueue() { front = QueueSize - 1; rear = QueueSize - 1; }

（2）析构函数——循环队列的销毁

循环队列是静态存储分配，在循环队列变量退出作用域时自动释放所占内存单，因此，循环队列无须销毁，析构函数为空。

CirQueue::~CirQueue() { }

（3）入队操作

循环队列的入队操作只需将队尾位置rear在循环意义下加1，然后将待插素x插入队尾位置。

void CirQueue::EnQueue(int x) { if((rear + 1) % QueueSize == front) { throw "上溢"; } rear = (rear + 1) % QueueSize; data[rear] = x; }

（4）出队操作

循环队列的出队操作只需将队头位置front在循环意义下加1，然后读取并返回队头素。

int CirQueue::DeQueue() { if(rear == front) { throw "下溢"; } front = (front + 1) % QueueSize; return data[front]; }

（5）取队头素

读取队头素与出队操作类似，唯一的区别是不改变队头位置。

int CirQueue::GetHead() { if(rear == front) { throw "下溢"; } return data[(front + 1) % QueueSize]; }

（6）判空操作

循环队列的判空操作只需判断front是否等于rear。

bool CirQueue::Empty() { return front == rear; }

（7）循环队列的使用

#include<iostream> using namespace std; const int QueueSize = 100; class CirQueue { public: CirQueue(); // 构造函数 ~CirQueue(); // 析构函数 void EnQueue(int x); // 入队操作 int DeQueue(); // 出队操作 int GetHead(); // 获取队头素 bool Empty(); // 判空操作 private: int data[QueueSize]; // 存放队列素的数组 int front, rear; // 队头和队尾指针 }; CirQueue::CirQueue() { front = QueueSize - 1; rear = QueueSize - 1; } CirQueue::~CirQueue() { } void CirQueue::EnQueue(int x) { if((rear + 1) % QueueSize == front) { throw "上溢"; } rear = (rear + 1) % QueueSize; data[rear] = x; } int CirQueue::DeQueue() { if(rear == front) { throw "下溢"; } front = (front + 1) % QueueSize; return data[front]; } int CirQueue::GetHead() { if(rear == front) { throw "下溢"; } return data[(front + 1) % QueueSize]; } bool CirQueue::Empty() { return front == rear; } int main() { int x; CirQueue Q{}; // 入队操作 Q.EnQueue(5); Q.EnQueue(8); Q.EnQueue(10); // 获取队头素 cout << "当前队头素为：" << Q.GetHead() << endl; // 出队操作 try { x = Q.DeQueue(); cout << "执行一次出队操作，出队素为：" << x << endl; } catch(char *str) { cout << str << endl; } // 入队操作 try { cout << "请输入入队素："; cin >> x; Q.EnQueue(x); } catch(char *str) { cout << str << endl; } // 判空操作 if(Q.Empty()) { cout << "队列为空" << endl; } else { cout << "队列非空" << endl; } return 0; }

3. 队列的链接存储结构及实现

队列的链接存储结构称为链队列，通常用单链表表示，其节点结构与单链表的节点结构相同。为了使空队列和非空队列的操作一致，链队列也加上头节点。根据队列的先进先出特性，为了操作上的方便，设置队头指针指向链队列的头节点，队尾指针指向终端节点，如图3-1所示。

链队列基本操作的实现本质上是单链表操作的简化，且时间复杂度均为O(1)。

（1）构造函数——链队列的初始化

初始化链队列只需申请头节点，然后让队头指针和队尾指针均指向头节点。

LinkQueue::LinkQueue() { Node *s = NULL; s = new Node; s->next = NULL; front = rear = s; // 将队头指针和队尾指针都指向头节点s }

（2）析构函数——链队列的销毁

链队列是动态存储分配，需要释放链队列的所有节点的存储空间。

LinkQueue::~LinkQueue() { Node *q = NULL; while(front != NULL) { q = front; front = front->next; delete q; } }

（3）入队操作

链队列的插入操作只考虑在链表的尾部进行，由于链队列带头节点，空链队列和非空链队列的插入操作语句一致，其操作示意图如图3-2所示。

void LinkQueue::EnQueue(int x) { Node *s = NULL; s = new Node; s->data = x; s->next = NULL; rear->next = s; rear = s; // 将节点s插入到队尾 }

在不带头结点的链队列中执行入队操作，在空链队列和非空链队列的操作语句是不同的，如图3-3所示，所以，为了操作方便，链队列一般都带头节点。

（4）出队操作

链队列的删除操作只考虑在链表的头部进行，注意队列长度等于1的特殊情况，其操作示意图如图3-4所示。

int LinkQueue::DeQueue() { int x; Node *p = NULL; if(rear == front) { throw "下溢"; } p = front->next; x = p->data; front->next = p->next; // 将队头素所在节点摘链 if(p->next == NULL) { rear = front; // 出队前队列长度为1 } delete p; return x; }

（5）取队头素

取链队列的队头素只需返回第一个素节点的数据域，即返回front->next->data。

int LinkQueue::GetHead() { return front->next->data; }

（6）判空操作

链队列的判空操作只需判断front是否等于rear。

bool LinkQueue::Empty() { return front == rear; }

（7）链队列的使用

#include<iostream> using namespace std; struct Node { int data; // 数据域 Node *next; // 指针域 }; class LinkQueue { public: LinkQueue(); // 构造函数 ~LinkQueue(); // 析构函数 void EnQueue(int x); // 入队操作 int DeQueue(); // 出队操作 int GetHead(); // 获取队头素 bool Empty(); // 判空操作 private: Node *front, *rear; }; LinkQueue::LinkQueue() { Node *s = NULL; s = new Node; s->next = NULL; front = rear = s; // 将队头指针和队尾指针都指向头节点s } LinkQueue::~LinkQueue() { Node *q = NULL; while(front != NULL) { q = front; front = front->next; delete q; } } void LinkQueue::EnQueue(int x) { Node *s = NULL; s = new Node; s->data = x; s->next = NULL; rear->next = s; rear = s; // 将节点s插入到队尾 } int LinkQueue::DeQueue() { int x; Node *p = NULL; if(rear == front) { throw "下溢"; } p = front->next; x = p->data; front->next = p->next; // 将队头素所在节点摘链 if(p->next == NULL) { rear = front; // 出队前队列长度为1 } delete p; return x; } int LinkQueue::GetHead() { return front->next->data; } bool LinkQueue::Empty() { return front == rear; } int main() { int x; LinkQueue Q; // 入队操作 Q.EnQueue(5); Q.EnQueue(8); Q.EnQueue(10); // 获取队头素 cout << "当前队头素为：" <<Q.GetHead() << endl; // 出队操作 try { x = Q.DeQueue(); cout << "执行一次出队操作，出队素为：" << x << endl; } catch(char *str) { cout << str << endl; } // 入队操作 try { cout << "请输入入队素："; cin >> x; Q.EnQueue(x); } catch(char *str) { cout << str << endl; } // 判空操作 if(Q.Empty()) { cout << "队列为空" << endl; } else { cout << "队列非空" << endl; } return 0; }

4. 循环队列和链队列的比较

循环队列和链队列基本操作的时间复杂度均为O(1)。因此，可以比较的只有空间性能。初始时，循环队列必须确定一个固定的长度，所以有存储素个数的限制和浪费空间的问题。链队列没有溢出的问题，只有当内存没有可用空间时才会出现溢出，但是每个素都需要一个指针域，从而产生了结构性开销。作为一般规律，当队列中素个数变化较大时，应该采用链队列；反之，应该采用循环队列，如果确定不会发生假溢出，也可以采用顺序队列。

5. 双端队列

双端队列是队列的扩展，如图5-1所示。如果允许在队列的两端进行插入和删除操作，则称为双端队列；如果允许在两端插入但只允许在一端删除，则称为二进一出队列；如果只允许在一端插入但允许在两端删除，则称为一进二出队列。

双端队列和普通队列一样，具有入队、出队、取队头素等基本操作，不同的是必须指明操作的位置。双端队列可以采用循环队列的存储方式，基本算法可以在循环队列的基础上修改而成。不同的是，在队头入队，先将新素插入到front处，再把队头位置front在循环意义下减1；在队尾出队时，先将rear处的队尾素暂存，再把队尾位置rear在循环意义下减1。

C++ Double Ended Queues(双端队列)

（1）Constructors

语法：

deque();

deque(size_type size);

deque(size_type num, const TYPE &val);

deque(const deque &from);

deque(input_iterator start, input_iterator end);

C++ Deques能用以下方式创建：

无参，创建一个空双端队列
size，创建一个大小为size的双端队列
num and val，放置num个val的拷贝到队列中
from，从from创建一个内容一样的双端队列
start 和 end，创建一个队列，保存从start到end的素

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq(10, 1); // 创建一个双端队列，里面有10个1 deque<int>::iterator it; for(it = dq.begin(); it != dq.end(); ++it) { // 1 1 1 1 1 1 1 1 1 1 cout << *it << " "; } return 0; }

（2）Operators

语法：[]

可以使用[]操作符访问双端队列中单个的素。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq(10, 1); deque<int>::iterator it; cout << dq[2]; // 1 return 0; }

（3）assign

语法：

void assign(input_iterator start, input_iterator end);

void assign(Size num, const TYPE &val);

assign()函数用start和end指示的范围为双端队列赋值，或者设置成num个val。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq(10, 1); int arr[] = {1, 2, 3, 4, 5}; // 使用assign函数将数组中的素赋值给dq dq.assign(begin(arr), end(arr)); // 输出dq中的素 for(int num : dq) { // 1 2 3 4 5 cout << num << " "; } return 0; }

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq; // 使用assign函数将5个素值为10的素赋值给dq dq.assign(5, 10); // num value // 输出dq中的素 for(int num : dq) { // 10 10 10 10 10 cout << num << " "; } return 0; }

（4）at

语法：reference at(size_type pos);

at()函数返回一个引用，指向双端队列中位置pos上的素。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5}; int x = dq.at(2); cout << x << endl; // 3 dq.at(4) = 6; // 使用at()函数返回双端队列中指定位置的素并修改 // 输出修改后的双端队列中的素 for(int num : dq) { // 1 2 3 4 6 cout << num << " "; } return 0; }

（5）back

语法：reference back();

back()返回一个引用，指向双端队列中最后一个素。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5}; int x = dq.back(); cout << x; // 5 return 0; }

（6）begin

语法：iterator begin();

begin()函数返回一个迭代器，指向双端队列的第一个素。

（7）clear

语法：void clear();

clear()函数删除双向队列中所有的素。

（8）empty

语法：bool empty();

empty()返回true如果双端队列为空，否则返回false。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5}; // 清空双端队列 dq.clear(); // 判空 if(dq.empty()) { cout << "双端队列为空" << endl; // 双端队列为空 } else { cout << "双端队列非空" << endl; } return 0; }

（9）end

语法：iterator end();

end()函数返回一个迭代器，指向双端队列的尾部。

（10）erase

语法：

iterator erase(iterator pos);

iterator erase(iterator start, iterator end);

erase()函数删除pos位置上的素，或者删除start和end之间的所有素。返回值是一个iterator，指向被删除素的后一个素。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 删除双端队列中第三个素 dq.erase(dq.begin() + 2); // 输出删除素后的双端队列中的素 for(int num : dq) { // 1 2 4 5 6 7 8 9 10 cout << num << " "; } cout << endl; // 删除双端队列中第二个到第四个素 dq.erase(dq.begin() + 1, dq.begin() + 4); // 输出删除素后的双端队列中的素 for(int num : dq) { // 1 6 7 8 9 10 cout << num << " "; } return 0; }

（11）front

语法：reference front();

front()函数返回一个引用，指向双端队列的头部。

（12）get_allocator

语法：allocator_type get_allocator();

get_allocator()函数返回双端队列的配置器。

（13）insert

语法：

iterator insert(iterator pos, size_type num, const TYPE &val);

void insert(iterator pos, input_iterator start, input_iterator end);

insert()在pos前插入num个val值，或者插入从start到end范围内的素到pos前面。

（14）max_size

语法：size_type max_size();

max_size()返回双端队列能容纳的最大素个数。

（15）pop_back

语法：void pop_back();

pop_back()删除双向队列尾部的素。

（16）pop_front

语法：void pop_front();

pop_front()删除双端队列头部的素。

（17）push_back

语法：void push_back(const TYPE &val);

push_back()函数在双向队列的尾部加入一个值为val的素。

（18）push_front

语法：void push_front(const TYPE &val);

push_front()函数在双端队列的头部加入一个值为val的素。

（19）rbegin

语法：reverser_iterator rbegin();

rbegin()返回一个指向双端队列尾部的逆向迭代器。

（20）rend

语法：reverse_iterator rend();

rend()返回一个指向双端队列头部的逆向迭代器。

（21）resize

语法：void resize(size_type num, TYPE val);

resize()改变双向队列的大小为num，另新加入的素都被填充为val。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; dq.resize(20, 8); for(int num : dq) { // 1 2 3 4 5 6 7 8 9 10 8 8 8 8 8 8 8 8 8 8 cout << num << " "; } return 0; }

（22）size

语法：size_type size();

size()函数返回双端队列中素的个数。

（23）swap

语法：void swap(deque &target);

swap()函数交换target和现双端队列中的素。

#include<iostream> #include<deque> using namespace std; int main() { deque<int> dq = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; deque<int> dq2 = {11, 12, 13, 14, 15, 16, 17, 18, 19, 20}; dq.swap(dq2); cout << "dq中的素："; for(int num : dq) { // 11 12 13 14 15 16 17 18 19 20 cout << num << " "; } cout << endl; cout << "dq2中的素："; for(int num : dq2) { // 1 2 3 4 5 6 7 8 9 10 cout << num << " "; } return 0; }

6. C++ Priority Queues(优先队列)

与queue的不同之处在于我们可以自定义队列中数据的优先级，让优先级高的排在队列前面，优先出队。优先队列具有队列的所有特性，包括基本操作。优先队列的底层实现通常是基于堆(heap)数据结构，具体来说是使用小根堆或大根堆。

基本用法示例：使用priority_queue创建了一个大根堆的优先队列。

#include <iostream> #include <queue> int main() { // 创建一个大根堆的优先队列，素类型为int std::priority_queue<int, vector<int>, less<int> > pq; // 插入素 pq.push(30); pq.push(10); pq.push(50); pq.push(20); // 输出队列中的素，按照优先级从高到低输出 while (!pq.empty()) { // 50 30 20 10 std::cout << pq.top() << " "; pq.pop(); } std::cout << std::endl; return 0; }

除了默认的大根堆实现，priority_queue还可以通过自定义比较函数来实现小根堆：

#include <iostream> #include <queue> int main() { // 创建一个小根堆的优先队列，素类型为int std::priority_queue<int, std::vector<int>, std::greater<int> > pq; // 插入素 pq.push(30); pq.push(10); pq.push(50); pq.push(20); // 输出队列中的素，按照优先级从低到高输出 while (!pq.empty()) { // 10 20 30 50 std::cout << pq.top() << " "; pq.pop(); } std::cout << std::endl; return 0; }

对于pair的比较，先比较第一个素，第一个相等的比较第二个：

#include <iostream> #include <queue> #include <vector> using namespace std; int main() { priority_queue<pair<int, int> > q; pair<int, int> a(1, 2); pair<int, int> b(1, 3); pair<int, int> c(2, 5); q.push(a); q.push(b); q.push(c); while (!q.empty()) { cout << q.top().first << ' ' << q.top().second << '\n'; q.pop(); } /* 2 5 1 3 1 2 */ return 0; }

7. C++ Queues(队列)常用的API

头文件：#include<queue>

（1）back

语法：TYPE &back();

back()返回一个引用，指向队列的最后一个素。

（2）empty

语法：bool empty();

empty()函数返回true如果队列为空，否则返回false。

（3）front

语法：TYPE &front();

front()返回队列第一个素的引用。

（4）pop

语法：void pop();

pop()函数删除队列的第一个素。

（5）push

语法：void push(const TYPE &val);

push()函数往队列中加入一个素。

（6）size

语法：size_type size();

size()返回队列中素的个数。

（7）使用示例

#include<iostream> #include<queue> using namespace std; int main() { queue<int> q; // 入队操作 q.push(5); q.push(10); q.push(15); // 获取队列的大小 cout << "队列的大小为：" << q.size() << endl; // 3 // 判空操作 if(q.empty()) { cout << "队列为空" << endl; } else { cout << "队列非空" << endl; // 队列非空 } // 获取队头素 cout << "队列的队头素为：" << q.front() << endl; // 5 // 获取队尾素 cout << "队列的队尾素为：" << q.back() << endl; // 15 // 出队操作 q.pop(); cout << "出队操作后新的队头素为：" << q.front() << endl; // 10 }

今天的文章 C++ Stacks(堆栈) 和 Queues(队列)的基本用法分享到此就结束了，感谢您的阅读。