堆疊和佇列精華決議

一：堆疊和佇列簡介

堆疊和佇列是使用頻率最高的資料結構，堆疊和佇列是指插入和洗掉只能在表的一端進行的線性表，

從資料結構的角度來看，堆疊和佇列也是線性表，其特殊性在于堆疊和佇列的基本操作是線性表操作的子集，它們是操作受限的線性表，因此可稱為限定性的資料結構，

堆疊

先進后出（限定性操作）

堆疊具有后進先出的特性，如果問題解決具有先進后出的天然特性的話，則求解的演算法就要使用堆疊，比如：進制轉換，括號匹配，運算式求值，函式呼叫，遞回呼叫，八皇后問題，迷宮求解等，

佇列（限定性操作）

先進先出

佇列具有先進先出的特性，如果問題解決具有先進先出的特性的話，則求解的演算法就要使用佇列，比如：脫機列印操作，行程按等待時間創建優先級佇列，信號按接受的先后順序依次處理，

二：堆疊

(一)：堆疊的介紹

堆疊：限制在表的一端進行插入和洗掉運算的線性表

堆疊頂和堆疊底：允許插入、洗掉的一端稱為堆疊頂，另一端稱為堆疊底，

空堆疊：表中沒有元素稱為空堆疊

堆疊的運算規則：后進先出

添加元素時我們稱之為入堆疊或壓堆疊(push);洗掉元素稱之為出堆疊(pop)

堆疊與一般線性表的區別：

(二)：堆疊的存盤

堆疊的存盤分為順序存盤和鏈式存盤

1. 順序存盤

   ? 堆疊的本質是線性表，線性表的存盤結構對堆疊也適用，堆疊的順序存盤結構稱為順序堆疊，與順序表類似，在python中使用串列來實作順序堆疊，其它的語言使用陣列來實作順序堆疊，

   ? 堆疊底位置固定不變，堆疊頂位置隨著入堆疊和出堆疊操作而變化，用一個整型變數top存盤堆疊頂的位置，通常稱top為堆疊頂指標（實際是小標），

代碼實作：

功能函式撰寫

初始化一個空串列

def __init__():
	self.lst = []

判斷空堆疊

def is_empty(self):
	if self.lst = []:
		return True
	return False

入堆疊

時間復雜度：O(1)

因為list采用的是動態順序表技術，所以不需要判斷表會不會滿

def pushstack(self,item):
	self.append(item)
 	return item

出堆疊

時間復雜度：O(1)

def popstack(self):
 	self.pop()
 	return item

讀取堆疊頂元素

時間復雜度：O(1)

def peek(self):
	item = self.lst[-1]
	return item

完整代碼：

class Stack:

    def __init__():
        self.lst = []

    def is_empty(self):
        if self.lst = []:
            return True
        return False

    def pushstack(self,item):
        self.append(item)
        return item

     def popstack(self):
        self.pop()
        return item

     def peek(self):
        item = self.lst[-1]
        return item

2. 鏈式存盤

? 堆疊的鏈式存盤結構稱為鏈堆疊，它是運算受限的單鏈表，插入和洗掉操作僅限制在表頭位置上進行，

? 在記憶體中開辟不連續的記憶體空間，元素之間的關系是通過指標的指引來實作它前繼和后繼的關系，

? 時間復雜度為O(1)

圖解：

初始化堆疊

# 定義節點類
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

# 定義堆疊類
class LinkTack:
    def __init__(self,node=None):
        self._top = node

判斷堆疊空

def is_empty(self):
	if self._top == None:
		return True
	return False

入堆疊

def push(self,item):
	node = Node(item)
	node.next = self._top
	self._top = node

出堆疊

def pop(self):
	if self.is_empty():
		return
	else:
		p = self._top
		self._top = p.next
		return p.item

完整代碼：

# 定義節點類
class Node:
    def __init__(self,item):
        self.item = item
        self.next = None

# 定義堆疊類
class LinkTack:
    def __init__(self,node=None):
        self._top = node

    def is_empty(self):
        if self._top == None:
            return True
        return False

    def push(self,item):
        node = Node(item)
        node.next = self._top
        self._top = node

    def pop(self):
        if self.is_empty():
            return
        else:
            p = self._top
            self._top = p.next
            return p.item

(三)：鏈式存盤應用

