栈

栈是由一系列对象组成的一个集合，这些对象的插入和删除操作遵循后进先出的原则。用户可以在任何时刻向栈中插入一个对象，但只能取得或者删除最后一个插入的对象（即所谓的“栈顶”）。
下面是一些使用堆栈的示例：
1 网络浏览器将最近浏览的网址存放在一个栈中。每次当访问者访问一个新网站时，这个新网站的网址就会压入栈顶。这样，浏览器就可以在用户点击“后退”按钮时，弹出先前访问的网址，以回到先前访问的网页。
2 文本编辑器通常需要提供一个“撤销”机制已取消最近的编辑操作并返回到先前的文本状态。这个撤销操作就是通过将文本的变化状态保存在一个栈中得以实现的。

栈的抽象数据类型

栈是最简单的数据结构，但它同样也是最重要的数据结构。用S来表示这一抽象数据类型的一个实例：
S.push(e):将一个元素e添加到栈S的栈顶。
S.pop(e):从栈S中移除并且返回栈顶的元素，如果此时栈是空的，这个操作将出错。
S.top()：再不一处栈顶元素的前提下，返回一个栈S的栈顶元素；若栈为空，这个操作将会出错。
S.is_empty()：如果栈中不包括任何元素，则返回一个布尔值“True”
len(S)：返回栈S中元素的数量。

简单的基于数组的栈实现

# 用Python列表作为存储实现一个栈
from queue import Empty


class ArrayStack:
    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data)==0

    def push(self,e):
        self._data.append(e)

    def top(self):
        if self.is_empty():
            raise Empty('stack is empty')
        return self._data[-1]

    def pop(self):
        if self.is_empty():
            raise Empty('stack is empty')

        return self._data.pop()

分析基于数组的栈实现
在最坏的情况下， top，len,is_emoty方法均在常量时间内完成。对于push和pop操作的时间复杂度为O(1)，指的是摊销计算的边界。
避免由于预留空间所导致的摊销
我们相信，在实际中狗杂偶哦个最初长度为n的列表要比一开始就从一个空的列表开始逐步添加n项更加有效（即使两种方法均能在O(n)时间内运行完毕）

class ArrayStack2:
    def __init__(self,size):
        self.size = size
        self._data = []
        self._n = 0

    def __len__(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data)==0

    def push(self,e):
        if self.is_full():
            return Exception('overflow!')
        self._data.append(e)
        self._n += 1

    def top(self):
        if self.is_empty():
            raise Empty('stack is empty')
        return self._data[-1]

    def pop(self):
        if self.is_empty():
            raise Empty('stack is empty')
        self._n -= 1
        return self._data.pop()

    def is_full(self):
        return self.size == self._n

使用栈实现数据的逆置

#实现文件中各行的逆置函数
def reverse_file(filename):
    S = ArrayStack()
    original = open(filename)
    for line in original:
        S.push(line.rstrip('\n'))
    original.close()
    
    output = open(filename,'w')
    while not S.is_empty():
        output.write(S.pop() + '\n')
    output.close()

括号和HTML标记匹配

分隔符的匹配算法

# 在算数表达式中分隔符匹配算法的函数实现
def is_matched(expr):
    lefty = '({['
    righty = ')}]'
    S = ArrayStack()
    for c in expr:
        if c in lefty:
            S.push(c)
        elif c in righty:
            if S.is_empty():
                return False
            if righty.index(c) != lefty.index(S.pop()):
                return False
    return S.is_empty()

# 测试一个HTML文本是否有匹配标签的函数
def is_matched_html(raw):
    S = ArrayStack()
    j = raw.find('<')
    while j != -1:
        k = raw.find('>',j+1)
        if k == -1:
            return False
        tag = raw[j+1:k]
        if not tag.startswith('/'):
            S.push(tag)
        else:
            if S.is_empty():
                return False
            if tag[1:] != S.pop():
                return False
        j = raw.find('<',k+1)
    return S.is_empty()

队列

队列是另一种基本的数据结构，是由一系列对象组成的集合，这些对象的插入和删除遵循先进先出的原则。也就是说，元素可以在任何时刻进行插入，但只有处在队列最前面的元素才能被删除。

队列的抽象数据类型

通常来说，队列的抽象数据类型定义了一个包含一系列对象的集合，其中元素的访问和删除被限制在队列的第一个元素，而且元素的插入被限制在序列的尾部。
对于队列Q而言：
Q.enqueue(e)：向队列Q的尾部添加一个元素
Q.dequeue(e)：从队列Q中移除并返回第一个元素，如果队列为空，则触发一个错误。
Q.first()：在不移除的前提下返回队列的第一个元素；如果队列为空，则触发一个错误。
Q.is_empty()：如果队列Q没有包含任何元素则返回布尔值“true”
len(Q)：返回队列Q中元素的数量

基于数组的队列实现

class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

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

    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        return self._data[self._front]

    def dequeue(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front +1)%len(self._data)
        self._size -= 1
        return answer

    def enqueue(self,e):
        if self._size == len(self._data):
            self._resize(2*len(self._data))

        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

    def _resize(self,cap):
        old = self._data
        self._data = [None]*cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1+walk)%len(old)
        self._front = 0

双端队列

接下来考虑一个类队列数据结构，它支持在队列的头部和尾部都进行插入和删除的操作。这样的一种结构被称为双端队列