用队列实现栈

人类迷惑行为 x 1

queue 只保存队列的最后一个元素, 每次 top 或 pop 操作均需将 queue 中元素除队列最后一个元素外的所有元素倒入 help 中, queue 中最后一个元素再出队列, 以此模拟出栈操作.

import java.util.LinkedList;
import java.util.Queue;

public class QueueStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    public QueueStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    public void push(int newEle) {
        queue.add(newEle);
    }

    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        swap();
        return result;
    }

    public int peek() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        help.add(result);
        swap();
        return result;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    private void swap() {
        Queue tmp = queue;
        queue = help;
        help = tmp;
    }
}

例题: LeetCode #225

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈

• pop() – 移除栈顶元素

• top() – 获取栈顶元素

• empty() – 返回栈是否为空

注意:

• 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

Java

class MyStack {
    private Queue<Integer> queue;
    private Queue<Integer> help;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue = new LinkedList<>();
        help = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        queue.add(x);
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        swap();
        return result;
    }

    /**
     * Get the top element.
     */
    public int top() {
        if (queue.isEmpty()) {
            throw new RuntimeException("Empty stack");
        }
        while (queue.size() != 1) {
            help.add(queue.poll());
        }

        int result = queue.poll();
        help.add(result);
        swap();
        return result;
    }

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

    private void swap() {
        Queue tmp = queue;
        queue = help;
        help = tmp;
    }
}

Python

class MyStack():
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue = []
        self.help_queue = []

    def push(self, x):
        """
        Push element x onto stack.
        """
        self.queue.insert(0, x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        """
        if len(self.queue) == 0:
            return None

        while len(self.queue) != 1:
            self.help_queue.insert(0, self.queue.pop())

        result = self.queue.pop()
        self.queue, self.help_queue = self.help_queue, self.queue
        return result

    def top(self):
        """
        Get the top element.
        """
        if len(self.queue) == 0:
            return None

        while len(self.queue) != 1:
            self.help_queue.insert(0, self.queue.pop())

        result = self.queue.pop()
        self.help_queue.insert(0, result)
        self.queue, self.help_queue = self.help_queue, self.queue
        return result

    def empty(self):
        """
        Returns whether the stack is empty.
        """
        return len(self.queue) == 0