로고조성현

0232 Implement Queue using Stacks

Solved at: 2022-11-28

Question

Implement a first in, first out (FIFO) queue using only two stacks. The implemented queue should support a regular queue's functions (push, peek, pop, and empty).

  • Implement the MyQueue class:
    • void push(int x) Pushes element x to the back of the queue.
    • int pop() Removes the element from the front of the queue and returns it.
    • int peek() Returns the element at the front of the queue.
    • boolean empty() Returns true if the queue is empty, false otherwise.
  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, the stack may not be supported natively. Using only a stack's standard operations, you may simulate a stack using a list or deque (double-ended queue).

Solution

class MyQueue:
    front = []
    back = []

    def __init__(self):
        self.front = []
        self.back = []

    def push(self, x: int) -> None:
        self.back.append(x) # push to top

    def pop(self) -> int:
        if not self.front:
            while self.back:
                self.front.append(self.back.pop())
        return self.front.pop()

    def peek(self) -> int:
        if not self.front:
            while self.back:
                self.front.append(self.back.pop())
        return self.front[-1]

    def empty(self) -> bool:
        return not self.front and not self.back

Results

  • Runtime: 46 ms, Beats 72.73%
  • Memory, 14 MB Beats 76.5%

Accepted on the first try? Let's go!

Complexity Analysis

  • Push - O(1)O(1) per operation,
  • Pop - Amortized O(1)O(1) per operation.
  • Space: O(n)O(n)

Depending on the policy of moving elements in the queue, either moving ahead of time or just in time, the time complexity can vary from O(1)O(1) to O(n)O(n).