stack

栈的特点是 先进后出(first in last out)

我们可以看出, stack的接口相比 vector/string/list 的接口少的太多了

1. 构造函数 && 容器适配器
   

• 容器适配器的含义:
  首先, 适配器 — — 用户传数据进来, 我们用合适的容器来进行管理
  其次, 容器 — — 容器要符合类型的要求. 比如堆要求用下标来访问数据, 那么我们适配的容器就应该是vector, 而不应该是list
  总结下来就是, 容器适配器是 外壳用容器封装, 数据由容器来进行管理

2. 不支持下标访问数据, 不能进行遍历.
   只能通过不断的 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只有栈顶

1. 我们发现, queue也使用的是 容器适配器
2. 跟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

题目训练

1. 最小栈

首先, 先想到的是定义一个全局变量 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;
};

2. 栈的压入, 弹出序列
   
   不绕弯子了: 本题属于 模拟题, 模拟压栈,出栈的顺序来做的. 由此需要一个辅助栈来进行, 最后判断辅助栈是否为空就知道答案了!

思路:

1. 不管什么, 先进栈 st
2. 再判断栈顶元素是否和出栈数组的当前值相同
   1. 不相同, 什么事情也不用做, 继续入栈
   2. 相同, st出栈, 出栈数组向前挪动数据, 直至和栈顶元素不相同
3. 结果: 看st是否为空
   1. 为空, 说明按照入栈, 出栈的顺序走了一遍, 说明逻辑是通的
   2. 不为空, 说明中间出现了问题, 说明逻辑是错误的

解题代码:

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();
}

---

2、知而不行，只是未知。
语出明·王守仁《传习录》。学了知识，而不实践，这等于没有学到知识一样。