0232._implement_queue_using_stacks.md

Navigation

• Navigation
• Links:
• Solution 1 使用两个栈 入队 - O(n)， 出队 - O(1)
• Solution 2 使用两个栈 入队 - O(1)，出队 - 摊还复杂度 O(1)（平均）

Links:

1. https://leetcode.com/problems/implement-queue-using-stacks/
2. https://leetcode-cn.com/problems/implement-queue-using-stacks/

Solution 1 使用两个栈 入队 - O(n)， 出队 - O(1)

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.master = []
        self.slave = []

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        while self.master:
            self.slave.append(self.master.pop())

        self.master.append(x)

        while self.slave:
            self.master.append(self.slave.pop())


    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        return self.master.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        return self.master[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.master

Solution 2 使用两个栈 入队 - O(1)，出队 - 摊还复杂度 O(1)（平均）

无论是哪个元素，都是入栈两次(进一次A和一次B)，出栈两次(同理)，所以平均复杂度都是O（1)

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.master = []
        self.slave = []

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.slave.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if not self.master:
            self.move()
        
        return self.master.pop()

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.master:
            self.move()
        
        return self.master[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.master and not self.slave
        
    def move(self):
        while self.slave:
            self.master.append(self.slave.pop())