用两个栈实现队列

【题目】：

用两个栈实现一个队列，实现这个队列的删除头部deleteHead和插入尾部appendTail的功能。

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

【解题思路】：

• 构造两个栈：stack1， stack2：
• 从队列中删除一个头节点： 先将数据压入到stack1中， 要删除头节点的时候，将stack1中的元素出栈再压入到stack2中，这时stack2栈顶的元素就是头节点；
• 插入一个为尾节点：直接将数据压入到stack1中。
   

class MyQueue(object):
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def append_tail(self, val):
        self.stack1.append(val)
        print("The %d is added to tail of the queue" % val)

    def delete_head(self):
        if self.stack2:
            print("The head is deleted from the queue, the head value is:", self.stack2.pop(-1))
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop(-1))
            if not self.stack2:
                print("The queue is empty!")
                return
            print("The head is deleted from the queue, the head value is:", self.stack2.pop(-1))


# test
q = MyQueue()
# delete head from an empty queue
print("# delete head from an empty queue")
q.delete_head()
# add [1,2,3] to the queue, and then delete the head
print("# add [1,2,3] to the queue, and then delete the head")
for i in [1, 2, 3]:
    q.append_tail(i)
q.delete_head()

# add [4, 5] to the queue, and the delete the head twice
print("# add [4, 5] to the queue, and the delete the head twice")
for i in [4, 5]:
    q.append_tail(i)
for i in range(2):
    q.delete_head()

# delete the head 3 times
print("# delete the head 3 times")
for i in range(3):
    q.delete_head()

运行结果：

示例代码2：

class CQueue(object):

    def __init__(self):
        self.stack1 = []
        self.stack2 = []


    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self.stack1.append(value)


    def deleteHead(self):
        """
        :rtype: int
        """
        if self.stack2:
            return self.stack2.pop()
        if not self.stack1:
            return -1
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        return self.stack2.pop()



# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()