栈与队列理论基础
栈和队列是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（底层容器可替换）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
我们常用的SGI STL（gcc所使用的stl库）默认是以deque为缺省情况下栈的底层结构。
1
2
3
| std::stack<int> third;
std::stack<int, std::vector<int> > third;
std::queue<int, std::list<int>> third;
|
1、232用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空，返回 true ；否则，返回 false
我的思路： 好吧。没做出来。
代码随想录： 用两个栈一个进另一个再转进去弹出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class MyQueue {
stack<int> in;
stack<int> out;
public:
MyQueue() {
}
void push(int x) {
in.push(x);
}
int pop() {
int top = peek();
out.pop();
return top;
}
int peek() {
if(out.empty()){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
return out.top();
}
bool empty() {
return in.empty()&&out.empty();
}
};
|
2、225用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
我的思路： 还是没做出来。。
代码随想录： 使用一个队列就可以完成。一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class MyStack {
queue<int> q;
public:
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
int i = 1;
while(i++ < q.size()){
q.push(q.front());
q.pop();
}
auto temp = q.front();
q.pop();
return temp;
}
int top() {
int i = 1;
while(i++ < q.size()){
q.push(q.front());
q.pop();
}
auto temp = q.front();
q.push(q.front());
q.pop();
return temp;
}
bool empty() {
return q.empty();
}
};
|
3、20有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
我的思路： 这道题比较简单，依次符号入栈，然后下一个符号如果能和栈顶匹配就消去，和消消乐一样。但是问题是–要不是这节课学的就是栈，我可能想不到用栈去做。笔试时怎么办？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
bool isValid(string s) {
stack<char> sta;
int i = 0;
while(i < s.size()){
if(sta.empty()){
sta.push(s[i]);
}else{
if(sta.top()=='(' && s[i]==')'){
sta.pop();
}else if(sta.top()=='[' && s[i]==']'){
sta.pop();
}else if(sta.top()=='{' && s[i]=='}'){
sta.pop();
}else{
sta.push(s[i]);
}
}
i++;
}
if(sta.empty()){
return true;
}
return false;
}
};
|
4、1047删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
我的思路： 和上一题20有效的括号一样，也是找到同类元素消除。开心消消乐。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
string removeDuplicates(string s) {
int i = 0;
stack<char> sta;
while(i<s.size()){
if(sta.empty()){
sta.push(s[i]);
}else{
if(sta.top()==s[i]){
sta.pop();
}else{
sta.push(s[i]);
}
}
i++;
}
string res;
while(!sta.empty()){
res+=sta.top();
sta.pop();
}
reverse(res.begin(),res.end());
return res;
}
};
|
代码随想录算法训练第十天|232用栈实现队列|225用队列实现栈|20有效的括号|1047删除字符串中的所有相邻重复项
