用栈实现队列

题目

编写一个类，用两个栈实现队列。
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解答

栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。

具体实现时是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。

因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1～5依次压入stackPush，那么从stackPush的栈顶到栈底为5～1，此时依次再将5～1倒入stackPop，那么从stackPop的栈顶到栈底就变成了1～5。再从stackPop弹出时，顺序就像队列一样，如图1-3所示。

1.如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。

2.如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。违反了以上两点都会发生错误。

代码

class CQueue:
    def __init__(self):
        self.appendStack = []
        self.delStack = []
    def appendTail(self, value: int) -> None:
        self.appendStack.append(value)
    def deleteHead(self) -> int:
        if len(self.delStack) == 0 and len(self.appendStack) == 0:
            return -1
        if len(self.delStack) != 0:
            return self.delStack.pop()
        else:
            while len(self.appendStack) != 0:
                self.delStack.append(self.appendStack.pop())
            return self.delStack.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.appendStack = []
        self.delStack = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.appendStack.append(x)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.delStack) == 0 and len(self.appendStack) == 0:
            return -1
        if len(self.delStack) != 0:
            return self.delStack.pop()
        else:
            while len(self.appendStack) != 0:
                self.delStack.append(self.appendStack.pop())
            return self.delStack.pop()
    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.delStack) != 0:
            return self.delStack[-1]
        else:
            while len(self.appendStack) != 0:
                self.delStack.append(self.appendStack.pop())
            return self.delStack[-1]
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.delStack) == 0 and len(self.appendStack) == 0
# 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()