剑指offer：用两个栈实现队列

发表于 | 分类于

前言

　　栈和队列是非常常见的数据结构。栈先进后出，队列先进先出，Java中有定义好的栈和队列数据结构。要熟悉源码。栈和队列也有很多的联系，本题就是用两个栈实现一个队列。

用两个栈实现队列

题目

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

分析

       我们知道栈是先进后出，而队列是先进先出。两个栈是可以实现先进后出的，我们模拟进队列操作时，进队列都进入第一个栈，然后出队列操作时，先把栈1全部倒入栈2，栈2出栈完成出队列操作，为了保证顺序，栈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
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() {
        //如果栈1不为空，把栈1值导入栈2，完成逆序
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        //栈2栈顶出队列
        int first=stack2.pop();
        //这里是重点：栈2的值都要倒回栈1，因为如果不倒回，出队列操作之后，栈2还有元素，但是之
        //后进队列的元素又倒回栈2，这样就乱序了，倒回保证每次栈2中先进的都在下面，整体倒入栈2
        //后肯定保证是先进的元素在栈顶
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        //
        return first;
    }
}