232. 用栈实现队列
题目链接：
https://leetcode.cn/problems/implement-queue-using-stacks/
思路：
准备两个栈，一个作为入栈，一个作为出栈。
入栈只存放新增的元素
出栈负责弹窗队首元素。
push操作：把所有的元素的放在入栈中，在栈顶添加元素
pop操作：把所有元素放在出栈中，在栈顶弹出元素。
empty操作：当两个栈都为空时，返回true，否则返回false
代码：
class MyQueue {
private:
stack<int> startin;
stack<int> startout;
public:
MyQueue() {
}
void push(int x) {
while(!startout.empty())
{
int val = startout.top();
startout.pop();
startin.push(val);
}
startin.push(x);
}
int pop() {
while(!startin.empty())
{
int val = startin.top();
startin.pop();
startout.push(val);
}
if(startout.empty())
return -1;
int top = startout.top();
startout.pop();
return top;
}
int peek() {
int val = pop();
startout.push(val);
return val;
}
bool empty() {
if(!startin.empty()||!startout.empty())
return false;
else
return true;
}
};
/**
* 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. 用队列实现栈
题目链接：
https://leetcode.cn/problems/implement-stack-using-queues/
思路：和用栈实现队列不通，这题队列2是作为队列1的备份使用。
优化：可以用一个队列实现栈。要弹出栈顶元素，只要把队列首元素放到队尾，取到最后一个即可。
class MyStack {
queue<int> qin;
queue<int> qout;
int size;
public:
MyStack() {
size = 0;
}
void push(int x) {
qin.push(x);
cout<<"size:"<<size<<endl;
size++;
}
int pop() {
cout<<"in pop"<<endl;
int new_size = size;
new_size--;
while(new_size!=0)
{
int front = qin.front();
cout<<"front:"<<front<<endl;
qout.push(front);
qin.pop();
new_size--;
}
int top = qin.front();
qin.pop();
while(!qout.empty())
{
int front = qout.front();
qin.push(front);
qout.pop();
}
size--;
cout<<"size:"<<size<<endl;
return top;
}
int top() {
cout<<"int top"<<endl;
int new_size = size;
new_size--;
while(new_size!=0)
{
int front = qin.front();
cout<<"front:"<<front<<endl;
qout.push(front);
qin.pop();
new_size--;
}
int top = qin.front();
qin.pop();
cout<<"top:"<<top<<endl;
// qin.pop();
qout.push(top);
cout<<"====reset===="<<endl;
while(!qout.empty())
{
int front = qout.front();
cout<<"front:"<<front<<endl;
qin.push(front);
qout.pop();
}
cout<<"qin.size"<<qin.size()<<endl;
cout<<"qin.front"<<qin.front()<<endl;
cout<<"qin.back"<<qin.back()<<endl;
return top;
}
bool empty() {
if(qin.empty())
return true;
else
return false;
}
};
/**
* 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();
*/
优化版本：
class MyStack {
public:
queue<int> queue1;
queue<int> queue2;
MyStack() {
}
void push(int x) {
queue1.push(x);
}
int pop() {
int size = queue1.size();
size--;
while(size>0)
{
queue1.push(queue1.front());
queue1.pop();
size--;
}
int top = queue1.front();
queue1.pop();
return top;
}
int top() {
int top = pop();
queue1.push(top);
return top;
}
bool empty() {
if(queue1.empty())
return true;
else
return false;
}
};
/**
* 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();
*/
