leetcode算法刷题的第九天

今天是栈与队列

栈与队列的理论基础

1.原理大家应该都懂，队列是先进先出，栈是先进后出。

2.大家要知道，栈和队列都是STL（c++标准库）里面的两个数据结构。

3.HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。

4.P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。

5.SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

6.栈提供push和pop等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器，不像是set或者map提供迭代器iterator来遍历所有元素。

7.，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

8.队列中先进先出的数据结构吗，同样不允许有遍历行为，不提供迭代器，但是队列不被归为容器，而被归为容器适配器。

leetcode 232.用栈实现队列

题目链接

class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;

MyQueue() {

}

void push(int x) {
stIn.push(x);
}

int pop() {
//只有当stOut为空的时候，再从stIn里导入数据
if(stOut.empty()){
//从stIn导入数据知道stIn为空
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int result=stOut.top();
stOut.pop();
return result;
}

int peek() {
int result=this->pop();//直接调用pop函数
stOut.push(result);//因为pop函数弹出了元素，我们还要再添加回去
return result;
}

bool empty() {
return stIn.empty()&&stOut.empty();
}
};

/**
* 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();
*/

思路总结：这道题的关键在于我们如何用栈来实现队列的功能函数。其实就是用两个栈，一个输入栈，一个输出栈。在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的。如果进栈和出栈都为空的话，说明模拟的队列为空了。

leetcode 225.用队列实现栈

这道题大家可能会惯性思维，以为还要用两个队列来模拟栈，其实只要用一个队列就可以了。

并且这道题用一个队列来模拟也是比较简单的，甚至比用两个队列还简单。

题目链接

class MyStack {
public:
queue<int> que;
MyStack() {

}

void push(int x) {
que.push(x);//直接插入就好了
}

int pop() {
int size=que.size();
size–;
while(size–){//循环插入队列头部的数值
que.push(que.front());
que.pop();
}
int result=que.front();//这里只是取到了数值，但是还没弹出来
que.pop();//所以要弹出
return result;
}

int top() {
return que.back();//栈的头部其实就是队列的尾部，直接return就好了
}

bool empty() {
return que.empty();
}
};

/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/

思路总结：这道题的关键在于，要深刻理解栈和队列的底层实现原理，并且碰到这种数据结构的题目最好是能够自己画出一张图出来，这样更好理解。

leetcode 20.有效的括号

题目链接

括号匹配是用栈来解决的经典问题。由于栈的特殊性，非常适合做对称匹配类型的题目。

class Solution {
public:
bool isValid(string s) {
stack<int> st;
if(s.size()%2!=0) return false;//如果s的长度为奇数，一定不符合条件
for(int i=0;i<s.size();i++){
if(s[i]=='(') st.push(')');
else if(s[i]=='[') st.push(']');
else if(s[i]=='{') st.push('}');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if(st.empty()||st.top()!=s[i]) return false;
else st.pop();
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
if(st.empty()) return true;
else return false;
}
};

思路总结：以上代码中的注释中，有分别对应根据题意的三种条件，就是发现任意一种括号，就往栈里面插入对应的括号，然后遇到继续遍历字符串，遇到对应的括号，如果和栈里面顶部的括号相等，就pop出来，然后继续进行比较。技巧性的东西没有固定的学习方法，还是要多看多练，自己灵活运用了。

leetcode 1047.删除字符串中的所有相邻重复项

题目链接

这道题也是栈的经典应用。大概的意思有点像开心消消乐。

class Solution {
public:
string removeDuplicates(string s) {
stack<int> st;
for(int i=0;i<s.size();i++){
if(st.empty()||st.top()!=s[i]){
st.push(s[i]);
}
else{
st.pop();//s与st.top()相等的情况
}
}
string result="";
while(!st.empty()){//把栈中的元素放到result字符串中
result+=st.top();
st.pop();
}
reverse(result.begin(),result.end());//最后要把字符串反转一下
return result;
}
};

思路总结：大家如果有条件可以画个图，遇到这种数据结构的题目，一定要多画图，这样能够更好地理解，光凭空想的话很难想得到。思路就是先把字符串放到栈里面，然后看情况消消乐，其次再把栈的中元素拼成一个字符串，最后再把这个字符串反转一下就完成了。