上回說到，棧常見的三個應用：括号比對、表達式求值以及遞歸。這一會我們來看一看另一個操作受限的線性表：隊列！
隊列的基本概念
隊列的定義
隊列（Queue）簡稱隊，也是一種操作受限的線性表，隻允許在表的一端進行插入，而在表的另一端進行删除。向隊列中插入元素稱為入隊或進隊；删除元素稱為出隊或離隊。這和我們日常生活中的排隊是一緻的，最早排隊的也是最早離隊的，其操作特性是先進先出（First In Last Out，FIFO）。
隊頭（Front）。允許删除的一端，又稱隊首。
隊尾（Rear）。允許插入的一端。
空隊列。不含任何元素的空表。
隊列常見的基本操作
__init__(self)：初始化隊列，構造一個空隊列 self。
is_empty(self)：判隊列空，若隊列 self 為空傳回 True，否則傳回 False。
en_queue(self, x)：入隊，若隊列 self 未滿，将 x 加入，使之成為新的隊尾。
de_queue(self)：出隊，若隊列 self 非空，删除隊頭元素，并傳回。
get_head(self)：讀隊頭元素，若隊列 self 非空，則将隊頭元素傳回。
隊列的順序存儲結構
隊列的順序存儲
隊列的順序實作是指配置設定一塊連續的存儲單元存放隊列中的元素，并附設兩個指針：隊頭指針 front 指向隊頭元素，隊尾指針 rear 指向隊尾元素的下一個位置。
隊列的順序存儲類型可描述為
class SqQueue:
def __init__(self, max_size=50):
self.max_size = max_size # 定義隊列中元素的最大個數
self.data = [None]*max_size # 存放隊列元素
self.front = self.rear = 0 # 隊頭指針和隊尾指針
複制
初始狀态（隊空條件）：self.front==self.rear==0。
進隊操作：隊不滿時，先送值到隊尾元素，再将隊尾指針加 1。
出隊操作：隊不空時，先取隊頭元素值，再将隊頭指針加 1。
圖（a）所示為隊列的初始狀态，有 self.front==self.rear==0 成立，該條件可以作為隊列判空的條件。但能否用 self.rear==self.max_size 作為隊列滿的條件呢？顯然不能，圖（c）中，隊列中僅有一個元素，但仍滿足該條件。這時入隊出現“上溢出”，但這種溢出并不是真正的溢出，在 self.data 數組中依然存在可以存放元素的空位置，是以是一種“假溢出”。
循環隊列
前面已指出了順序隊列的缺點，這裡引出循環隊列的概念。将順序隊列臆造為一個環狀的空間，即把存儲隊列元素的表從邏輯上視為一個環，稱為循環隊列。當隊首指針 self.front=self.max_size-1 後，再前進一個位置就自動到 0，這可以利用除法取餘運算（%）來實作。
初始時：self.front=self.rear=0。
隊首指針進 1：self.front=(self.front+1)%self.max_size。
隊尾指針進 1：self.rear=(self.rear+1)%self.max_size。
隊列長度：(self.rear+self.max_size-self.front)%self.max_size。
那麼，循環隊列隊空和隊滿的判斷條件是什麼呢？顯然隊空的條件是 self.front==self.rear。若入隊元素的速度快于出隊元素的速度，則隊尾指針很快就會趕上隊首指針，此時可以看出隊滿時也有 self.front==self.rear。
為了區分隊空還是隊滿的情況，有三種處理方式：
- 犧牲一個單元來區分隊空和隊滿，入隊時少用一個隊列單元，這是一種較為普遍的做法，約定以“隊頭指針在隊尾指針的下一位置作為隊滿的标志”。隊滿條件：(self.rear+1)%self.max_size==self.front。隊空條件仍：self.front==self.rear。隊列中元素的個數：(self.rear-self.front+self.max_size)%self.max_size。
- 類型中增設表示元素個數的資料成員，這樣，隊空的條件為 self.size==0；隊滿的條件為 self.size==self.max_size。這兩種情況都有 self.front==self.rear。
- 類型中增設 tag 資料成員，以區分隊滿還是隊空。self.tag 等于 0 時，若因删除導緻 self.front==self.rear，則為隊空；self.tag 等于 1 時，若因插入導緻 self.front==self.rear，則為隊滿。
循環隊列的操作
初始化
def __init__(self, max_size=50): # 初始化
self.max_size = max_size # 定義隊列中元素的最大個數
self.data = [None]*max_size # 存放隊列元素
self.front = self.rear = 0 # 隊頭指針和隊尾指針
複制
判隊空
def is_empty(self): # 判隊空
if self.rear == self.front: # 隊空條件
return True
return False
複制
入隊
def en_queue(self, x): # 入隊
if (self.rear+1) % self.max_size == self.front: # 隊滿則報錯
return
self.data[self.rear] = x
self.rear = (self.rear+1) % self.max_size # 隊尾指針加 1 取模
複制
出隊
def de_queue(self): # 出隊
if self.rear == self.front: # 隊空則報錯
return
x = self.data[self.front]
self.front = (self.front+1) % self.max_size # 隊頭指針加 1 取模
return x
複制
讀隊頭元素
def get_head(self): # 讀隊頭元素
if self.front == self.rear:
return
return self.data[self.front]
複制
隊列的鍊式存儲結構
隊列的鍊式存儲
隊列的鍊式表示稱為鍊隊列，它實際上是一個同時帶有隊頭指針和隊尾指針的單連結清單。頭指針指向隊頭結點，尾指針指向隊尾結點，即單連結清單的最後一個結點（注意與順序存儲的不同）。
隊列的鍊式存儲類型可描述為
class LinkNode: # 鍊式隊列結點
def __init__(self, data=0):
self.data, self.next = data, None
class LinkQueue: # 鍊式隊列
def __init__(self):
self.front = self.rear = LinkNode() # 隊列的隊頭和隊尾指針
複制
當 self.front==None 且 self.rear==None 時，鍊式隊列為空。
出隊時，首先判斷隊是否為空，若不空，則取出隊頭元素，将其從連結清單中摘除，并讓 self.front 指向下一個結點（若該結點為最後一個結點，則置 self.front 和 self.rear 都為 None）。入隊時，建立一個新結點，将新結點插入到連結清單的尾部，并改讓 self.rear 指向這個新插入的結點（若原隊列為空隊，則令 self.front 也指向該結點）。
不難看出，不帶頭結點的鍊式隊列在操作上往往比較麻煩，是以通常将鍊式隊列設計成一個帶頭結點的單連結清單，這樣插入和删除操作就統一了。
用單連結清單表示的鍊式隊列特别适合于資料元素變動較大的情形，而且不存在隊列滿且産生溢出的問題。另外，假如程式中要使用多個隊列，最好使用鍊式隊列，這樣就不會出現存儲配置設定不合理和“溢出”的問題。
鍊式隊列的基本操作
初始化
def __init__(self): # 初始化
self.front = self.rear = LinkNode() # 隊列的隊頭和隊尾指針
複制
判隊空
def is_empty(self): # 判隊空
return True if self.front == self.rear else False
複制
入隊
def en_queue(self, x): # 入隊
s = LinkNode(x) # 建立新結點，插入到鍊尾
self.rear.next = s
self.rear = s
複制
出隊
def de_queue(self):
if self.front == self.rear: # 空隊
return
p = self.front.next
x = p.data
self.front.next = p.next
if self.rear == p:
self.rear = self.front # 若原隊列中隻有一個結點，删除後變空
return x
複制
讀隊頭元素
def get_head(self):
if self.front == self.rear:
return
return self.front.next.data
複制
雙端隊列
雙端隊列是指允許兩端都可以進行入隊和出隊操作的隊列。其元素的邏輯結構仍是線性結構。将隊列的兩端分别稱為前端和後端，兩端都可以入隊和出隊。
在雙端隊列進隊時，前端進的元素排列在隊列中後端進的元素的前面，後端進的元素排列在前端進的元素的後面。在雙端隊列出隊時，無論是前端還是後端出隊，先出的元素排列在後出的元素的前面。
輸出受限的雙端隊列：允許在一端進行插入和删除，但在另一端隻允許插入的雙端隊列稱為輸出受限的雙端隊列。
輸入受限的雙端隊列：允許在一端進行插入和删除，但在另一端隻允許删除的雙端隊列稱為輸入受限的雙端隊列。
總結
關于隊列的定義以及基本操作的實作就介紹到這裡，下回我們看到隊列的應用。
當然，我從今年開始已經入駐 B 站了！下面給出 B 站賬号：新時代的運籌帷幄，喜歡的可以關注一下，看完視訊不要忘記一鍵三連啊！