代码随想录二刷|栈与队列

基础理论

STL的版本

HP STL：第一个STL版本，开源

P.J.Plauger STL：被Visual C++编译器所采用，不是开源的

SGI STL：GCC使用，开源

栈（stack）

（1）栈不是容器，而是容器适配器

（2）这里的栈是SGI STL这个版本的STL里面的

（3）stack的实现：

stack是先进后出的数据结构，SGI STL中用deque实现，deque是双向队列，堵住一侧，打开另一侧就可以实现栈

（4）stack不允许有遍历行为，没有迭代器

队列（queue）

（1）队列不是容器，是容器适配器

（2）这里的队列是SGI STL这个版本的STL里面的

（3）queue的实现：

queue是先进先出的数据结构，SGI STL中用deque实现

（4）queue不允许有遍历行为，没有迭代器

用栈实现队列

题干

你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

思路

在输入的时候把元素放进s1，如果s2空了，就把s1元素放进s2，在s1中先入的元素会后入s2，弹出s2的栈顶就是弹出s1的先入元素

class MyQueue {
public:stack<int> s1;stack<int> s2;MyQueue() {}void push(int x) { s1.push(x); }int pop() {if (s2.empty()) {while (s1.size() > 0) {s2.push(s1.top());s1.pop();}}int res = s2.top();s2.pop();return res;}int peek() {int res = this->pop();s2.push(res);return res;}bool empty() {if (s1.size() == 0 && s2.size() == 0)return true;return false;}
};/*** 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();*/

用队列实现栈

题干

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

思路

将元素输入q1，顺组和栈是反的，在pop栈顶的时候，从q1中取出元素放进q2直到q1只剩下一个元素，弹出，再把q2放回q1；在获取栈顶的时候，从q1中取出元素放进q2直到q1只剩下一个元素，记录答案，把这个元素放进q2，再把q2放回q1

class MyStack {
public:queue<int> q1;queue<int> q2;MyStack() {}void push(int x) { q1.push(x); }int pop() {while (q1.size() > 1) {q2.push(q1.front());q1.pop();}int res = q1.front();q1.pop();while (!q2.empty()) {q1.push(q2.front());q2.pop();}return res;}int top() {while (q1.size() > 1) {q2.push(q1.front());q1.pop();}int res = q1.front();q1.pop();q2.push(res);while (!q2.empty()) {q1.push(q2.front());q2.pop();}return res;}bool empty() { return (q1.empty() && q2.empty()); }
};

理解：为什么用队列实现栈需要每次把q2清空，但是用栈实现队列可以保留s2，直到s2空了再把s1放进s2

有效的括号

题干

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路

因为后出现的括号先匹配，所以先进后出，用栈

class Solution {
public:bool isValid(string s) {stack<char>q;for (int i=0;i<s.size();i++){if(s[i]=='('||s[i]=='{'||s[i]=='['){q.push(s[i]);}else if(s[i]==')'){if(q.empty()||q.top()!='(')return false;else q.pop();}else if(s[i]=='}'){if(q.empty()||q.top()!='{')return false;else q.pop();}else {if(q.empty()||q.top()!='[')return false;else q.pop();}}if(q.empty())return true;return false;}
};

删除字符串当中的所有相邻重复项

题干

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

思路

后出现的字符要考虑是否要删掉，为了便于获取后出现的字符，用栈

class Solution {
public:string removeDuplicates(string s) {stack<char> x;for (int i = 0; i < s.size(); i++) {if (x.empty()) {x.push(s[i]);continue;}if (x.top() == s[i]) {while (!x.empty()&&x.top() == s[i]) {x.pop();}continue;}else{x.push(s[i]);}}stack<int >x2;while(!x.empty()){x2.push(x.top());x.pop();}string res;while(!x2.empty()){res.push_back(x2.top());x2.pop();}return res;}
};