工作内容
1、总结有关栈和队列的相关题型
2、总结coodsheep发布的算法题大集锦
3、看RT Huang的GitHub
剑指上有关栈的题目总结:1、用队列实现栈,2、栈实现队列 ,3、包含min函数的栈,4、 合法的出战序列
1、用队列实现栈
无论是两个队列还是一个队列去实现栈的功能,思路都是一样的,在压入当前数值时,先把队列内之前的元素要么移动到辅助队列里,压入元素后再移动回来。要么就是直接在一个队列里进行操作,即只保留最后一个压入元素,在尾部压入头部元素,再删除头部元素。
1.1 两个队列实现栈
class MyStack { public: queue<int> qi; //主队列 queue<int> qt; //辅助队列 MyStack() { } void push(int x) { while(qi.size()) { //将qi中的元素全部搬至qt qt.push(qi.front()); qi.pop(); } qi.push(x); //插入新元素 while(qt.size()) { //将qt中的元素全部搬回qi qi.push(qt.front()); qt.pop(); } } int pop() { int temp = qi.front(); qi.pop(); return temp; } int top() { return qi.front(); } bool empty() { return qi.empty(); } };
1.2 单队列实现栈
class MyStack { public: queue<int> q; //单队列 MyStack() { } void push(int x) { q.push(x); for(int i = 0; i < q.size() - 1; i ++) { //交换位置 q.push(q.front()); q.pop(); } } int pop() { int temp = q.front(); q.pop(); return temp; } int top() { return q.front(); } bool empty() { return q.empty(); } };
2、栈实现队列
class Solution { public: void push(int node) { stack1.push(node); } int pop() { int a; if(stack2.empty()){ while(!stack1.empty()){ a=stack1.top(); stack2.push(a); stack1.pop(); } } a=stack2.top(); stack2.pop(); return a; } private: stack<int> stack1; stack<int> stack2; };
3、包含min函数的栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
思路:1、设置一个压入栈,压入数值。设置一个辅助栈,保存最小值。2、弹出时,当压入栈和辅助栈的数相等时,同时弹出,否则压入栈弹出。因为相等时,即代表当前元素为最小值,如果弹出,则该最小值不再是当前值。
class MinStack { public: /** initialize your data structure here. */ MinStack() { } stack<int>s; stack<int>Min; void push(int x) { s.push(x); if(Min.empty()||x<=Min.top())Min.push(x); } void pop() { if(!s.empty()){ if(s.top()==Min.top())Min.pop(); s.pop(); } } int top() { return s.top(); } int getMin() { return Min.top(); } };
4、 合法的出战序列
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
思路:定义一个栈,向栈里添加第一个序列元素,直到与第二序列元素相等时,栈弹出,二序列往后移动一位。
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> p; int j = 0; //记录弹出序列的位置 for(int i = 0; i< pushed.size();i++) { p.push(pushed[i]); while(!p.empty() &&p.top() == popped[j] ) { p.pop(); j++; } } if(p.empty()) return true; return false; } };