两个队列实现栈
思路:
由于对于队列是先进先出的结构,但是栈是后入先出的结构,所以可以用两个队列实现栈。
1.入栈操作就是将元素入队列1
2.出栈操作就是需要将队列1中的除了最后一个元素外的其他元素都移动到队列2中
3.再将队列1中的最后一个元素出栈,将队列2中的元素放回队列1中
4.获得栈顶元素就是获得队列1的队尾元素
5.判断栈是否为空就是判断队列1和队列2是否都为空
代码:
class Solution {
public:
//将需要插入栈的元素插入队列1中即可
void push(int x){
q1.push(x);
}
//将栈顶元素出栈,需要将队列1中前面的除了最后一个元素都移动到队列2中
//再将队列1中的这个元素出队列1,就是出栈
//之后再将队列2中的元素移动回队列1
int pop(){
while(q1.size()>1){
q2.push(q1.front());
q1.pop();
}
int temp=q1.front();
q1.pop();
while(!q2.empty()){
q1.push(q2.front());
q2.pop();
}
return temp;
}
//栈顶元素就是队列1中的队尾元素
int top(){
return q1.back();
}
//只有当两个队列都为空的时候栈才是空
bool empty(){
return (q1.empty())&&(q2.empty());
}
private:
//定义两个STL中的队列queue,分别为q1和q2
//由于栈是后入先出的结构,如果只有一个队列只能实现元素存入栈中
//但是对于出栈操作,由于栈是后入先出,但是队列是先入先出,所以想在队列1中让最后一个元素先出去,就需要将队列1中前面的所有元素都先移动到队列2中,
//让最后一个元素从队列1中出栈,再把队列2中的元素放回队列1中
queue<int>q1;
queue<int>q2;
};