232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

 

说明：

• 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

 

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

 

示例：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

先了解一下栈和队列

栈：先进后出

队列：先进先出

JAVA中栈的基本用法：

Stack的基本使用
初始化
private Stack<Integer> a = new new Stack<>();
private Stack<Integer> b = new new Stack<>();
判断是否为空
a.empty()
取栈顶值（不出栈）
a.peek()
进栈
a.push(Object);
出栈
stack.pop();
 
实例：
public class Test01 {
    public static void main(String[] args) {
        Stack stack=new Stack();
        //1.empty()栈是否为空
        System.out.println(stack.empty());
        //2.peek()栈顶值    3.进栈push()
        stack.push(new Integer(1));
        stack.push("b");
        System.out.println(stack.peek());
        //4.pop()出栈
        stack.pop();
        System.out.println(stack.peek());
        
    }
}

JAVA中队列的基本用法：

队列测试：实现类使用LinkedList

public class TestQuene {

// 定义一个队列
Queue<String> queue = new LinkedList<String>();


 // add方法向队列中添加元素,返回布尔值，add方法添加失败时会抛异常,不推荐使用
 // queue.add("1");
 // queue.add("2");
 // queue.add("3");
 // queue.add("4");
 // queue.add("5");

 // offer方法向队列中添加元素，返回布尔值
 queue.offer("a");
 queue.offer("b");
 queue.offer("c");
 queue.offer("d");
 queue.offer("e");
}

// poll方法移除队列首个元素并返回，若队列为空，返回null

public void test1() {
// 弹出元素
String pollEle = queue.poll(); // 先进先出,弹出了a
System.out.println(pollEle); // a
System.out.println(queue); // [b, c, d, e]
}

// remove方法移除首个元素并返回,若队列为空,会抛出异常：NoSuchElementException，不推荐使用

public void test2() {
// 弹出元素
String remove = queue.remove(); // 先进先出,弹出了a
System.out.println(remove); // a
System.out.println(queue); // [b, c, d, e]
}

// peek方法返回队列首个元素，但不移除，若队列为空，返回null

public void test3() {
// 查看首个元素
String peek = queue.peek(); // 首个元素是a,最先加入
System.out.println(peek); // a
System.out.println(queue); // [a, b, c, d, e]
}

// element方法返回队列的头元素，但不移除，若队列为空，会抛出异常：NoSuchElementException，不推荐使用

public void test4() {
// 查看首个元素
String element = queue.element();
System.out.println(element); // a
System.out.println(queue); // [a, b, c, d, e]
}

}

 

 

本题要求使用两个栈来实现队列，也就是将先进后出改造成先进先出。

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    /** Initialize your data structure here. */
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {//将元素 x 推到队列的末尾
        s1.push(x);

    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {//从队列的开头移除并返回元素
        if(s2.isEmpty()==true){//  如果s2栈为空，则将s1栈全部弹出并压入s2栈中，然后s2.pop()
            while(s1.isEmpty()!=true){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    /** Get the front element. */
    public int peek() {//返回队列开头的元素
        if(s2.isEmpty() == true){
            while(s1.isEmpty()!=true){
                s2.push(a.pop());
            }
        }
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {//如果队列为空，返回 true ；否则，返回 false
        return s1.isEmpty() && s2.isEmpty();
    }
}