用2个栈实现一个队列：
转的一篇文章：
大多数人的思路是：始终维护s1作为存储空间，以s2作为临时缓冲区。
入队时，将元素压入s1。
出队时，将s1的元素逐个“倒入”（弹出并压入）s2，将s2的顶元素弹出作为出队元素，之后再将s2剩下的元素逐个“倒回”s1。
见下面示意图：
上述思路，可行性毋庸置疑。但有一个细节是可以优化一下的。即：在出队时，将s1的元素逐个“倒入”s2时，原在s1栈底的元素，不用“倒入”s2（即只“倒”s1.Count()-1个），可直接弹出作为出队元素返回。这样可以减少一次压栈的操作。约有一半人，经提示后能意识到此问题。
上述思路，有些变种，如：
入队时，先判断s1是否为空，如不为空，说明所有元素都在s1，此时将入队元素直接压入s1；如为空，要将s2的元素逐个“倒回”s1，再压入入队元素。
出队时，先判断s2是否为空，如不为空，直接弹出s2的顶元素并出队；如为空，将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
有些人能同时想到大众方法和变种，应该说头脑还是比较灵光的。
相对于第一种方法，变种的s2好像比较“懒”，每次出队后，并不将元素“倒回”s1，如果赶上下次还是出队操作，效率会高一些，但下次如果是入队操作，效率不如第一种方法。我有时会让面试者分析比较不同方法的性能。我感觉（没做深入研究），入队、出队操作随机分布时，上述两种方法总体上时间复杂度和空间复杂度应该相差无几（无非多个少个判断）。
真正性能较高的，其实是另一个变种。即：
入队时，将元素压入s1。
出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。
这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次。但在实际面试中很少有人说出，可能是时间较少的缘故吧。
以上几个思路乍看没什么问题了，但其实还是有个细节要考虑的。其实无论什么方法和情况，都要考虑没有元素可供出队时的处理（2个栈都为空的时候，出队操作一定会引起异常）。在实际写代码时，忽略这些判断或异常处理，程序会出现问题。所以，能不能考虑到这些细节，也体现了个人的素养。
个人感觉，这道题确实有助于我鉴别应聘的人。但对于面试，毕竟还是要看面试者的综合素质，一道（或几道）题定生死不可取。
#include<iostream> #include<stack> #include<queue> using namespace std; #define MAX 100 template<class T> class Stack { private: T data[MAX]; int top;//有些书top指向的是栈顶，有些书是栈顶元素+1,这里是栈顶+1 public: Stack(){top=0;} bool empty(){ return top==0;} int size() { return top; } void push(T x) { data[top++]=x;} T pop() { int tmp=data[--top]; data[top]=0;return tmp;} }; template<class T> class Queue { private: Stack<T> s1;//可以使用的stack操作有push,pop和stack的元素个数 Stack<T> s2; public: void put(T x) { s1.push(x); } T get() { if(s2.size()!=0) { return s2.pop(); } else { int size=s1.size(); for(int i=1;i<=size-1;i++) { s2.push(s1.pop()); } return s1.pop(); } } }; int main() { Stack<int> s; s.push(1); s.push(2); cout<<s.pop()<<endl; Queue<int> q; for(int i=0;i<5;i++) q.put(i); for(int i=0;i<4;i++) cout<<q.get()<<ends; cout<<endl; q.put(10); cout<<q.get()<<endl; cout<<q.get(); }
输出：
2
0 1 2 3
4
10
遇到的一个很奇怪的问题是：
cout<<q.get()<<“ ”<<q.get()<<endl;
输出10 4
为什么？
是因为cout
cout的输出顺序有如下规律：
计算顺序：自右至左
输出顺序：自左至右、
写成：
cout<<q.get()<<“ ”<<q.get()<<endl;
先计算右边：q.get()为4，然后左边q.get() 10,输出10,4导致错误。
2个队列实现栈；
队列的特点：FIFO(First In First Out) 仅能从队头删除元素，从队尾插入元素。 最基本的接口包括enque()——从队尾插入元素, deque()——从队头删除元素 1.用两个栈实现队列 思路： 新入队列的元素压入stack1中，当元素出队列时，若stack2为空，则将stack1的全部元素依次弹出，压入stack2中，这样stack2的栈顶元素即为队头元素。 [cpp] template<typename T> class MyQueue { public: T front(); T back(); void enque(const T& ele); void deque(); private: void move(std::stack<T>& from, std::stack<T>& to); private: std::stack<T> stack1; std::stack<T> stack2; }; template<typename T> void MyQueue<T>::move(std::stack<T>& from, std::stack<T>& to) { if (to.empty()) { while (!from.empty()) { to.push(from.top()); from.pop(); } } } template<typename T> T MyQueue<T>::front() { T ele; move(stack1, stack2); if (!stack2.empty()) { ele = stack2.top(); } return ele; } template<typename T> T MyQueue<T>::back() { T ele; move(stack2, stack1); if (!stack1.empty()) { ele = stack1.top(); } return ele; } template<typename T> void MyQueue<T>::enque(const T& ele) { stack1.push(ele); } template<typename T> void MyQueue<T>::deque() { move(stack1, stack2); if (!stack2.empty()) { stack2.pop(); } } 2.用两个队列实现栈 思路： 新元素入栈时，若两个队列都为空，向任意一个队列队尾插入元素，否则向其中一个非空队列插入元素。栈弹出元素时，将非空队列的元素依次删除， 插入另一个空队列，只留下队尾元素(此即栈顶元素)，弹出栈顶即从队列中删除此元素。
CLRS 10.1-7 :
说明如何用两个队列来实现一个栈，并分析有关栈操作的运行时间。
解法：
1.有两个队列q1和q2，先往q1内插入a，b，c，这做的都是栈的push操作。
2.现在要做pop操作，即要得到c，这时可以将q1中的a,b两个元素全部dequeue并存入q2中，这时q2中元素为a，b，对q1再做一次dequeue操作即可得到c。
3.如果继续做push操作，比如插入d，f，则把d，f插入到q2中，
4.此时若要做pop操作，则做步骤2
5.以此类推，就实现了用两个队列来实现一个栈的目的。
注意在此过程中，新push进来的元素总是插入到非空队列中，空队列则用来保存pop操作之后的那些元素，那么此时空队列不为空了，原来的非空队列变为空了，总是这样循环。
对于push和pop操作，其时间为O(n).
[cpp] template<typename T> class MyStack { public: T top(); void push(const T& ele); void pop(); private: std::queue<T> queue1; std::queue<T> queue2; }; template<typename T> T MyStack<T>::top() { T ele; if (queue1.empty() && !queue2.empty()) { ele = queue2.back(); } else if (!queue1.empty() && queue2.empty()) { ele = queue1.back(); } return ele; } template<typename T> void MyStack<T>::push(const T& ele) { if (queue1.empty()) { queue2.push(ele); } else if (queue2.empty()) { queue1.push(ele); } } template<typename T> void MyStack<T>::pop() { if (queue1.empty()) { while(queue2.size() > 1) { queue1.push(queue2.front()); queue2.pop(); } if (!queue2.empty()) { queue2.pop(); } } else if (queue2.empty()) { www.2cto.com while(queue1.size() > 1) { queue2.push(queue1.front()); queue1.pop(); } if (!queue1.empty()) { queue1.pop(); } } }
转】用两个队列来实现一个栈--算法导论10.1-7
用一个队列就可以实现栈的基本操作
s.push(x)操作，直接将该元素压入队列即可，花费时间O(1),
pop()操作，将q中前面n-1个元素都删除并压入队尾，让第n的元素在队首，删除即可，花费时间O(n)。
int t = (q.GetTail()-1+q.GetSize())%q.GetSize();
while( q.GetHead()!=t)
{
q.EnQueue(q.DeQueue()) ;
}
return q.DeQueue() ;
如果用两个队列应该对减少pop（）操作的复杂度，但是还没想出具体方法，发在这里和大家讨论吧。
可能题目本意是不允许调用：GetTail(),GetSize()的，这样
只能：
int x ; // 栈顶元素 int num = 0 ; // 统计队列中原有元素的数量 while(!q1.IsEmpty()) { x = q1.DeQueue() ; num++ ; q2.EnQueue(x) ; } while( num > 0) { q1.EnQueue(q2.DeQueue()) ; // 将q2中前n-1个元素传给q1 } return x ;