一、用栈实现队列

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)