法1:《剑指》的思路
代码: C++算法之 两个队列实现一个栈
法2:更加简单
思路:
在实现时使得栈顶等于队列头;
由于栈的pop弹出栈顶元素,而队列的pop也是弹出栈顶元素,所以我们需要特别处理的是插入操作。
由于往栈中添加元素相当于往队列头添加元素,因此我们需要在两个队列中进行元素的转移,比较简单的实现是:
1.q1和q2在任一时刻至少有一个为空,即如果有元素,所以元素只在同一个队列中。
2.当有元素需要插入时,将插入的元素插入到空的队列中,并将另一非空队列的元素转移到该队列中,于是插入的元素添加到了队列头中。
代码: 使用两个队列实现一个栈