棧

棧（stack），有些地方稱(chēng)為堆棧，是一種容器，可存入數(shù)據(jù)元素、訪問(wèn)元素、刪除元素，它的特點(diǎn)在于只能允許在容器的一端（稱(chēng)為棧頂端指標(biāo)，英語(yǔ)：top）進(jìn)行加入數(shù)據(jù)（英語(yǔ)：push）和輸出數(shù)據(jù)（英語(yǔ)：pop）的運(yùn)算。沒(méi)有了位置概念，保證任何時(shí)候可以訪問(wèn)、刪除的元素都是此前最后存入的那個(gè)元素，確定了一種默認(rèn)的訪問(wèn)順序。
由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。

棧結(jié)構(gòu)實(shí)現(xiàn)

棧可以用順序表實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)。

棧的操作

• Stack() 創(chuàng)建一個(gè)新的空棧
• push(item) 添加一個(gè)新的元素item到棧頂
• pop() 彈出棧頂元素
• peek() 返回棧頂元素
• is_empty() 判斷棧是否為空
• size() 返回棧的元素個(gè)數(shù)

線性表都可以用來(lái)實(shí)現(xiàn)棧，棧只是一個(gè)容器，這里我們就用簡(jiǎn)單的順序表來(lái)實(shí)現(xiàn)棧，python中的順序表有哪幾種呢，我們直接用list來(lái)實(shí)現(xiàn)吧。

class Stack(object):
    '''棧'''
    def __init__(self):
        self.__list = []#首先建立這個(gè)容器
    def push(self,item):
    #添加一個(gè)新的元素item到棧頂，也就是壓棧
        return self.__list.append(item)
    def pop(self):
    #彈出棧頂元素
        return self.__list.pop()
    def peek(self):
    #返回棧頂元素
        if self.__list:
            return self.__list[-1]
        else:
            return None
    def is_empty(self):
    #判斷棧是否為空
        return self.__list == []
    def size(self):
        return len(self.__list)

if __name__ == '__main__':
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.size())
    print(s.peek())
    print(s.pop())
    print(s.pop())
    print(s.pop())
    print(s.pop())

為什么我們使用從尾部取元素和壓棧呢，因?yàn)槲膊康臅r(shí)間復(fù)雜度為O(1)，而如果是從頭部進(jìn)行取元素和壓棧，所需要的時(shí)間復(fù)雜度就是O(n)。

輸出如下：

4
4
4
3
2
1

說(shuō)完了這個(gè)，說(shuō)一下隊(duì)列的問(wèn)題。

隊(duì)列

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

隊(duì)列的實(shí)現(xiàn)

同棧一樣，隊(duì)列也可以用順序表或者鏈表實(shí)現(xiàn)。

操作

• Queue() 創(chuàng)建一個(gè)空的隊(duì)列
• enqueue(item) 往隊(duì)列中添加一個(gè)item元素
• dequeue() 從隊(duì)列頭部刪除一個(gè)元素
• is_empty() 判斷一個(gè)隊(duì)列是否為空
• size() 返回隊(duì)列的大小

class Queue(object):
    '''隊(duì)列'''
    def __init__(self):
        self.__list = []
    def enqueue(self,item):
        '''往隊(duì)列中添加一個(gè)item元素'''
        return self.__list.append(item)
        #return self.__list.insert(0,item)

    def dequeue(self):
        '''從隊(duì)列頭部刪除一個(gè)元素'''
        return self.__list.pop(0)
        #return self.__list.pop() pop()沒(méi)參數(shù)默認(rèn)是隊(duì)尾

    def is_empty(self):
        '''判斷一個(gè)隊(duì)列是否為空'''
        return self.__list == []

    def size(self):
        '''返回隊(duì)列的大小'''
        return len(self.__list)

if __name__ == '__main__':
    s = Queue()
    s.enqueue(1)
    s.enqueue(2)
    s.enqueue(3)
    s.enqueue(4)
    print('*'*20)
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())

因?yàn)樯婕暗絻蓚€(gè)通道，一頭壓棧，一頭出棧，所以總會(huì)有一頭的時(shí)間復(fù)雜度是O(n)，一個(gè)是O(1)。
輸出結(jié)果如下：

********************
1
2
3
4

雙端隊(duì)列

雙端隊(duì)列（deque，全名double-ended queue），是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。