用两个栈实现队列
【题目】：
用两个栈实现一个队列，实现这个队列的删除头部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()