1. 進制轉換

   • 演算法思想：若 N != 0，則將 N % r 壓入堆疊中，即將N除進制的余數壓入堆疊中
   • 用 N // r 代替 N
   • 若N=0，則將堆疊中的內容依次出堆疊，演算法結束

   # 定義堆疊類
   class LinkStack:
       def __init__(self,node=None):
           self._top = node
   
       def is_empty(self):
           if self._top == None:
               return True
           return False
   
       def push(self,item):
           node = Node(item)
           node.next = self._top
           self._top = node
   
       def pop(self):
           if self.is_empty():
               return
           else:
               p = self._top
               self._top = p.next
               return p.item
   
   if __name__ == "__main__":
       N = int(input("輸入一個待轉換的十進制數："))
       r = int(input("輸入要轉換的進制："))
       s = LinkStack()
       while N != 0:
           s.push(N % r)
           N = N // r
       while N == 0:
           item = s.pop()
           print(item,end="")
           if s.is_empty():
               break
       print()
   

（四）：堆疊與遞回

函式堆疊：

? 堆疊里面每一層都裝函式的堆疊就是函式堆疊，呼叫一個函式的時候，這個函式就入堆疊，這個函式呼叫完成了(執行到了函式的最后一個陳述句或者說return)，就出堆疊，

堆疊與子程式的呼叫：

? 在高級語言和匯編語言編制的程式中，子程式(函式等)的呼叫和回傳處理，在編譯系統中都是采用堆疊來實作的，

? 當在一個主程式呼叫一個子程式時，在運行該主程式前，需先將子程式之前的所有中間結果、回傳地址等保存在堆疊中，子程式呼叫結束后將堆疊中的資料取出

? 多個子程式嵌套呼叫的規則是：后呼叫-先回傳，記憶體管理實行堆疊式管理

圖解：

代碼：

def fuc(n):
    if n == 1:
        return 1
    else:
        return fuc(n-1) * n

if __name__ == "__main__":
    print(fuc(4))

三：佇列

(一)：佇列的定義及運算

佇列(Queue)：運算受限的線性表，它只允許在表的一端進行插入，而在另一端進行洗掉，

隊頭(front)和隊尾(rear)：允許洗掉的一端稱為隊頭，允許插入的一端稱為隊尾

佇列的運算規則：先進先出(FIFO)

佇列的存盤結構：

• 順序對壘-----回圈佇列
• 鏈佇列

(二)：順序佇列基本操作----回圈佇列

? 佇列的順序存盤結構與順序表相似，用連續的存盤空間存放當前佇列中的元素，另設兩個指標分別指示隊頭和隊尾元素在最烈中的位置，

? 通常順序存盤的佇列采用回圈佇列結構

? 隊頭指標(front)：指向隊頭元素所在的位置，初始為空時，隊頭指標為0；出隊時，取出隊頭元素，然后將隊頭指標加1(并回傳被刪元素)

? 隊尾指標(rear)：指向隊尾元素，初始為空時，隊頭指標為0；入隊時，先將新元素插入到隊尾，再將隊尾指標加1

入隊程序：先將入隊元素放在rear指標的位置，然后再將rear指標向上移動一位

出隊程序：先將隊頭元素取出，然后將front指標向上移動一位

圖解：

創建一個3個長度的對列，當對列的長度占滿后，新進入的變數會存放到對列已出去元素的位置上，這就稱為回圈佇列，

順序佇列結構存在的問題：

• 設順序表容量為M，則：
• 當front=0,rear=M-1時，再有元素入隊發生溢位-------真溢位
• 當front=0,rear=M-1時，再有元素入隊發生溢位-------假溢位

回圈佇列：

? 將佇列首尾連接成環形進行使用，讓queue[0]接在queue[M-1]之后，若rear+1 == M，則令rear = 0

演算法思想

? 在回圈佇列中進行出隊/入隊操作時，頭尾指標仍要加1，向上移動，只不過頭/尾指標指向佇列上界(M-1)時，其加1操作的結果是指向向量的下界0，

? 用代碼描述為：

if i+1 == M:
	i=0
else:
	i += 1

? 利用模運算可將其簡化為：

i = (i+1) % M

利用求模運算表示入隊、出隊時指標的變化：

• 入隊：rear = (rear+1) % M
• 出隊：front = (front+1) % M

判斷佇列為慷訓滿

問題：

如上圖所示，佇列為慷訓滿時的front和rear的指標都指向同一個空間，是無法判斷是慷訓是滿的，

解決：

少用一個元素空間，即

• 隊空：front == rear
• 隊滿：(rear+1)%M == front

圖解

代碼實作回圈佇列：

