【C++】STL--stack
【C++】STL--stack
1. stack的介绍
stack的文档介绍
后进先出（LIFO）：Stack容器遵循后进先出的原则，即最后进入栈的元素最先被移出栈。
2.stack的使用
常用的几个接口
代码演示如下
int main()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
cout << st.size() << endl;
cout << st.top() << endl;
st.pop();
cout << st.top() << endl;
cout << st.empty() << endl;
return 0;
}
3.stack的模拟实现
从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。
#pragma once
#include <deque>
namespace xc
{
template <class T,class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
const T& top()const
{
return _con.back();
}
void pop()
{
_con.pop_back();
}
size_t size()const
{
return _con.size();
}
bool empty()const
{
return _con.empty();
}
private:
Container _con;
};
}4.OJ练习题
4.1最小栈
题目链接：最小栈
题目描述：
思路：题目要求我们在常数时间内检索到最小元素的栈，所以遍历一遍找肯定不行，我们可以用两个栈，一个栈用来模拟出栈入栈(_st)一个用来存放最小值(_minst)，大概思路就是先插入一个数据然后让入栈元素和_minst的栈顶元素进行比较如果_minst为空或者入栈元素小于等于_minst就push到最小栈也就是_minst，出栈时如果_st的出栈元素等于_minst则_minst就出栈。
参考代码
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty() || val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
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;
};
/**
* 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然后将入栈数据依次push进去，push一个元素我们就拿它和出栈序列比较如果相等我们就将st里面的元素pop掉直到st为空或者不相等，然后继续push以此内推直至入栈元素全push进去了，最后判断st是否为空，为空就匹配上了返回true。
参考代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
stack<int> st;
size_t popi = 0;
for(auto e:pushV)
{
st.push(e);
while(!st.empty() && st.top() == popV[popi])
{
++popi;
st.pop();
}
}
return st.empty();
}
};4.3 用栈实现队列
题目链接：用栈实现队列
题目描述：
思路：栈是后进先出，那么我们可以创建两个栈来实现一个队列，一个插入数据一个用来导数据，当我们要出栈时我们就把栈数据导到入到不为空的那个栈，比如1234我们要取出1就把数据导一下变成4321然后进取栈顶数据即可
参考代码
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
st1.push(x);
}
int pop() {
while(st2.empty())
{
while(!st1.empty())
{
int x = st1.top();
st1.pop();
st2.push(x);
}
}
int x = st2.top();
st2.pop();
return x;
}
int peek() {
while(st2.empty())
{
while(!st1.empty())
{
int x = st1.top();
st1.pop();
st2.push(x);
}
}
return st2.top();
}
bool empty() {
return st1.empty() && st2.empty();
}
private:
stack<int> st1;
stack<int> st2;
};
/**
* 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();
*/总结
C++ STL中的stack是一种非常有用的容器适配器，它提供了简单而高效的后进先出数据结构。通过封装特定的容器类，stack能够灵活地适应不同的应用场景。虽然stack的访问受限，但这正是其设计初衷的一部分，以确保数据的正确性和安全性。因此，在需要后进先出数据结构的场景中，stack是一个非常好的选择。
腾讯云开发者
