数据结构与算法

用两个栈实现队列

略

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

分析

  栈是一种常见的数据结构，特点是先入栈的后出栈，后入栈的先出栈，类似堆叠的货物。而队列与它相反，特点是先入队的最先出队，后入队的后出队，类似于排队买票。

  题目中要求用两个先进后出的栈实现一个先进先出的队列，根据栈的特点，可以实现倒序输出一串数据，而两个栈，把一组数据倒序两次，负负得正，就可以实现先进先出的队列了，基本的实现是，入队时，把数据放到栈A中，出队时，先把栈A中的数据依次出栈并依次放到栈B中，此时B再出栈就实现队列了（为了保证数据顺序正确性，当A栈向B栈放入数据时，必须保证栈B是空的，）。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
  	//入队
    public void push(int node) {
        stack1.push(node);
    }
    
  	//出队
    public int pop() {
        if(stack2.empty()){	//如果栈2是空的就从1中转移数据，否则直接从2中输出
           while(!stack1.empty()){	//必须保证栈1是空的，否则会出现顺序出错
           		stack2.push(stack1.pop());
        }
        }
        return stack2.pop();
    }
}

总结

  1. 要注意思考验证一下，应该出栈的数据会不会被其他事件所影响。我的一次错误是：在入队操作时就同时把数据从栈A到栈B，然后出队时不把数据出完，再去入队，就会发生错误。所以应该入队时把数据放到栈A，出队时再进行栈栈间的数据转移，这样就不会导致反复进出队而发生的错误了。
  2. 栈的使用场景：
  1. 逆序输出
  2. 语法检查（符号的成对出现）
  3. 数制转换（10进制转换为8进制，使用短除法，取得的余数最后需要倒着输出，相当与逆序输出）