前言

在现代C++编程中，STL（标准模板库）是一个不可或缺的工具。它提供了一套通用的模板类和算法，使得开发者能够更加高效地处理数据。本文将重点介绍STL中的stack容器，作为一种重要的顺序容器，stack遵循后进先出（LIFO，Last In First Out）的特性，广泛应用于函数调用、表达式求值等场景。通过深入了解stack的特性、基本操作及应用实例，读者将能够更好地掌握和应用这一重要的数据结构。

博客主页: 酷酷学!!!

感谢关注!!!

---

正文开始

1. stack的介绍

1. stack是一种容器适配器, 专门用在具有后进先出操作的上下文环境中, 其删除只能从容器的一端进行元素的插入与提取操作.
2. stack是作为容器适配器被实现的, 容器适配器即是对特定类作为其底层的容器, 并提供了一组特定的成员函数来访问其元素, 将特定类作为其底层的, 元素特定容器的尾部(即栈顶)被压入和弹出.
3. stack的容器可以是任何形式的容器类模板或者一些其他特定的容器类, 这些容器类应该支持以下操作:

• empty: 判空操作
• back: 获取尾部元素操作
• push_back: 尾部插入元素操作
• pop_back: 尾部删除元素操作

4. 标准容器vector, deque, list均符合这些需求, 默认情况下, 如果没有为stack指定特定的底层容器, 默认情况下使用deque.

2. stack的使用

重点:

代码演示:

#include<stack>
#include<iostream>
using namespace std;
int main()
{stack<int> st;st.push(1);st.push(2);cout << st.top() << endl;st.pop();cout << st.size() << endl;st.pop();cout << st.empty() << endl;return 0;
}

3. stack的模拟实现

从栈的接口中可以看出, 栈实际上是一种特殊的vector, 因此使用vector完全可以模拟实现stack.

#pragma once
#include<iostream>
#include<vector>
#include<list>
using namespace std;namespace my
{//传统写法//template<class T>//class stack//{//private://	T* _a;//	int _top;//	int _capacity;//};//直接复用容器template<class T, class Container = vector<T>> //当然适配器也可以是其他容器class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}

4. stackOJ题目

4.1 最小栈

题目链接:最小栈

题目描述:

题目思路:

题目要求在常数时间内求出栈中最小元素, 如果我们遍历栈, 时间复杂度就为N, 不符合题目要求, 我们可以创建两个栈, 一个用来模拟入栈出栈, 一个用来记录最小数据, 定义两个栈为成员函数, 首先, 先插入一个元素, 然后让出栈序列与入栈的栈顶元素进行比较, 如果_minst为空或者栈顶元素小于或者等于_minst的栈顶元素, 则将数据push到最小栈, 出栈时, 如果_st的栈顶元素等于_minst的栈顶元素, 则_minst出栈, 即更改了当前最小元素.

代码演示:

class MinStack {
public:MinStack() {}void push(int val) {if(_minst.empty() || val <= _minst.top()){_minst.push(val);}_st.push(val);}void pop() {if(_st.top() == _minst.top()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}stack<int> _st;stack<int> _minst;};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

4.2 栈的压入弹出序列

题目链接:栈的压入弹出序列

题目描述:

题目思路

对于栈的压入弹出序列, 我们如果直接上手对比, 很容易出错, 而且比较麻烦, 我们可以对入栈与出栈进行栈的模拟, 创建一个栈st, 对入栈序列进行遍历插入, 先插入一个元素, 然后与出栈序列进行对比, 遍历出栈序列, 如果与出栈序列相等, 则说明该出栈了, 就pop出此时的栈, 这时还不能插入新的元素, 继续将st的栈顶元素与出栈序列对比, 如果不想等了, 我们再插入, 然后再进行下一轮的对比, 或者此时st已经为空了, 则跳出循环, 也进行下一轮的插入对比, 如果插入序列全部遍历完, 而出栈序列没有遍历完, 则说明此出栈序列不为栈的弹出序列, 反之亦然.也可以判断此时栈是否为空即可.

代码演示:

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;int pos = 0;for(auto e : pushV){st.push(e);while( !st.empty() && st.top() == popV[pos]){pos++;st.pop();}}return st.empty();}
};

4.3 用栈实现队列

题目链接:

用栈实现队列

题目描述:

题目思路

对于本题我们再栈的那一篇已经使用c语言完成过了, 本次我们采用C++进行完成, 避免了我们自己造轮子, 还是一样, 用两个栈实现一个队列, 一个栈进行插入, 如果需要出栈, 则就把所有的插入栈所有数据导一下,出栈直接出popst中的元素.

代码演示

class MyQueue {
public:MyQueue() {}void push(int x) {pushst.push(x);}int pop() {if(popst.empty()){while(!pushst.empty()){int x = pushst.top();popst.push(x);pushst.pop();}}int ret = popst.top();popst.pop();return ret;}int peek() {if(popst.empty()){while(!pushst.empty()){int x = pushst.top();popst.push(x);pushst.pop();}}int ret = popst.top();return ret;}bool empty() {return pushst.empty()&&popst.empty();}stack<int> pushst;stack<int> popst;};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

总结

通过对STL中stack的探讨，我们认识到它在解决特定问题时的便利性和高效性。stack类提供了简单易用的接口，使得数据的插入和删除操作更加直接。同时，我们也了解了其在实际应用中的价值，例如在算法中用于管理临时状态或数据。此外，结合实际示例和代码实现，读者可以看到如何灵活地将stack应用于自己的项目中。掌握stack的使用，将为解决更复杂的问题奠定坚实的基础。希望本文能帮助大家更深入地了解STL之stack，并在日常编程中熟练运用

---

完