232.用栈实现队列
1.使用两个栈（修改输出）
思路
1.使用两个栈，用一个栈输入数据，用另一个栈输出数据
2.当输出栈为空时，将输入栈的数据转移到输出栈中
实现
点击查看代码
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
stack1.push(x);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){//将栈1的元素放入栈2
stack2.push(stack1.top());
stack1.pop();
}
}
int result = stack2.top();//取出栈2的栈顶元素
stack2.pop();
return result;
}
int peek() {
int result = this->pop();
stack2.push(result);
return result;
}
bool empty() {
return stack1.empty() && stack2.empty();
}
private:
stack<int> stack1;
stack<int> stack2;
};
复杂度分析
- 入栈时间复杂度：O(1)
- 入栈空间复杂度：O(n)
- 出栈时间复杂度：O(1),均摊复杂度，每个数据只用进一次输出栈，出一次输出栈。
- 出栈空间复杂度：O(1)
2.倒序入栈（修改输入）
思路
1.入栈时先将栈1所有元素存入栈2，将元素存入栈1，在将栈2内的所有元素存入栈1
2.出栈只用出栈顶元素
实现
点击查看代码
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
stack1.push(x);
while(!stack2.empty()){
stack1.push(stack2.top());
stack2.pop();
}
}
int pop() {
int x = stack1.top();
stack1.pop();
return x;
}
int peek() {
return stack1.top();
}
bool empty() {
return stack1.empty();
}
private:
stack<int> stack1;
stack<int> stack2;
};
复杂度分析
- 入栈时间复杂度：O(n)
- 入栈空间复杂度：O(n)
- 出栈时间复杂度：O(1)
- 出栈空间复杂度：O(1)
225.队列实现栈
1.修改输入
思路
1.将新元素输入到队列2
2.将队列1中的全部元素输入到队列2
3.交换队列1和队列2
实现
点击查看代码
class MyStack {
public:
MyStack() {
}
void push(int x) {
que2.push(x);
while(!que1.empty()){
que2.push(que1.front());
que1.pop();
}
swap(que1,que2);
}
int pop() {
int x = que1.front();
que1.pop();
return x;
}
int top() {
return que1.front();
}
bool empty() {
return que1.empty();
}
private:
queue<int> que1;
queue<int> que2;
};
复杂度分析
- 入队列时间复杂度：O(n)
- 入队列空间复杂度：O(n)
- 出队列时间复杂度：O(1)
- 出队列空间复杂度：O(1)
2.修改输出（一个队列）
思路
遍历一个队列，将队头元素加入到队尾，直到最后一个元素
实现
点击查看代码
class MyStack {
public:
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size()-1;
while(size--){
que.push(que.front());
que.pop();
}
int x = que.front();
que.pop();
return x;
}
int top() {
int x = this-> pop();
que.push(x);
return x;
}
bool empty() {
return que.empty();
}
private:
queue<int> que;
};
/**
* 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();
*/
复杂度分析
- 入队列时间复杂度：O(1)
- 入队列空间复杂度：O(n)
- 出队列时间复杂度：O(n)
- 出队列空间复杂度：O(1)
20.有效的括号
思路
1.对字符串进行遍历
2.如果字符与栈首元素配对，则弹出栈首元素。否则将该字符入栈。
实现
点击查看代码
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i = 0; i < s.size(); i++){
if(st.empty()) st.push(s[i]);
else if(st.top() == '(' && s[i] == ')')st.pop();
else if(st.top() == '[' && s[i] == ']')st.pop();
else if(st.top() == '{' && s[i] == '}')st.pop();
else{
st.push(s[i]);
}
}
return st.empty();
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
1047. 删除字符串中的所有相邻重复项
思路
1.遍历字符串
2.对比字符和栈顶元素，如果相等，弹出栈顶元素，如果不相等，将字符入栈
3.将栈中元素输入新字符串中
4.翻转新字符串
实现
点击查看代码
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i = 0; i < s.size(); i++){
if(st.empty()) st.push(s[i]);
else if(st.top() == s[i]) st.pop();
else{
st.push(s[i]);
}
}
string m(st.size(),0);
int stSize = st.size();
for(int i = 0; i < stSize; i++){
m[i] = st.top();
st.pop();
}
reverse(m.begin(),m.end());
return m;
}
};
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)