数据结构与算法

用两个队列实现栈

略

题目：用两个队列来实现一个栈，完成栈的Push和Pop操作。 队列中的元素为int类型。

  本题目不属于《剑指offer》的题目，属于上次题目的拓展。上次使用两个栈实现了队列的入队和出队操作，那可不可以使用两个队列来实现一个栈的入栈和出栈操作呢？

分析

基本思想

  队列的特点是先入先出，而栈的特点是先入后出。如果要想让队列实现栈，就要考虑：当一组数据到队后，要去实现栈的输出，即是把队的最后一个元素输出，然而又要去考虑这个队其他不需要输出的数据要如何处理呢？这里就引入了第二个队列，可以把数据先放到第二个队列中，等到该输出的元素输出之后，再把数据重新放到第一个队列中。

升级

  对于上面的方法，可以看出有一个缺点，那就是需要频繁的把数据进行移动，那可不可以简化一下呢？答案是可以的，在上面的基础上，当数据出栈之后，需要把刚刚移动到队列2的数据移回队列1，此时队列2是作为一个中转站（要出库的货物被别的货物堵住门了，就把别的货物先放到中转站中，等要出库的出库了，再按照原来的摆放顺序放入）。

  但是，当数据出栈后，队列2中有数据，此时的队列2是否就像当初的队列1中存着未出栈的数据。我们可以把队列1和队列2的角色互换一下，具体描述如下：

  • 入栈：两个队列哪个不为空，就把数据入队到那个队列中去；如果都为空，比如选择队列1入队。
  • 出栈：把不为空的队列的数据除去最后一个想要输出的数据，其他数据全部出队然后移动到另外一个队列中去，然后把想要输出的数据输出。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
  
  	//两个队列
    ArrayQueue queue1 = new ArrayQueue();
  	ArrayQueue queue2 = new ArrayQueue();
    
  	//入栈
    public void push(int item) {
		if(queue2.isEmpty()){
          queue1.put(item);
		} else {
          queue2.put(item);
		}
    }
    
  	//出栈
    public int pop() {
		if(size() == 0){
          throw new IndexOutOfBoundsException("栈空了");
		} else {
          
          if(queue2.isEmpty()){//如果2是空的，就...
            
            while(queue1.size()>1){//把1中的除了最后一个元素，全部...
              queue2.put(queue1.poll());//放到2中，然后...
            }
            return queue1.poll();//出栈
            
          } else {				//如果2有数据，则...
            
            while(queue2.size()>1){//把2中除最后一个数据，全部...
              queue1.put(queue2.poll());//放到1中，然后...
            }
            return queue2.poll();//出栈
          }
          
		}
    }
  
  	//数据的总长度
  	public int size(){
      return queue1.size()+queue2.size();
  	}
}

总结

  1. 上节是两个栈实现队列，本次是两个队列实现栈，所以要学会举一反三。
  2. 要对程序运行的每个时刻高度警觉，当到达一个状态后，要思考是否和之前的状态类似，避免一些不必要的操作。
  3. 思考问题要全面，出栈（队）要思考栈（队）是否为空，入栈（队）要思考栈（队）是否已满。