用两个栈实现队列

【题目】：

用两个栈实现一个队列，实现这个队列的删除头部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!")returnprint("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 -1while 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()