【c++丨STL】stack和queue的使用及模拟实现

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：C++、STL

前言

一、什么是容器适配器

二、stack的使用及模拟实现

1. stack的使用

empty

size

top

push和pop

swap

2. stack的模拟实现

三、queue的使用及模拟实现

1. queue的使用

empty

size

front和back

push和pop

swap

2. queue的模拟实现

总结

前言

本篇文章，博主将介绍STL中两个比较重要的容器适配器：stack（栈）和queue（队列）以及它们的使用方法，并且尝试模拟实现它们。如果你不是很了解栈和队列这两种数据结构，可以参阅这篇文章：

【数据结构】栈和队列（c语言实现）（附源码）_创建栈和队列及使用代码-CSDN博客

正文开始

一、什么是容器适配器

与vector、list这些容器不同，stack和queue被称作容器适配器。所谓容器适配器，就是指在一种已有的容器基础上，为其添加了一些新的特性或者功能，目的是使一事物的行为类似于另一类事物。

比如说栈这一数据结构，它的本质其实就是对顺序表或者链表的功能进行了一些限制，例如无法遍历、只能在一端进出数据等，但其底层仍然是顺序结构或是链式结构。STL在设计stack和queue时，并没有从零开始构建它们的底层结构，而是采用了这种设计思想，对现有容器进行了封装，从而实现了它们。

接下来，我们看看SGI版本的STL源码是怎么实现stack的：

可以看到，源码使用了一个叫做deque的容器创建对象，然后调用该对象的一些接口来实现stack的接口。之后模拟实现stack和queue的过程中，我们也将遵循源码的设计思路，对其他容器（例如vector和list）进行封装。

关于deque(双端队列)的底层结构，博主将在后续文章中讲解。

二、stack的使用及模拟实现

接下来，我们正式开始学习stack的使用方法，并尝试模拟实现。

1. stack的使用

stack的成员函数如下：

注意：容器适配器是不支持遍历的，所以它们没有迭代器接口。

empty

empty的作用是判断栈是否为空，若为空则返回true，否则返回false。

代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{stack<int> s1;stack<int> s2;s2.push(1);//压入一个元素cout << s1.empty() << endl;cout << s2.empty() << endl;return 0;
}

size

size用于获取栈中元素个数。

代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{stack<int> s;s.push(1);s.push(1);s.push(1);cout << s.size() << endl;return 0;
}

top

top用于获取栈顶元素。代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{stack<int> s;s.push(10);cout << s.top() << endl;return 0;
}

push和pop

push的功能是将数据压入栈顶，而pop可以将栈顶元素弹出。

使用举例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{stack<int> s;for (int i = 1; i <= 10; i++)//循环压入十个元素{s.push(i);}while (!s.empty())//栈非空则循环出栈{cout << s.top() << ' ';s.pop();//出栈}return 0;
}

swap

swap用于交换两个栈的内容。

2. stack的模拟实现

stack的模拟实现也比较简单，由于我们之前使用顺序结构来实现栈，那么我们就将vector作为封装容器。代码如下：

#include <iostream>
#include <vector>
using namespace std;template<class T, class Container = vector<T>>//模板参数默认为vector
class Stack
{
public://压栈void push(const T& x){_con.push_back(x);//调用vector的尾插}//出栈void pop(){_con.pop_back();//调用vector的尾删}//取栈顶元素const T& top() const{return _con.back();//调用vector的获取尾元素}//判空bool empty() const{return _con.empty();//调用vector的empty}//获取元素个数size_t size() const{return _con.size();//调用vector的size}//交换void swap(Stack<T>& s){_con.swap(s._con);//调用vector的交换函数}
private:Container _con;//成员容器
};

三、queue的使用及模拟实现

在掌握了stack的使用与模拟实现之后，我们为大家介绍queue的使用及模拟实现。

1. queue的使用

queue的成员函数如下：

empty

empty用于判断队列是否为空。若为空则返回true，否则返回flase。

代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{queue<int> q1;queue<int> q2;q1.push(1);cout << q1.empty() << endl;cout << q2.empty() << endl;return 0;
}

size

size用于获取队列中的元素个数。代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{queue<int> q;q.push(1);q.push(1);q.push(1);q.push(1);q.push(1);cout << q.size() << endl;return 0;
}

front和back

front和back分别用于获取对头/队尾元素。代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.front() << endl;cout << q.back() << endl;return 0;
}

push和pop

push和pop分别用于进行入队/出队操作。注意对头出队，队尾入队。

代码示例：

#include <iostream>
#include <stack>
#include <queue>
using namespace std;int main()
{queue<int> q;for (int i = 1; i <= 10; i++){q.push(i);}while (!q.empty()){cout << q.front() << ' ';q.pop();}return 0;
}

swap

swap用于交换两个队列的内容。

2. queue的模拟实现

接下来，我们尝试模拟实现queue。由于list具有头删和尾插的接口，我们就将list作为封装容器。代码实现如下：

#include <iostream>
#include <list>
using namespace std;template<class T, class Container = list<T>>//模板参数默认为list
class Queue
{
public://入队void push(const T& x){_con.push_back(x);//调用list的尾插}//出队void pop(){_con.pop_front();//调用list的头删}//取队头元素const T& front(){return _con.front();//调用list的front}//取队尾元素const T& back(){return _con.back();//调用list的back}//获取元素个数size_t size(){return _con.size();//调用list的size}//判空bool empty(){return _con.empty();//调用list的empty}//交换void swap(Queue<T>& q){_con.swap(q._con);//交换两个成员容器的内容}
private:Container _con;//成员容器
};