使用C语言2堆叠与伫列.PPT

Chapter 3 堆疊與佇列 3.1 堆疊和佇列基本觀念 3.2 堆疊的加入與刪除 3.3 佇列的加入與刪除 3.4 其他型式的佇列 3.5 多個堆疊 3.6 堆疊與佇列的應用 3.7 如何計算後序表示式 堆疊與佇列 堆疊與佇列是資料結構最基本的二個主題，您將會體會以前您所學到的副程式的呼叫，它們是怎麼處理的，為何會有條不紊，不會出差錯。中序的表示式與後序的表示式有何不同，它們之間應如何轉換。 3.1 堆疊和佇列基本觀念 堆疊是一有序串列（order list），其加入（insert）和刪除（delete）動作都在同一端，此端通常稱之為頂端（top）。 加入一元素於堆疊，此動作稱為推入（push），與之相反的是從堆疊中刪除一元素；此動作稱為彈出（pop）。 由於堆疊具有先進去的元素最後才會被搬出來的特性，所以又稱堆疊是一種後進先出（Last In First Out，LIFO）串列。 3.1 堆疊和佇列基本觀念 佇列也是屬於線性串列，與堆疊不同的是加入和刪除不在同一端，刪除的那一端為前端（front），而加入的一端稱為後端（rear）。 由於佇列具有先進先出（First In First Out，FIFO）的特性，因此也稱佇列為先進先出串列，假若佇列兩端皆可做加入或刪除的動作，則稱之為雙佇列（double-ended queue,deque）。 3.1 堆疊和佇列基本觀念 堆疊、佇列如圖3.1之(a)、(b)所示。 3.1 堆疊和佇列基本觀念 其中(a)堆疊有如一容器，而(b)的佇列有如一排隊的隊伍，最前面的是front所指的地方，因此front所指的位置一定會先被服務，而rear所指的地方是新加入的位置。 3.2 堆疊的加入與刪除 在堆疊的運作上，堆疊的加入必須注意加入的元素是否會超出堆疊的最大容量，因此設定一變數查看它是否超出，每次push 一個元素則top 加1；反之，pop 一個元素則top 減1。我們可以利用一陣列來表示堆疊，如：stack[MAX]，其中MAX 表示堆疊的最大容量。 初始的top 設為–1。 3.2 堆疊的加入與刪除 3.2.1堆疊的加入 堆疊的加入應注意堆疊是否為滿的情況，若沒滿，則將輸入的資料放在堆疊的上方。 3.2 堆疊的加入與刪除 3.2.1堆疊的刪除 堆疊的刪除應注意堆疊是否為空的，若不是空的，則將資料刪除之。 3.3 佇列的加入與刪除 佇列的運作，分別利用rear 變數作用在加入的動作；front 變數作用在刪除的動作，佇列的加入要注意它是否超出最大的容量，rear 變數的初值為–1。注意！先將rear 加1 之後，再加入資料喔!而front 變數之初值為0，刪除的動作是先刪除資料後再將front 加1。 3.3 佇列的加入與刪除 3.3.1佇列的加入 佇列的加入是作用在rear 端 3.3 佇列的加入與刪除 3.3.2佇列的刪除 佇列的刪除是作用在front 端 3.3 佇列的加入與刪除 當佇列的表示方式是Q(1：n)時，常常會發生佇列前端還有空位，但要加入元素時卻發現此佇列已滿的情形，如下圖所示： 3.3 佇列的加入與刪除 為了解決此一問題，佇列常常以環狀佇列(circle queue)來表示之，CQ(0: n-1)，如圖所示： 3.3 佇列的加入與刪除 3.3.3 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述 rear=(rear+1) % MAX; 3.3 佇列的加入與刪除 環狀佇列開始的時候，將front 與rear 之初值均設為MAX–1。 3.3 佇列的加入與刪除 3.3.3 環狀佇列的刪除 環狀佇列之刪除與之前的線性佇列有所不同 3.3 佇列的加入與刪除 是環狀佇列的加入是先找一位置，然後做判斷；但其刪除則是先做判斷，然後再找位置。還有一點要留意的是在環狀佇列永遠會空一個位置，乃是為了辨別是否已額滿或空的。如下圖：假設此環狀佇列cq[]中有10 個元素。 3.3 佇列的加入與刪除 1. front 在cq[9]，經過多次的加入後rear 在cq[8]。 2. 加一元素此時(8+1) % 10 = 9，因此rear 指向cq[9]的地方。 3. 此時rear == front，因此輸出Queue is full!，但是從圖得知front 指的位置是空的。假設要繼續使用此空間的話，則下次在刪除環狀佇列的元素時會產生佇列是空的訊息(根據上述的片段程式，當front == rear 時，會顯示Queue is empty!)，這與有許多的元素在環狀佇列中有所不符了。所以環狀佇列會浪費一個空間。 假使一定非用此