Implement Stack with Queue

题目描述

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

解题方法

Version A:

• push: enqueue in queue1
• pop: while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2 dequeue and return the last item of queue1, then switch the names of queue1 and queue2

Version B:

• push: enqueue in queue2 enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2
• pop: deqeue from queue1

Solution

Version B

from collections import deque

class Stack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.queue1 = deque()
        self.queue2 = deque()

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.queue1.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        while len(self.queue1) > 1:
            ele = self.queue1.popleft()
            self.queue2.append(ele)
        result = self.queue1.pop()
        self.queue1, self.queue2 = self.queue2, self.queue1
        return result

    def top(self):
        """
        :rtype: int
        """
        if len(self.queue1) > 1:
            ele = self.queue1.popleft()
            self.queue2.append(ele)
        result = self.queue1[-1]
        return result

    def empty(self):
        """
        :rtype: bool
        """
        if not self.queue1 and not self.queue2:
            return True
        else:
            return False

Reference

• stackoverflow
• geeksforgeeks