两个栈实现队列——jzoffer

操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。

• 栈的特点是后进先出，最后被压入（push）栈的元素会第一个被弹出（pop）；
• 通常栈是一个不考虑排序的数据结构，我们需要O(n)时间才能找到其中最大或最小的元素。

队列的特点是先进先出

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数append_tail和delete_head，分别完成在队列尾部插入节点和在队列头部删除节点的功能

'''
class CQueue:
    def append_tail(self, val):
        pass
    def delete_head(self):
        pass
'''
class CQueue:
    def __init__(self):
        self.stack_a = []
        self.stack_b = []
    def append_tail(self, val):
        self.stack_a.append(val)
    def delete_head(self):
        if self.stack_b:
            ret = self.stack_b.pop()
        else:
            if not self.stack_a:
                raise Exception("CQueue is empty")
            while self.stack_a:
                item = self.stack_a.pop()
                self.stack_b.append(item)
            ret = self.stack_b.pop()
        return ret