刷题记录
232. 用栈实现队列
考察栈与队列之间的特性。
栈：后进先出（先进后出）——FILO。
队列：先进先出——FIFO。
所以使用两个栈模拟队列，分别为in和out。当入队新元素时将其压入in栈。当需要对队头元素操作时（peek/pop），从out栈中取栈顶元素。当out栈为空时，则将in栈中的元素全部存入out栈。
时间复杂度： push：
O
(
1
)
O(1)
O(1)；pop：
O
(
n
)
O(n)
O(n)；peek：
O
(
n
)
O(n)
O(n)；empty：
O
(
1
)
O(1)
O(1)；
空间复杂度：
O
(
n
)
O(n)
O(n)
// c++
class MyQueue {
public:
stack<int> in;
stack<int> out;
MyQueue() {
}
void push(int x) {
in.push(x);
}
int pop() {
if(out.empty()){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
int res = out.top();
out.pop();
return res;
}
int peek() {
int res = pop();
out.push(res);
return res;
}
bool empty() {
return in.empty() && out.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();
*/
225. 用队列实现栈
同上题类似。
使用两个队列模拟栈，分别为qu和tmp。入栈新元素压入qu，当需要操作栈顶元素时，获取qu的长度size，将qu中的前size-1个元素挪入tmp，剩余一个元素即为栈顶元素，操作结束过后再将tmp中的元素挪回qu。
时间复杂度： push：
O
(
1
)
O(1)
O(1)；pop：
O
(
n
)
O(n)
O(n)；peek：
O
(
1
)
O(1)
O(1)；empty：
O
(
1
)
O(1)
O(1)；
空间复杂度：
O
(
n
)
O(n)
O(n)
// c++
class MyStack {
public:
queue<int> qu;
queue<int> tmp;
MyStack() {
}
void push(int x) {
qu.push(x);
}
int pop() {
int len = qu.size();
while(len > 1){
tmp.push(qu.front());
qu.pop();
len--;
}
int res = qu.front();
qu.pop();
while(!tmp.empty()){
qu.push(tmp.front());
tmp.pop();
}
return res;
}
int top() {
return qu.back();
}
bool empty() {
return qu.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();
*/
20. 有效的括号
左括号压入栈，右括号与栈顶元素进行匹配，若匹配成功，弹出栈顶元素，反之返回pop。
一些小细节需要处理：
- 当前面没有左括号或者左括号都匹配完毕（栈为空），此时输入一个右括号进行匹配直接取栈顶元素会出异常。需要返回false。
- 当输入字符串中只有左括号没有右括号或左括号未完全匹配时，遍历结束后栈中会剩余未匹配的左括号。需要返回false。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
// c++
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0; i<s.size(); i++){
if(s[i]=='(' || s[i]=='{' || s[i]=='[') st.push(s[i]);
else{
if(st.empty()) return false;
if(s[i]==')' && st.top()=='(') st.pop();
else if(s[i]=='}' && st.top()=='{') st.pop();
else if(s[i]==']' && st.top()=='[') st.pop();
else return false;
}
}
if(!st.empty()) return false;
return true;
}
};
1047. 删除字符串中的所有相邻重复项
题目描述类似于祖玛游戏，相邻元素相同则删除。遍历字符串，借助栈来存储前面访问过的元素，若栈顶元素也就是前一个访问的元素与当前元素相同，遍历的指针后移，栈顶元素弹出。反之则将元素压入栈中。
Tips： 字符串也可用作栈，入栈push_back()，出栈pop_back()。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
n
)
O(n)
O(n)
// c++
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i=0; i<s.size(); i++){
if(!st.empty() && st.top()==s[i]) st.pop();
else st.push(s[i]);
}
int i=st.size();
s.resize(i);
while(i--){
s[i] = st.top();
st.pop();
}
return s;
}
};