class Queue:
    # 初始化
    def __init__(self,maxsize):
        # 定義一個一定空間的串列
        self.queue = [None] * maxsize
        # 串列的最大值
        self.maxsize = maxsize
        # 頭指標初始值為0
        self.front = 0
        # 尾指標初始值為0
        self.rear = 0

    # 入隊
    # 時間復雜度為O(1)
    def in_queue(self,item):
        # 判斷隊是否為滿
        if (self.rear+1) % self.maxsize == self.front:
            print("隊已滿，無法插入")
        else:
            # 隊尾指標處插入元素
            self.queue[self.rear] = item
            # 指標向上移動一位
            self.rear = (self.rear +1) % self.maxsize
    
    # 出隊
    def out_queue(self):
        # 判斷隊是否為空
        if self.rear == self.front:
            print("隊已空，無法取出元素")
        else:
            # 取隊頭元素
            front_item = self.queue[self.front]
            # 指標向后移動一位
            self.front = (self.front + 1) % self.maxsize
            # 回傳隊頭元素
            return front_item

    # 求隊中元素的個數
    def queue_nums(self):
        nums = (self.front + self.maxsize - self.rear) % self.maxsize
        return nums

    # 遍歷佇列
    def serch(self):
        # 新設一個隊頭指標
        cur = self.front
        # 隊頭和隊尾是否相遇
        while cur != self.rear:
            print(self.queue[cur])
            # 指標后移
            cur = (cur + 1) % self.maxsize

(三)：鏈佇列基本操作

鏈佇列：限制僅在表頭進行洗掉和表尾進行插入的單鏈表，一個鏈佇列由一個頭指標和尾指標唯一確定，

定義鏈佇列中的資料節點類

# 定義節點類
class QueueNode:
    def __init__(self.item):
        self.item = item
        self.next = None

定義鏈佇列中的表頭節點類

# 定義鏈表頭節點類
class QueueHead:
    def __init__(self):
        self.front = None
        self.rear = None

定義一個鏈佇列類

# 定義一個鏈佇列類
class QueueLink:
    def __init__(self):
        self._head = QueueHead()

判斷佇列是否為空

圖解：

代碼實作：

def is_empty(self):
	if self._head.front == self._head_rear and self._head.front == None:
		return True
	else:
		return False

元素入隊

在隊尾添加元素，修改隊尾指標

特殊情況：當佇列為空時，不僅要修改隊尾指標也要修改隊頭指標

圖解：

代碼實作：

def in_queue(self):
	# 創建節點
	node = QueueNode()
	# 判斷是否為空
	if self.is_empty():
	# 如果為空則隊頭和隊尾指標都指向這個節點
		self._head.front = node
		self._head.rear = node
	else:
		# 添加元素
		self._head.rear.next = node
		# 移動指標
		self._head.rear = node

出隊

將頭指標指向頭部元素的next即可完成出隊

特殊情況：當隊內只有一個元素時，需同時修改隊頭和隊尾元素的指標為空

圖解：

代碼實作：

def out_queue(self):
	# 隊空
	if self.is_empty():
	print("佇列已空")
    
	# 隊中只含一個元素
	if self._head.front == self._head.rear and self._head.front != None:
		# 取對頭元素
		p = self._head.front 
		# 將頭指標和尾指標指向None
		self._head.front = None
		self._head.rear = None
		return p.item
	else:  # 含有多個節點
		# 取隊頭元素
		p = self._head.front
		# 移動指標
		self._head.front = self._head.front.next
		return p.item

完整代碼：

class QueueNode:
    def __init__(self,item):
        self.item = item
        self.next = None

class QueueHead:
    def __init__(self):
        self.front = None
        self.rear = None

class QueueLink:
    def __init__(self):
        self._head = QueueHead()

    def is_empty(self):
        if self._head.front == self._head.rear and self._head.front == None:
            return True
        else:
            return False

    def in_queue(self,item):
        node = QueueNode(item)
        if self.is_empty():
            self._head.front = node
            self._head.rear = node
        else:
            self._head.rear.next = node
            self._head.rear = node
    
    def out_queue(self):
        if self.is_empty():
            print("佇列已空")        
        if self._head.front == self._head.rear and self._head.front != None:
            p = self._head.front 
            self._head.front = None
            self._head.rear = None
            return p.item
        else:  # 含有多個節點
            p = self._head.front
            self._head.front = self._head.front.next
            return p.item

_head.front = node
self._head.rear = node
else:
self._head.rear.next = node
self._head.rear = node

def out_queue(self):
    if self.is_empty():
        print("佇列已空")        
    if self._head.front == self._head.rear and self._head.front != None:
        p = self._head.front 
        self._head.front = None
        self._head.rear = None
        return p.item
    else:  # 含有多個節點
        p = self._head.front
        self._head.front = self._head.front.next
        return p.item