232. Implementing queues with stacks

Leetcode-cn.com/problems/im…

Topic describes

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, pop, peek, empty) : Void push(int x) pushes element x to the end of the queue int pop() removes the element from the beginning of the queue and returns the element int peek() returns the element at the beginning of the queue Boolean empty() Returns true if the queue is empty; Otherwise, return false note: You can only use standard stack operations -- only push to Top, peek/pop from Top, size, and is empty are legal. Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it's standard stack operations. Advanced: Can you implement a queue with O(1) amortized time per operation? In other words, the total time complexity of performing n operations is O(n), even though one of them may take a long time. Example: input: [" MyQueue ", "push" and "push" and "peek", "pop", "empty"] [[], [1], [2], [], [], []] output: [null, null, null, 1, 1, false] MyQueue MyQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false hint: 1 <= x <= 9 calls push, pop, peek, and empty up to 100 times assuming all operations are valid (e.g., an empty queue does not call pop or peek)Copy the code

Train of thought

PeekIndex is used as A pointer to record the last digit, Alist and Blist implement push and pop, and in pop, when Blist is empty, the A is reversed

code

  • Language support: Python3

Python3 Code:


class MyQueue:

    def __init__(self) :
        """ Initialize your data structure here. """
        self.Alist = []
        self.Blist = []
        self.peekIndex = None


    def push(self, x: int) - >None:
        """ Push element x to the back of queue. """
        self.Alist.append(x)
        if len(self.Alist)== 1:
            self.peekIndex = x


    def pop(self) - >int:
        """ Removes the element from in front of queue and returns that element. """
        If B is empty, pour from A to B
        if len(self.Blist) == 0 and len(self.Alist) == 0:
            return None
        if len(self.Blist) ! =0:
            return self.Blist.pop()
        else:
            while len(self.Alist)! =0:
                self.Blist.append(self.Alist.pop())
            self.peekIndex = None
            return self.Blist.pop()


    def peek(self) - >int:
        """ Get the front element. """
        if self.Blist.__len__() == 0:
            return self.peekIndex
        else:
            return self.Blist[-1]

    def empty(self) - >bool:
        """ Returns whether the queue is empty. """
        if self.peekIndex == None and len(self.Blist) == 0:
            return True
        else:
            return False


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

Copy the code

Complexity analysis

Let n be the length of the array.

  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(n)O(n)O(n)