【C++】stack和queue的应用及其模拟实现：适配器与容器适配器
前言
本篇文章主要讲解STL中stack和queue的应用及实现，从这两个容器的学习中还会引出一个新的知识——容器适配器。因为stack和queue的实现很简单，所以本文的核心目标还是让你们知道，理解容器适配器以及适配器的设计模式，这里先透露一点内容，即标准库中一般不把stack，queue简单的定义为容器，而是称为容器适配器，具体的原因，我们之后进行讲解。
一. stack
stack的应用
std::stack的基本使用
| 成员函数 | 功能描述 | 时间复杂度 | 代码示例 | 说明 / 效果 |
|---|---|---|---|---|
push(const T& val) | 将元素压入栈顶 | O(1) | s.push(10); s.push(20); | 栈内元素：[10, 20]（20 在栈顶） |
pop() | 弹出栈顶元素（无返回值，需确保栈非空） | O(1) | s.pop(); | 移除当前栈顶元素（如上例中的 20） |
top() | 返回栈顶元素的可修改引用 | O(1) | s.top() = 100; | 将栈顶元素值修改为 100 |
top() const | 返回栈顶元素的只读引用 | O(1) | int x = s.top(); | x 获得栈顶元素的值（如 100） |
empty() | 判断栈是否为空 | O(1) | if (!s.empty()) { /* ... */ } | 非空时进入条件分支 |
size() | 返回栈中当前元素个数 | O(1) | cout << s.size(); | 输出元素个数（例如 1） |
swap(stack& other) | 交换两个栈的全部底层内容（C++11） | O(1) | stack<int> s2; s2.push(99); s.swap(s2); | 交换后，s 栈顶为 99，s2 获得原 s 的内数据 |
std::stack在算法题中的应用
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
题解
本题的唯一的难点就在于需要在常数的时间内找到栈中最小的元素，那要如何实现呢？首先确定，使用一个变量维护栈中的最小值的方案是不可行的，因为题目还提供了pop的函数接口，这就代表会有数据的删除，当删除的数据刚好是最小值，此时需要再拿到最小值就只能遍历stack了，且不说时间复杂度不是O(1)，就是遍历stack都是一个麻烦的操作。
既然不能使用一个变量维护最小值，就要使用一个容器记录最小值，所以我们考虑使用一个栈minst来维护普通栈st中的最小值，使用st.top()就可以拿到最小值。minst的维护逻辑很简单，维护操作分为两个情况：
- push：当st进行插入数据val时，如果此时minst为空，那么此时st中的最小值一定是val，所以stmin也要插入val。这里还有一个情况就是当
val < stmin.top()时，代表此时st中的最小值要更新了，需要将val插入minst。
这里需要注意的是，容器中可能同时存在多个相同的最小值，举个例子，如st = { 2,3,1,2,1,1,1,5 };，此时为了保证删除操作正确，如果val和stmin.top()相等，也需要插入数据。 - pop：当进行删除栈顶数据时，只需要判断st.top()是否和minst.top()相等，如果相等，代表此时删除的是st中的最小值，所以minst也需要进行删除操作。
class MinStack {
public:
MinStack() {
}
void push(int value) {
st.push(value);
// 如果最小栈为空，或者value小于等于当前栈中的最小值，才将数据插入到minst中
if(minst.empty() || value <= minst.top())
minst.push(value);
}
void pop() {
// 如果删除的值和最小值相同，那minst也要删除栈顶数据
if(st.top() == minst.top())
minst.pop();
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return minst.top();
}
private:
stack<int> st;
stack<int> minst;
};
题目描述
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
题解
逆波兰表达式也称为后缀表达式，而后缀表达式求值是栈的经典应用。因为后缀表达式是将两个需要运算的数字的运算符放在数字的后面，举个例子，如2 3 -就是一个后缀表达式，而它等价于2 - 3。所以给我们一串后缀表达式，要进行求值的关键就是只要遇到运算符号，就找它的前两位数字，然后进行运算得出结果。
因为这里对于数字的运算顺序为：后遇到的数字先计算。所以我们使用栈来存储操作数和操作符，刚好符合这里的计算逻辑。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(const auto& e : tokens)
{
if(e == "+" || e == "-" || e == "*" || e == "/")
{
int behind = st.top(); st.pop();
int front = st.top(); st.pop();
switch(e[0])
{
case '+':
st.push(front + behind);
break;
case '-':
st.push(front - behind);
break;
case '*':
st.push(front * behind);
break;
case '/':
st.push(front / behind);
break;
default:
break;
}
}else
{
st.push(stoi(e));
}
}
return st.top();
}
};
stack的模拟实现
我们知道，栈是一种线性结构的容器，看过我在数据结构篇章的栈和队列的文章的就知道，在数据结构阶段，栈的底层是使用一个顺序表实现的（具体原因我在那篇文章中有详细分析），因此，对于stack的模拟实现，我们也使用顺序表作为它的底层。
基于vector的模拟实现的底层也是一个顺序表，那这里对于stack的实现，还是像vector一样重新写一个顺序表然后封装为stack吗？这样太麻烦了，正确的方法是，直接使用vector作为stack底层的容器，简单点说，就是让vector类型的对象做stack的成员变量。
stack的实现的代码如下，可以看到stack的实现的代码量和逻辑和deque的实现简直是天差地别，包括命名空间仅仅只有16行代码就实现完了，究其原因，都是因为直接对vector和vector的成员函数进行复用，所以将stack说成是简约版的vector也不足为过。
namespace yzx
{
template<class T>
class stack
{
public:
void push(const T& val){ _con.push_back(val); }
void pop(){ _con.pop_back(); }
int& top(){ return _con.back(); }
const int& top() const{ return _con.back(); }
bool empty() const{ return _con.empty(); }
size_t size() const{ return _con.size(); }
private:
vector<T> _con;
};
}
stack模拟实现架构图
二. queue
queue的成员函数
| 成员函数 | 功能描述 | 时间复杂度 | 代码示例 | 说明 / 效果 |
|---|---|---|---|---|
push(const T& val) | 将元素添加到队尾（拷贝构造） | O(1) | q.push(10); q.push(20); | 队列内元素：[10, 20]（10 在队头，20 在队尾） |
pop() | 弹出队头元素（无返回值，需确保队列非空） | O(1) | q.pop(); | 移除队头元素（移除 10），队列变为 [20] |
front() | 返回队头元素的可修改引用 | O(1) | q.front() = 99; | 将当前队头（20）修改为 99 |
front() const | 返回队头元素的只读引用 | O(1) | int x = q.front(); | x 获得队头元素的值（如 99） |
back() | 返回队尾元素的可修改引用 | O(1) | q.back() = 88; | 将当前队尾（20）修改为 88 |
back() const | 返回队尾元素的只读引用 | O(1) | int y = q.back(); | y 获得队尾元素的值（如 88） |
empty() | 判断队列是否为空 | O(1) | if (!q.empty()) { /* ... */ } | 非空时进入条件分支 |
size() | 返回队列中当前元素个数 | O(1) | cout << q.size(); | 输出元素个数（例如 1） |
swap(queue& other) | 交换两个队列的全部底层内容（C++11） | O(1) | queue<int> q2; q2.push(77); q.swap(q2); | 交换后，q 队头为 77，q2 获得原 q 的内容 |
queue的模拟实现
在数据结构给queue的定义中，queue也属于是线性表，且因为queue只能尾部插入数据头部删除数据的特性，所以queue的底层也可以复用一个容器来实现，但是如果再继续使用vector作为queue的底层容器，就是一个不明智的选择了。
因为queue的删除数据是从头部删除的，而众所周知，vector在头部数据操作上效率低的让人难以接受，所以queue的底层容器不选择使用vector，而是选择list作为queue的底层容器。
如下代码为queue以list为底层容器的实现，其简洁程度与stack的模拟实现有过之而无不及。
namespace yzx
{
template<class T>
class queue
{
public:
void push(const T& val){ _con.push_back(val); }
void pop(){ _con.pop_front(); }
T& front(){ return _con.front(); }
T& back(){ return _con.back(); }
const T& front() const { return _con.front(); }
const T& back() const{ return _con.back(); }
size_t size() const{ return _con.size(); }
bool empty() const{ return _con.empty(); }
private:
list<T> _con;
};
}
queue模拟实现架构图
三. 适配器
什么是适配器？
适配器是一种设计模式，其核心理念就是，对同源的东西设计出不同的接口以满足用户不同的需求，举个例子，家用电的电压为220v，但是手机，笔记本，烧水壶的电压却没有那么大，所以，为了适配这些家用电器的电压才产生除了各种不同的充电器，转接器……而这种设计模式就叫做适配器。
适配器模式示意图
容器适配器
C++标准库中也涉及到了适配器的设计模式，其中最具代表性的就是容器适配器。前面我们说了，std::stack和std::queue就是容器适配器，那为什么这样说呢？这是因为，C++标准库为std::stack和std::queue提供了一个接口，使得用户可以根据需求自行的选择实现它们的底层容器，如图 3-2，3-3所示。
从图中可以看到，stack和queue都有一个模板参数Container作为它们底层的容器，而C++标准库中为stack和queue设置的默认的底层实现容器时deque，这里和我们上面所想的不一样，这里为什么要使用deque呢？
原因很简单，deque的特性天然就适合作为stack和queue的底层容器。回顾一下deque，我们说deque的优点是头部和尾部的插入删除数据的效率很高，缺点是中间位置的插入删除效率很低，而stack和queue恰好只能在头部或者尾部插入删除数据。因此，使用deque作为stack和queue不仅发挥了deque的优点，同时又避开了deque的缺点，所以说deque就是stack和queue底层容器的首选。
这里我们根据C++标准库中实现stack和queue的方法，对上面实现的stack和queue进行改造，使得模拟实现的版本也包含适配器的涉及模式，最终代码如下所示。
namespace yzx
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& val){ _con.push_back(val); }
void pop(){ _con.pop_back(); }
int& top(){ return _con.back(); }
const int& top() const{ return _con.back(); }
bool empty() const{ return _con.empty(); }
size_t size() const{ return _con.size(); }
private:
Container _con;
};
}
namespace yzx
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& val){ _con.push_back(val); }
void pop(){ _con.pop_front(); }
T& front(){ return _con.front(); }
T& back(){ return _con.back(); }
const T& front() const { return _con.front(); }
const T& back() const{ return _con.back(); }
size_t size() const{ return _con.size(); }
bool empty() const{ return _con.empty(); }
private:
Container _con;
};
}
更多推荐
11
0- 0
已为社区贡献5条内容
所有评论(0)