stack
栈的特点是 先进后出(first in last out)
我们可以看出, stack的接口相比 vector/string/list 的接口少的太多了
- 构造函数 && 容器适配器
- 容器适配器的含义:
首先, 适配器 — — 用户传数据进来, 我们用合适的容器来进行管理
其次, 容器 — — 容器要符合类型的要求. 比如堆要求用下标来访问数据, 那么我们适配的容器就应该是vector, 而不应该是list
总结下来就是, 容器适配器是 外壳用容器封装, 数据由容器来进行管理
不支持下标访问数据, 不能进行遍历.
只能通过不断的 pop 来进行访问数据
int main() { stack<int> st; st.push(1); st.push(5); st.push(9); st.push(8); st.push(6); st.push(90); cout << "size->" << st.size() << endl; cout << "出数据->"; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; return 0; }
运行结果:
size->6 出数据->90 6 8 9 5 1
栈的知识也就这么多, 下面进入queue
queue
队列的特点是 先进先出 (first in first out)
跟stack很相似, 但是队列不仅有队头也有队尾, 而stack只有栈顶
- 我们发现, queue也使用的是
容器适配器 - 跟stack一样, 不支持下标访问数据, 不能进行遍历.
只能通过不断的pop来进行访问数据
int main() { queue<int> q; q.push(1); q.push(5); q.push(9); q.push(8); q.push(6); q.push(90); cout << "size->" << q.size() << endl; cout << "出数据->"; while (!q.empty()) { cout << q.front() << " "; q.pop(); } cout << endl; return 0; }
运行结果:
size->6 出数据->1 5 9 8 6 90
题目训练
- 最小栈
- 首先, 先想到的是定义一个全局变量 min, 在每次push 和 pop的时候更新一下min, 然后返回min就行了.
这么做是真的没问题吗? 看一下下面的例子:
push: 6, 5, 4, 3, pop两次
此时当前栈的最小值应该是5, 但是按照我们的想法, min应该是3才对
上面的那个想法不能很好地控制栈空间的变化
其实, 我们可以用两个栈来做: 一个负责正常工作, 一个负责记录当前栈的最小值
解题代码:
class MinStack { public: void push(int val) { st.push(val); // min_st进数据: 1. 首元素, 2.进入数据的元素 <= min_st的栈顶元素 if(min_st.size() == 0 || val <= min_st.top()) { min_st.push(val); } } void pop() { if(min_st.top() == st.top()) { min_st.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return min_st.top(); } private: stack<int> st; stack<int> min_st; };
解题代码:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> st; // 辅助栈 int pushi = 0; // 控制入栈数组 int popi = 0; // 控制出栈数组 // 当没数据可入了, 说明入栈结束 while(pushi < pushV.size()) { // 先入栈 st.push(pushV[pushi]); pushi++; // 防止st栈为空 while(st.size() && st.top() == popV[popi]) { st.pop(); popi++; } } return st.empty(); }
