目錄

二、隊列

（一）、定義

1. 定義

2. 邏輯結構

3. 存儲結構

4. 運算規則

5. 實現方式

（二）、隊列與一般線性表的區別

一般線性表???????????????????????????????????????????

隊列

（三）、分類

1、順序隊列：隊列的順序表示（用一維數組）

1.1隊列的順序表示－－用一維數組base[M]

存在問題

2、循環隊列

2.1 循環隊列初始化

?2.2判斷對空

2.3、循環隊列入隊----環狀位移要取余

2.4、獲取隊首元素

3.鏈式隊列：用單鏈表表示

3.1判斷隊空

3.2、鏈式入隊

?3.3、鏈式隊列出隊

?3.4、獲取隊首元素

---

二、隊列

（一）、定義

1. 定義

只能在表的一端（隊尾）進行插入，在另一端（隊首或隊頭）進行刪除運算的線性表

2. 邏輯結構

與線性表相同，仍為一對一關系

3. 存儲結構

用順序隊列或鏈式隊列存儲均可

4. 運算規則

先進先出（FIFO）

5. 實現方式

關鍵是編寫入隊和出隊函數，具體實現依順序隊或鏈隊的不同而不同

（二）、隊列與一般線性表的區別

隊列是一種特殊（操作受限）的線性表

區別：僅在于運算規則不同

一般線性表???????????????????????????????????????????

邏輯結構：一對一????????????????????

存儲結構：順序表、鏈表????????

運算規則：隨機、順序存取

隊列

邏輯結構：一對一????????????????????

存儲結構：順序隊列、鏈式隊列

運算規則：先進先出

（三）、分類

1、順序隊列：隊列的順序表示（用一維數組）

利用一組連續的存儲單元(一維數組) 依次存放從隊首到隊尾的各個元素，稱為順序隊列。

順序隊列定義如下：
class SeqQueue:def __init__(self, max):self.max = max 	# 隊列最大容量# 存儲隊列元素的數組self.data = [None for i in range(self.max)]self.front = 0	 # 隊首指針self.rear = 0 	 # 隊尾指針

1.1隊列的順序表示－－用一維數組base[M]

入隊和出隊

存在問題

真假溢出

解決辦法-----循環隊列?

2、循環隊列

?

2.1 循環隊列初始化

class CircleQueue(object):def __init__(self,max):# 隊列最大容量self.max = max# 存儲隊列元素的數組self.data = [None for i in range(self.max)]# 隊首指針self.front = 0# 隊尾指針self.rear = 0

?2.2判斷對空

class CircleQueue(object):def __init__(self,max):# 隊列最大容量self.max = max# 存儲隊列元素的數組self.data = [None for i in range(self.max)]# 隊首指針self.front = 0# 隊尾指針self.rear = 0

2.3、循環隊列入隊----環狀位移要取余

def push(self,val):''':Desc  入隊         :param  val:待入隊關鍵字'''# 如果隊列滿了，拋出異常if (self.rear + 1) % self.max == self.front:raise IndexError("隊列為滿")# 在隊尾插入新的關鍵字self.data[self.rear] = val# 修改隊尾指針self.rear = (self.rear + 1) % self.max

2.4循環隊列出隊

def pop(self):''':Desc 將隊首元素出隊'''# 如果隊列為空，拋出異常if self.empty():raise IndexError("隊列為空")# 隊列不為空，獲取隊首元素cur = self.data[self.front]# 修改隊首指針，指向下一個位置self.front = (self.front + 1) % self.max# 返回原隊首元素return cur

2.4、獲取隊首元素

def pop(self):''':Desc 將隊首元素出隊'''# 如果隊列為空，拋出異常if self.empty():raise IndexError("隊列為空")# 隊列不為空，獲取隊首元素cur = self.data[self.front]# 修改隊首指針，指向下一個位置self.front = (self.front + 1) % self.max# 返回原隊首元素return cur

3.鏈式隊列：用單鏈表表示

設立一個隊首指針front ，指向隊首元素。

初始化：front=None。

入隊：判斷隊列是否為空。如果隊列為空，將隊首指針指向待插入的新節點。若隊列不為空，則遍歷到隊尾元素，將新節點插入到隊尾。

出隊：首先判斷隊列是否為空，若是隊列為空，則拋出異常；否則，刪除隊首節點。

隊列為空：front is None。

class Node(object):def __init__(self,data):''':Desc   隊列節點存儲結構'''# 數據域self.data = data# 指針域self.next = None

class LinkedQueue(object):def __init__(self):''':Desc   隊列初始化'''# 隊首指針指向空self.front = None

3.1判斷隊空

class LinkedQueue(object):def __init__(self):''':Desc   隊列初始化'''# 隊首指針指向空self.front = None

3.2、鏈式入隊

入隊：判斷隊列是否為空。如果隊列為空，將隊首指針指向待插入的新節點。若隊列不為空，則遍歷到隊尾元素，將新節點插入到隊尾。

def push(self,val):''':Desc 將關鍵字入隊     :param  val: 關鍵字'''# 新節點new = Node(val)# 如果隊列為空if self.front == None:# 將隊首指針指向新節點self.front = new# 如果隊列不為空else:# 聲明cur指針cur = self.front# 通過cur指針遍歷隊列while cur.next != None:cur = cur.next# 在隊尾插入元素cur.next = new

?3.3、鏈式隊列出隊

出隊：首先判斷隊列是否為空，若是隊列為空，則拋出異常；否則，刪除隊首節點

def pop(self):''':Desc  將隊首元素出隊'''# 如果隊列為空，拋出異常if self.empty():raise IndexError("隊列為空")# 如果隊列不為空else:cur = self.front# 將隊首指針指向隊首節點的后繼節點self.front = self.front.next# 返回原本隊首節點return cur

?3.4、獲取隊首元素

peek(self):''':Desc  獲取隊首元素        :return:  返回隊首元素'''# 如果隊列為空，拋出異常if self.empty():raise IndexError("隊列為空")# 如果隊列不為空else:# 返回隊首元素return self.front