用两个队列实现栈
用队列实现栈的核心,就是让新加入队列的的元素,不在放置队尾,将其位置放置队头
这样就可保证栈后进先出的性质
思路
同两个栈实现队列。用两个队列来回倒腾,满足先进先出
push操作
将新加入的元素A放入q中(此时q中只有一个元素,在放之前q为空,其他的元素都在cache中放着)
然后将cache中的元素全部放入q中(从chche出队后直接入到q队中)
此时新加入的元素A就在对头,如果要pop操作直接出队即可。
然后再将q中的元素全部转移到cache中。
目的就是保持q为空,方便下次有元素入队时,它在队中处于第一个元素的位置上
这里就有两种写法
trans(q,cache);将q中的元素全部转移到cache中——q变成空了
swap(q,cache);直接交换q和cache——交换前cache为空,q是满的,换一下q成功
pop操作和top操作
直接将cache中的对头返回即可
pop记得要将cache中的对头弹出
top则不用
empty
直接看cache.empty()的返回值即可
class MyStack {
public:
queue<int> q,cache;
MyStack() {
}
void trans(queue<int> &a,queue<int> &b)
{
while(a.size())
{
b.push(a. front());
a.pop();
}
}
void push(int x) {
q.push(x);
trans(cache,q);
// trans(q,cache);
//上面两个trans一起运行是x入队后,将cache中的元素全部转移到q中,然后在转移回cache
//相当于是去q中吧新加入的元素x接回去
swap(q,cache);
}
int pop() {
int ans=cache. front();
cache.pop();
return ans;
}
int top() {
int ans=cache. front();
return ans;
}
bool empty() {
return cache.empty();
}
};
/**
* 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();
*/
用一个队列实现
push操作
当新元素A入队后,对中一共有n+1个元素。
让前n个元素出队在入队就和重新排到A后面,形成出队为栈的序列。
class MyStack {
public:
stack<int> q;
MyStack() {
}
void push(int x) {
int n=q.size();
q.push(x);
for(int i=0;i<n;i++)
{
q.push(q.top());
q.pop();
}
}
int pop() {
int t=q.top();
q.pop();
return t;
}
int top() {
return q.top();
}
bool empty() {
return q.empty();
}
};
/**
* 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();
*/