数据结构（二）

一、用栈实现队列

class MyQueue {

    private Stack<Integer> s1 = null;
    private Stack<Integer> s2 = null;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        shift();
        if(!s2.isEmpty()) {
            return s2.pop();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Get the front element. */
    public int peek() {
        shift();
        if(!s2.isEmpty()) {
            return s2.peek();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
    
    //将s1中的全部谈进s2,但是要保证s2为空
    public void shift() {
        if (s2.isEmpty()) {
            while(!s1.isEmpty()) {
                s2.push(s1.pop());
            }
        }
    }
}

/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */

二、用队列实现栈

栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈内元素从顶端压入（push），从顶端弹出（pop）。一般我们用数组或者链表来实现栈，但是这里会介绍如何用队列来实现栈。队列是一种与栈相反的 先进先出（first in - first out， FIFO）的数据结构，队列中元素只能从 后端（rear）入队（push），然后从 前端（front）端出队（pop）。为了满足栈的特性，我们需要维护两个队列 q1 和 q2。同时，我们用一个额外的变量来保存栈顶元素。

思路：画图帮助分析。

方法：peek 和 pop 时，依次将队首出队到队尾

• 1、push 的时候，直接在队列的尾部添加元素即可；

• 2、只要涉及到 peek 或者 pop 操作，要满足栈“后进先出”的性质。需要当前是队尾的元素成为队首，而队列只支持队首出队，队尾入队。很容易想到需要依次把队尾之前的元素出队，放到哪里呢？直接放在队尾即可。因此，定义一个操作 shift ，将队首元素出队，出队以后放在队尾（真的是有毛病，爱的魔力转圈圈）。这个操作需要执行当前队列长度 - 1 次。

• 3、peek 的时候，得到队尾元素以后，还得再队首元素移动到队尾一次。分析到这里，发现，其实如果我连着几次 peek 操作，得转好几圈。其实可以使用一个变量，记录上一次的操作是什么，这样会更合理一些。但是实际测试下来，因为每次多了一些判断，会消耗一些时间。

class MyStack {

    private Queue<Integer> q;
    
    /** Initialize your data structure here. */
    public MyStack() {
        q = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        q.offer(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if (!q.isEmpty()) {
            shift();
            return q.poll();
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Get the top element. */
    public int top() {
        if (!q.isEmpty()) {
            shift();
            int elem = q.poll();
            q.offer(elem);
            return elem;
        }
        throw new RuntimeException("队列中没有元素");
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
    
    public void shift() {
        for (int i = 0; i < q.size() - 1; i++) {
            q.offer(q.poll());
        }
    }
}

/** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */

参考链接：来源：力扣（LeetCode）