题目链接
如果用两个栈来实现队列,那么可以用两个队列来实现栈吗
首先看入栈操作和入队是一样的,直接用
就是这个出栈,每次出栈的是队列里的最后一个元素,那么将前面的元素依次入到第二个队列,然后再将所剩的最后一个元素出栈,然后再把前面的元素再入栈,恢复原样
盗个卡哥的图
首先队列的STL的访问首部元素是和那个栈的是不一样的
根据队列的数据结构,队列有头尾指针,而栈只有top一个栈顶指针。
入队可以指定元素,出队只能出队头第一个元素这是队列的特征,当然栈也是这么回事
经验,在敲代码的时候,要在每一行想着这行代码实现的中文含义,以及不要忘了再回顾一下是否可以实现这个程序或者函数要求实现的功能,敲完了,再回顾一遍,对照着功能
class MyStack {
public:
queue<int>one;
queue<int>two;
MyStack() {
}
void push(int x) {
one.push(x);
}
int pop() {
int num=one.size();
while(--num){
two.push(one.front());
one.pop();
}
int res = one.front();
one.pop();
while(!two.empty()){
one.push(two.front());
two.pop();
}
return res;
}
int top() {
return one.back();
}
bool empty() {
return one.empty()&&two.empty();
}
};
然后就是卡哥提出了个优化,第二个队列就是用来存东西的,那么能不能把最后一个元素之前的所有元素都存到这个队列的后面,就是在这个队列的后面排队,这不就和用两个队列的操作其实是一回事?
class MyStack {
public:
queue<int>one;
MyStack() {
}
void push(int x) {
one.push(x);
}
int pop() {
int num=one.size();
while(--num){
one.push(one.front());
one.pop();
}
int res=one.front();
one.pop();
return res;
}
int top() {
return one.back();
}
bool empty() {
return one.empty();
}
};