前文傳送門：
「一本正經的聊資料結構（1）：時間複雜度」
「一本正經的聊資料結構（2）：數組與向量」
引言
前一篇内容我們介紹了數組和向量，雖然說向量是數組的一個更新版，但是在另一個次元上，他們都屬于線性結構。
那麼什麼是線性結構呢？
線性結構是一個有序資料元素的集合。常用的線性結構有：線性表，棧，隊列，雙隊列，數組，串。
線性結構是最常用的資料結構，它最大的特點是資料元素之間存在一對一的線性關系。
線性結構擁有兩種不同的存儲結構，即順序存儲結構和鍊式存儲結構。
順序存儲的線性表稱為順序表，順序表中的存儲元素是連續的。
鍊式存儲的線性表稱為連結清單，連結清單中的存儲元素不一定是連續的，元素節點中存放資料元素以及相鄰元素的位址資訊。
線性結構中存在兩種操作受限的使用場景，就是我們本文要介紹的棧和隊列。
至于為什麼說棧和隊列是受限的線型結構，我們下面細聊。
棧
棧是一種比較奇葩的資料結構，棧的結構是支援對象的插入和删除操作，但是，棧操作的範圍僅限于棧的某一特定端，就是下面這樣的。
棧遵循先進後出（ last-in-first-out， LIFO ）的規律，這是重點。
棧一般使用兩種方式來實作：
- 順序表：采用順序存儲結構可以模拟棧存儲資料的特點，進而實作棧存儲結構。
- 連結清單：采用鍊式存儲結構實作棧結構。
注意，這兩種實作方式的差別，僅限于資料元素在實際實體空間上存放的相對位置，順序棧底層采用的是數組，鍊棧底層采用的是連結清單。
棧結構我們還是會經常用到，一個非常經典的場景就是在浏覽器的後退功能中。
例如我們每次打開一個頁面，浏覽器都會把這個頁面放入棧中，當我們點選後退按鈕的時候，在從棧中将這個頁面取出來。
順序棧
順序棧，是用順序表實作棧存儲結構。
棧存儲結構操作資料元素必須遵守 「先進後出 LIFO 」 的原則。
順序表的底層是使用數組來實作的，簡單了解可以直接了解成數組。
隻是棧結構對資料的存取過程有特殊的限制，而數組是沒有的。
鍊棧
鍊棧，是用連結清單實作棧存儲結構。
連結清單這個結構在前面沒聊過，簡單畫個圖大家了解下：
連結清單的結構相比較數組而言就稍微有些複雜了，連結清單的每個節點由兩部分組成，一個是存放資料的，叫資料域，另一個是存放指針的，叫指針域。
數組在記憶體中是連續的，是以我們可以輕松的知道數組的每一個元素的位置，而連結清單在記憶體中是分散的，我們需要一個指針來指明下一個元素在哪裡。
這裡介紹的其實是最簡單的一種連結清單，叫單連結清單，顧名思義，除了單連結清單之外還有雙連結清單，這個我們有機會後面再聊。
那麼鍊棧是将連結清單的頭部作為棧頂，尾部作為棧底。
将連結清單頭部作為棧頂的一端，可以避免在實作資料 「入棧」 和 「出棧」 操作時做大量周遊連結清單的耗時操作。
連結清單的頭部作為棧頂，意味着：
- 在實作資料"入棧"操作時，需要将資料從連結清單的頭部插入。
- 在實作資料"出棧"操作時，需要删除連結清單頭部的首元節點。
是以，鍊棧實際上就是一個隻能采用頭插法插入或删除資料的連結清單。
Python 實作棧
在 Python 中，棧并不是一個基礎資料結構，不過我們可以通過代碼來簡單的實作它。
因為棧是可以通過兩種方式來實作，一種是順序表，另一種是連結清單：
首先是最簡單的通過順序表來實作棧，這裡使用的是 Python 中的 list 清單：
class Stack(object):
def __init__(self):
'''
建立空清單實作棧
'''
self.__list = []
def is_empty(self):
'''
判斷是否為空
:return:
'''
return self.__list == []
def push(self,item):
'''
壓棧，添加元素
:param item:
:return:
'''
self.__list.append(item)
def pop(self):
'''
彈出棧，将元素取出
:return:
'''
if self.is_empty():
return
else:
return self.__list.pop()
如果不想使用順序表來實作，還可以使用連結清單，這裡使用的是單連結清單，連結清單的結構需要先提前定義：
class Node(object):
'''
節點實作
'''
def __init__(self,elem):
self.elem = elem
self.next = None
class Stack(object):
def __init__(self):
'''
初始化連結清單頭
'''
self.__head = None
def is_empty(self):
return self.__head is None
def push(self, item):
'''
壓棧
:param item:
:return:
'''
node = Node(item)
node.next = self.__head
self.__head = node
def pop(self):
'''
彈出棧
:return:
'''
if self.is_empty():
return
else:
p = self.__head
self.__head = p.next
return p.elem
在連結清單的實作中，我這裡先定義了連結清單的資料結構，然後才定義了棧。
上面兩段代碼都非常簡單，隻實作了最簡單的兩個功能，入棧和出棧，感興趣的同學可以自己動手實作下。
隊列
與棧一樣，隊列（ queue） 也是存放資料對象的一種容器，其中的資料對象也按線性的邏輯次序排列。
隊列和棧不一樣的地方在于棧是先進後出，而隊列是先進先出（ first-in-first-out, FIFO ）。
同棧一樣的是隊列也有兩種實作方式：
- 順序隊列：在順序表的基礎上實作的隊列結構。
- 鍊隊列：在連結清單的基礎上實作的隊列結構。
Python 中的 Queue
在 Python 的标準庫中，Python 為我們提供了線程安全的隊列 Queue （總算不用我再自己寫個隊列了），使用方法異常簡單：
先進先出隊列 （FIFO） ：
import queue
q1 = queue.Queue(maxsize=5)
for i in range(5):
q1.put(i)
while not q1.empty():
print('q1:',q1.get())
# 結果輸出
q1: 0
q1: 1
q1: 2
q1: 3
q1: 4
Queue 這個标準庫中，還為我們提供了 LIFO 隊列，即先進後出隊列，和我們前面介紹的棧非常類似，翻了下源碼，看到是使用 list 實作的，和我們上面的實作基本一緻，使用方式如下：
import queue
q2 = queue.LifoQueue(maxsize=5)
for i in range(5):
q2.put(i)
while not q2.empty():
print('q2:',q2.get())
# 結果輸出
q2: 4
q2: 3
q2: 2
q2: 1
q2: 0
本篇内容就這樣了，涉及到的代碼肯定會上傳代碼倉庫，有興趣的同學可以去翻翻看。
示例代碼
示例代碼-Github
示例代碼-Gitee
掃描二維碼關注「極客挖掘機」公衆号！作者：極客挖掘機
定期發表作者的思考：技術、産品、營運、自我提升等。
本文版權歸作者極客挖掘機和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果您覺得作者的文章對您有幫助，就來作者個人小站逛逛吧：
極客挖掘機