棧

棧是由一系列對(duì)象組成的一個(gè)集合，這些對(duì)象的插入和刪除操作遵循后進(jìn)先出的原則蝇率。用戶可以在任何時(shí)刻向棧中插入一個(gè)對(duì)象迟杂，但只能取得或者刪除最后一個(gè)插入的對(duì)象（即所謂的“棧頂”）。
下面是一些使用堆棧的示例：
1 網(wǎng)絡(luò)瀏覽器將最近瀏覽的網(wǎng)址存放在一個(gè)棧中本慕。每次當(dāng)訪問(wèn)者訪問(wèn)一個(gè)新網(wǎng)站時(shí)排拷，這個(gè)新網(wǎng)站的網(wǎng)址就會(huì)壓入棧頂。這樣锅尘，瀏覽器就可以在用戶點(diǎn)擊“后退”按鈕時(shí)监氢，彈出先前訪問(wèn)的網(wǎng)址，以回到先前訪問(wèn)的網(wǎng)頁(yè)。
2 文本編輯器通常需要提供一個(gè)“撤銷(xiāo)”機(jī)制已取消最近的編輯操作并返回到先前的文本狀態(tài)浪腐。這個(gè)撤銷(xiāo)操作就是通過(guò)將文本的變化狀態(tài)保存在一個(gè)棧中得以實(shí)現(xiàn)的何鸡。

棧的抽象數(shù)據(jù)類(lèi)型

棧是最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，但它同樣也是最重要的數(shù)據(jù)結(jié)構(gòu)牛欢。用S來(lái)表示這一抽象數(shù)據(jù)類(lèi)型的一個(gè)實(shí)例：
S.push(e):將一個(gè)元素e添加到棧S的棧頂骡男。
S.pop(e):從棧S中移除并且返回棧頂?shù)脑兀绻藭r(shí)棧是空的傍睹，這個(gè)操作將出錯(cuò)隔盛。
S.top()：再不一處棧頂元素的前提下，返回一個(gè)棧S的棧頂元素拾稳；若棧為空吮炕，這個(gè)操作將會(huì)出錯(cuò)。
S.is_empty()：如果棧中不包括任何元素访得，則返回一個(gè)布爾值“True”
len(S)：返回棧S中元素的數(shù)量龙亲。

簡(jiǎn)單的基于數(shù)組的棧實(shí)現(xiàn)

# 用Python列表作為存儲(chǔ)實(shí)現(xiàn)一個(gè)棧
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()

分析基于數(shù)組的棧實(shí)現(xiàn)
在最壞的情況下， top悍抑，len,is_emoty方法均在常量時(shí)間內(nèi)完成鳄炉。對(duì)于push和pop操作的時(shí)間復(fù)雜度為O(1)，指的是攤銷(xiāo)計(jì)算的邊界搜骡。
避免由于預(yù)留空間所導(dǎo)致的攤銷(xiāo)
我們相信拂盯，在實(shí)際中狗雜偶哦個(gè)最初長(zhǎng)度為n的列表要比一開(kāi)始就從一個(gè)空的列表開(kāi)始逐步添加n項(xiàng)更加有效（即使兩種方法均能在O(n)時(shí)間內(nèi)運(yù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

使用棧實(shí)現(xiàn)數(shù)據(jù)的逆置

#實(shí)現(xiàn)文件中各行的逆置函數(shù)
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()

括號(hào)和HTML標(biāo)記匹配

分隔符的匹配算法

# 在算數(shù)表達(dá)式中分隔符匹配算法的函數(shù)實(shí)現(xiàn)
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()

# 測(cè)試一個(gè)HTML文本是否有匹配標(biāo)簽的函數(shù)
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()

隊(duì)列

隊(duì)列是另一種基本的數(shù)據(jù)結(jié)構(gòu)，是由一系列對(duì)象組成的集合记靡，這些對(duì)象的插入和刪除遵循先進(jìn)先出的原則谈竿。也就是說(shuō)，元素可以在任何時(shí)刻進(jìn)行插入摸吠，但只有處在隊(duì)列最前面的元素才能被刪除空凸。

隊(duì)列的抽象數(shù)據(jù)類(lèi)型

通常來(lái)說(shuō)，隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義了一個(gè)包含一系列對(duì)象的集合寸痢，其中元素的訪問(wèn)和刪除被限制在隊(duì)列的第一個(gè)元素呀洲，而且元素的插入被限制在序列的尾部。
對(duì)于隊(duì)列Q而言：
Q.enqueue(e)：向隊(duì)列Q的尾部添加一個(gè)元素
Q.dequeue(e)：從隊(duì)列Q中移除并返回第一個(gè)元素轿腺，如果隊(duì)列為空两嘴，則觸發(fā)一個(gè)錯(cuò)誤。
Q.first()：在不移除的前提下返回隊(duì)列的第一個(gè)元素族壳；如果隊(duì)列為空憔辫，則觸發(fā)一個(gè)錯(cuò)誤。
Q.is_empty()：如果隊(duì)列Q沒(méi)有包含任何元素則返回布爾值“true”
len(Q)：返回隊(duì)列Q中元素的數(shù)量

基于數(shù)組的隊(duì)列實(shí)現(xiàn)

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

雙端隊(duì)列

接下來(lái)考慮一個(gè)類(lèi)隊(duì)列數(shù)據(jù)結(jié)構(gòu)仿荆，它支持在隊(duì)列的頭部和尾部都進(jìn)行插入和刪除的操作贰您。這樣的一種結(jié)構(gòu)被稱為雙端隊(duì)列