用栈模拟实现队列和用队列模拟实现栈
用栈模拟实现队列
题目描述
从题目的声明中可以看出，一个队列包含了两个栈，stack1和stack2，所以说，这道题目的意图其实是让我们操作两个先进后出的栈实现一个先进先出的队列我们可以通过举例子来分析往队列中插入和删除元素的过程，首先插入一个元素a，把它插入到第一个栈里面，此时第一个栈里面的元素有一个a，第二栈是空的，然后我们再继续压入两个元素b和c元素，依旧是插入到第一个栈里面，那么，现在第一个栈里面就有元素a,b,c了，其中c位于栈顶，此时，第二个栈仍然是空的，那么这个时候，我们试着去删除一个元素，因为a是最开始被插入的，那么在我们删除元素的时候，a也应该是第一个被删除的，但是a并不是处在栈顶的位置的，所以我们需要将第一个栈的全部元素全都入到第二个栈里面，那么，这个时候，第二个栈的栈顶元素就是a元素的，如果想要继续删除元素的话，也是可以的，此时b位于第二个栈的栈顶元素，直接删除掉第二个栈的栈顶元素就可以了。经过分析，我们可以得知，删除元素的步骤为，如果第二个栈不为空的时候，第二个栈的栈顶元素就是最开始入队列的元素，可以直接弹出，当第二个栈为空的时候，先把第一个栈里面的元素，全部入到第二个栈里面，然后使用同样的方法进行操作。如果想要获取到对头元素的话，对头元素其实就是第二个栈的栈顶元素
代码如下所示：
牛客上
class Solution
{
public:
void push(int node
)
{
stack1
.push(node
);
}
int pop()
{
if(stack2
.empty())
{
while(!stack1
.empty())
{
stack2
.push(stack1
.top());
stack1
.pop();
}
}
if(stack2
.empty())
return -1;
int ret
=stack2
.top();
stack2
.pop();
return ret
;
}
private:
stack
<int> stack1
;
stack
<int> stack2
;
};
leetcode上
class MyQueue {
private:
stack
<int> st1
;
stack
<int> st2
;
public:
MyQueue()
{
}
void push(int x
)
{
while(!st2
.empty())
{
st1
.push(st2
.top());
st2
.pop();
}
st1
.push(x
);
}
int pop()
{
while(!st1
.empty())
{
st2
.push(st1
.top());
st1
.pop();
}
int ans
= st2
.top();
st2
.pop();
return ans
;
}
int peek() {
while(!st1
.empty())
{
st2
.push(st1
.top());
st1
.pop();
}
return st2
.top();
}
bool empty()
{
if(st1
.empty() && st2
.empty())
return true;
else
return false;
}
};
测试用例
往空的队列里面添加，删除元素往非空的队列里面添加，删除元素连续删除元素直到队列为空
用队列模拟实现栈
题目描述
代码如下所示：
class MyStack {
public:
queue
<int> q1
;
queue
<int> q2
;
MyStack()
{
}
void push(int x
)
{
if(q1
.empty())
q2
.push(x
);
if(q2
.empty())
q1
.push(x
);
}
int pop()
{
int t
;
if(q1
.empty())
{
if(q2
.size()==1)
{
t
=q2
.front();
q2
.pop();
return t
;
}
else
{
while(q2
.size()>1)
{
q1
.push(q2
.front());
q2
.pop();
}
t
=q2
.front();
q2
.pop();
return t
;
}
}
else
{
if(q1
.size()==1)
{
t
=q1
.front();
q1
.pop();
return t
;
}
else
{
while(q1
.size()>1)
{
q2
.push(q1
.front());
q1
.pop();
}
t
=q1
.front();
q1
.pop();
return t
;
}
}
}
int top()
{
if(q1
.empty())
return q2
.back();
else
return q1
.back();
}
bool empty()
{
return q1
.empty()&&q2
.empty();
}
};
