《剑指Offer》栈和队列

1 基本概念

栈：后进先出
队列：先进先出

栈和队列是计算中使用最广泛的缓存结构，其使用环境可以总结如下：

• 计算过程分为一些顺序进行的步骤（任何复杂一点的计算都是这样）
• 计算中执行的某些步骤会不断产生一些后面可能需要的中间数据
• 产生的数据中有些不能立即使用，但又需要在将来使用
• 需要保存的数据项数不能事先（在编程序的时候）确定

在这种情况下，通常就需要用一个栈或者队列作为缓存结构。

由于栈和队列在计算机应用中的重要性，Python的基本功能中已经包含了堆栈的支持，可以直接用list实现栈的功能。此外，Python标准库还提供了一种支持队列用途的结构deque， 有关情况在后面介绍。

1.1 栈

栈的抽象数据类型描述：

ADT Stack:
  Stack(self)  #创建空栈
  is_empty(self)  #判断栈是否为空，空时返回True否则返回False
  push(self, elem)  #将元素elem加入栈，也称为压入获推入
  pop(self)  #删除栈里最后压入的元素并将其返回，称为弹出
  top(self)  #取得栈里最后压入的元素，不删除

1.1.1 栈的顺序表实现

实现栈结构之前，先考虑为操作失败的处理定义一个异常类。Python程序里的自定义异常都应定义为Exception的派生类。自定义异常和Python内置异常类似，同样通过except捕捉和处理，但（显然）只能通过raise语句引发。

Python的list实现方法可以如下考虑（假定lst的值是一个表）：

• 建立空栈对应于创建一个空表[]，判断空栈对应于检查是否为空表
• 由于list采用动态顺序表技术（分离式实现），作为栈的表不会满
• 压入元素操作应在表的尾端进行，对应于lst.append(x)
• 访问栈顶元素应该用lst[-1]
• 弹出操作也应该在表尾端进行，无参的lst.pop()默认弹出表尾元素

class StackUnderflow(ValueError):
    pass

class SStack():
    def __init__(self):
        self._elem = []

    def is_empty(self):
        return self._elem ==[]

    def top(self):
        if self._elem ==[]:
            raise StackUnderflow("in SStack.top()")
        return self._elem[-1]

    def push(self, elem):
        self._elem.append(elem)

    def pop(self):
        if self._elem ==[]:
            raise StackUnderflow("in SStack.pop()")
        return self._elem.pop()


st1 = SStack()
st1.push(5)
st1.push(4)
while not st1.is_empty():
    print(st1.pop())

注意这里两个raise语句，它们都包含了一个字符串实参。执行中实际产生的异常对象将携带者信息。在异常的引发处，可以用这种实参向最终捕捉到这个异常的处理器传递一些信息。

1.1.2 栈的链接表实现

class StackUnderflow(ValueError):
    pass

class SNode():
    def __init__(self,x,thenext = None):
        self._elem = x
        self.next = thenext

class LStack():
    def __init__(self):
        self._top = None

    def is_empty(self):
        return self._top is None

    def top(self):
        if self._top is None:
            raise StackUnderflow('in LStack.top()')
        return self._top._elem

    def push(self,elem):
        self._top = SNode(elem,self._top)

    def pop(self):
        if self._top is None:
            raise StackUnderflow('in LStack.pop()')
        p = self._top
        self._top = p.next
        return p._elem


    def printlink(self):
        if self._top is None:
            raise StackUnderflow('in LStack.printlink()')
        p = self._top
        while p.next is not None:
            print(p._elem,end = ', ')
            p = p.next
        print(p._elem)


ls = LStack()
tlist = [3,5,7,9,10,66]
for ele in tlist:
    ls.push(ele)

ls.printlink()

栈可以用来颠倒序列顺序，时间复杂度为O(n)。但不能得到原序列的任意排列，结果序列有一定的规律性。

1.2 队列

队列的抽象数据类型：与栈一一对应，只是通常采用另一套习惯的操作名（enqueue/dequeuer/peek）。

ADT Queue:
  Queue(self)  #创建空队列
  is_empty(self)  #判断队列是否为空，空时返回True否则False
  enqueue(self, elem)  #将元素elem加入队列，常称为入队
  dequeue(self)  #删除队列里最早进入的元素并将其返回，常称为出队
  peek(self)  #查看队列里最早进入的元素，不删除

最简单的单链表只支持首端高效操作，在另一端操作需要O(n)时间，不适合作为队列的实现基础。

有了尾端指针，尾端加入元素是O(1)时间操作。

数据不变式：
实现一种数据结构里的操作时，最基本的问题就是这些操作需要维护对象属性之间的正确关系，这样一套关系被称为这种数据结构（现在考虑的时队列）的数据不变式。

队列类的实现：

class QueueUnderflow(ValueError):
    pass

class SQueue():
    def __init__(self, init_len = 8):
        self._len = init_len
        self._elems = [0]*init_len
        self._head = 0
        self._num = 0

    def is_empty(self):
        return self._num ==0

    def peek(self):
        if self._num ==0:
            raise QueueUnderflow
        return self._elems[self._head]

    def dequeue(self):
        if self._num ==0:
            raise QueueUnderflow
        e = self._elems[self._head]
        self._head = (self._head +1)% self._len
        self._num -=1
        return e

    def enqueue(self,e):
        if self._num == self._len:
            self._extend()
        self._elems [(self._head + self._num) % self._len] = e
        self._num +=1

    def _extend(self):
        old_len = self._len
        self._len *=2
        new_elems = [0]*self._len
        for i in range(old_len):
            new_elems[i] = self._elems[(self._head +i)%old_len]
        self._elems, self._head = new_elems, 0

    def output(self):
        if self._num == 0:
            raise QueueUnderflow
        if self._len >= self._head + self._num:
            for ele in self._elems[self._head:self._head+ self._num]:
                print(ele,end = ', ')
        else:
            for ele in self._elems[self._head:]:
                print(ele,end = ', ')
            for ele in self._elems[:(self._head+self._num)%self._len]:
                print(ele,end = ', ')


sq = SQueue()
tlist = [1,3,5,7,9,11,13,17,19]
for ele in tlist:
    sq.enqueue(ele)
sq.output()

2 面试题

2.1 用两个栈实现队列

题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

Python实现
运行时间：27ms, 占用内存：5740k

class Solution:
    def __init__(self):
        self.stackA = []
        self.stackB = []
    def push(self, node):
        # write code here
        self.stackA.append(node)
    def pop(self):
        # return xx
        if self.stackB:
            return self.stackB.pop()
        elif not self.stackA:
            return None
        else:
            while self.stackA:
                self.stackB.append(self.stackA.pop())
            return self.stackB.pop()

2.2 镜像问题：用两个队列实现栈

队列用链表形式实现最合适，这里仅方便起见使用list实现：

class Solution():
    def __init__(self):
        self.queue1 = []
        self.queue2 = []

    def push(self, node):
        self.queue1.append(node)

    def pop(self):
        if not self.queue1:
           return None
        for i in range(0, len(self.queue1)-1):
            self.queue2.append(self.queue1[0])
            del self.queue1[0]
        e = self.queue1[0]
        del self.queue1[0]
        return e

sl = Solution()
for ele in [3,4,5,6,7,8]:
    sl.push(ele)

sl.pop()