题目描述

    用两个栈实现队列的简单操作
    push(int x),pop(),peek(),empty()

分析

我没找到Java语言的题解，故而写下自己不成熟的但是正确的题解给有需要的朋友借鉴。

可能由于题目简单的缘故，我没看见有详解，既然这样，基础的事情就让我这新手来做吧。

    一、首先要了解栈和队列。栈和队列是两种数据结构，栈的特点是“后进先出”，把栈想象成水杯，先进入

栈的元素放在栈底，再进来一个元素放在刚才元素的上方，然后依次压摞摞，因而出栈的时候只能让最后进来

的元素先出去，这就是“后进先出”。队列的特点是“先进先出”，就像在食堂买饭一样，先进入到队列里的元素

先买饭先离开队伍，这就是“先进先出”。

    二、不用说，在自定义MyQueue类里要有两个队列（题目要求就是两个栈，一个也实现不了），从题目中的

push(int x)方法以及样例输入输出可以知道，该队列内存放的元素为int类型，因此定义两个元素基类型为int的

栈，命名stack1，stack2。此两个栈在算法实现过程中的地位并不对等，stack1主要存放数据，stack2是为了

实现各方法而起到了临时中转站的作用（具体的实现往下看），设置不对等地位一方面也是为了编写易理解的代码。

    三、push(int x)方法的实现

    队列元素入队，就是为了存放数据，我在这里直接使元素x入栈stack1。

    四、pop()

    队列的pop是取队头元素，即最先push进来的元素，但该元素存储在栈stack1的栈底，因此若想取出栈底

元素，就要想办法把它变为栈顶元素。OK，这个时候stack2就该上场了。把stack1的栈顶元素入栈进入到

stack2，即语句stack2.push(stack1.pop());重复此操作直至全部元素进入到stack2。现在让stack2栈顶元素

出栈即为队列的队头元素出队。完成出队操作后，还要把stack2剩下的元素放回stack1内，因为stack1是存放

数据的，而且下文的empty()方法也是依据stack1完成的。

    五、peek()

    跟pop()基本一样，无非就是对队头元素（stack1的栈底元素）进行的操作不同。

    六、empty()

    empty()方法就是判断栈是否为空，在上文中已经说明了stack1主要用来存放数据，因此直接把stack1是否

为空的结果return回去就好了。

Java 代码

class MyQueue {

Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();

/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
    stack1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
    if (!stack1.empty()) {
        while (!stack1.empty()) {
            stack2.push(stack1.pop());              
        }
        int popValue = stack2.pop();
        while (!stack2.empty()) {
            stack1.push(stack2.pop());              
        }
        return popValue;
    }
    return 0;
}

/** Get the front element. */
public int peek() {
    if (!stack1.empty()) {
        while (!stack1.empty()) {
            stack2.push(stack1.pop());              
        }
        int popValue = stack2.peek();
        while (!stack2.empty()) {
            stack1.push(stack2.pop());              
        }
        return popValue;
    }
    return 0;
}

/** Returns whether the queue is empty. */
public boolean empty() {
    return stack1.empty();
}

}

码字着实还是有点累且花费时间的，希望能对各位有所帮助。