資料結構與C++程式設計進階 堆疊與佇列(Stack & Queue) 講師：林業峻 CSIE, NTU 6/ 21, 2010

堆疊與佇列 堆疊(Stack) 佇列(Queue) 加入(push)與刪除(pop)於同一端 用途：後進先出(LIFO)之資料特性 例子：遞迴、走迷宮、深度優先搜尋 佇列(Queue) 加入(enqueue)與刪除(dequeue)於不同端(front & rear) 用途：先進先出(FIFO)之資料特性 應用：排隊問題、資源使用順序控制

大綱 堆疊 (Stack) 陣列表示法 串列表示法 應用：走迷宮程式 佇列 (Queue) 應用：優先佇列

堆疊結構表示法(陣列) (stack_array.c) 堆疊表示法 加入堆疊 取出堆疊 top: 2 stack 資料1 資料2 資料3 MAX_SIZE: 6 [0] [1] [2] [3] [4] [5] 資料4 top: 3 stack 資料1 資料2 資料3 資料4 MAX_SIZE: 6 [0] [1] [2] [3] [4] [5] top: 2 stack 資料1 資料2 資料3 MAX_SIZE: 6 [0] [1] [2] [3] [4] [5] 資料4

堆疊結構表示法(陣列) 加入堆疊 int push(node data) { if(top == MAX_SIZE-1) //判斷堆疊是否已滿 return 0; //回傳存入失敗!(堆疊已滿) } top++; //移動堆疊結尾位置 stack[top] = data; //存入資料 return 1; //回傳存入成功!

堆疊結構表示法(陣列) 取出堆疊 int pop(node *data) { if(top == -1) //判斷堆疊是否為空的 return 0; //回傳取出失敗!(堆疊為空) } *data = stack[top]; //取出資料 stack[top].data = 0; //清除內容 top--; //移動堆疊結尾位置 return 1; //回傳存入成功!

堆疊結構表示法(鏈結串列) (stack_list.c) 堆疊表示法 加入堆疊 取出堆疊 stack 資料3 資料2 資料1 NULL stack 資料4 資料3 資料2 資料1 NULL stack 資料4 資料3 資料2 資料1 NULL

堆疊結構表示法(鏈結串列) 加入堆疊 void push(node data) { node *new_node; new_node = (node *)malloc(sizeof(node)); *new_node = data; //堆疊資料存入 new_node->next = stack; //取得新的堆疊起點 stack = new_node; //插入 }

堆疊結構表示法(鏈結串列) 取出堆疊 int pop(node *data) { node *top; if( stack != NULL ) //判斷堆疊是否為空的 top = stack; stack = stack->next; *data = *top; //取得資料 free(top); return 1; //回傳取得成功! } else return 0; //回傳取得失敗!(堆疊為空)

走迷宮問題 (stack_maze.c) 使用堆疊結構實作走迷宮問題 … 走法: 每次都把目前位置存到堆疊, 然後走下一步 下一步順序: 上,下,左,右 無路可走: 從堆疊中取出上一位置, 看看有沒路走 堆疊大小: ? 出口 (1,1) 1 1 1 1 1 1 1 1 1 1 走錯： 座標pop出去 1 1 1 1 (1,1) 1 1 1 1 1 1 1 1 1 1 1 1 … 1 1 1 1 1 1 1 1 1 (7,4) 走一步： 座標push入堆疊 入口 (8,5) (7,5) 1 1 1 1 1 1 1 1 1 1 (8,5)

走迷宮問題 走迷宮結果 1 1 1 1 1 1 1 1 1 1 1 2 1 3 1 3 3 3 3 1 1 2 1 3 1 3 1 1 3 1 1 2 1 3 1 1 1 3 3 1 1 2 1 2 2 2 2 2 1 1 1 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1

練習 將上一迷宮問題範例解答之路徑座標印出

大綱 堆疊 (Stack) 陣列表示法 串列表示法 應用：走迷宮程式 佇列 (Queue) 應用：優先佇列

佇列結構表示法(陣列) (queue_array.c) 佇列表示法 加入佇列 取出佇列 front: -1 rear: 2 MAX_SIZE: 6 size: 3 queue 資料1 資料2 資料3 [0] [1] [2] [3] [4] [5] 資料4 front: -1 rear: 3 MAX_SIZE: 6 size: 4 queue 資料1 資料2 資料3 資料4 [0] [1] [2] [3] [4] [5] front: 0 rear: 3 MAX_SIZE: 6 size: 3 queue 資料2 資料3 資料4 [0] [1] [2] [3] [4] [5] 資料1

佇列結構情況判斷(陣列) 佇列為空 佇列已滿 front: 3 rear: 3 MAX_SIZE: 6 size: 0 queue [0] [1] [2] [3] [4] [5] front: 2 rear: 2 MAX_SIZE: 6 size: 6 queue 資料4 資料5 資料6 資料1 資料2 資料3 [0] [1] [2] [3] [4] [5]

佇列結構表示法(陣列) 加入佇列 int enqueue(node data) { if( size == MAX_SIZE ) // 檢查佇列是否已滿 return 0; // 存入佇列失敗!(佇列已滿) rear++; // 移動佇列尾的位置 size++; // 佇列容量+1 if(rear==MAX_SIZE) // 檢查是否超過界限 rear = 0; // 重頭開始 queue[rear] = data; // 存入佇列 return 1; // 存入佇列成功! }

佇列結構表示法(陣列) 取出佇列 int dequeue(node *data) { if(size == 0) // 檢查佇列是否是空的 return 0; // 取出佇列失敗!(佇列為空) front++; // 移動佇列頭的位置 size--; // 佇列容量-1 if(front==MAX_SIZE) // 檢查是否超過界限 front = 0; // 重頭開始 *data = queue[front]; // 取出佇列資料 queue[front].data = 0; // 清除內容 return 1; // 取出佇列成功! }

佇列結構表示法(鏈結串列) (queue_list.c) 佇列表示法 加入佇列 取出佇列 queue 資料1 資料2 資料3 NULL rear front queue 資料1 資料2 資料3 資料4 NULL rear front queue 資料1 資料2 資料3 資料4 NULL rear front

佇列結構表示法(串列) 加入佇列 void enqueue(node data) { node *new_node; new_node = (node *)malloc(sizeof(node)); *new_node = data; //儲存新節點內容 new_node->next = NULL; if(front==NULL) //插頭 front = new_node; else //插尾 rear->next = new_node; rear = new_node; //取得佇列新結尾 }

佇列結構表示法(串列) 取出佇列 //取出節點 int dequeue(node *data) { node *top; if(front != NULL) top = front; front = front->next; //取得佇列新起點 *data = *top; //儲存節點內容 free(top); //刪除頭 return 1; //回傳取得成功! } else return 0; //回傳取得失敗!(佇列為空)

練習 改寫鏈結串列佇列程式(queue_list.c),設定練節串 列堆疊結構之節點最大值為6

優先佇列 優先佇列 (Priority Queues) (queue_priority.c) 資料排入佇列順序不一定是先到先贏, 而是根據優先權來插入 佇列之中 例如資料有兩種優先等級(A,B級), 如果有個A級資料需要插入 佇列, 應該將它插到目前佇列中A級資料之後, 與所有B級資料 之前 queue A1 A2 B1 B2 NULL front rear_a rear_b A級會員 B級會員

加入佇列 目前有同級會員 B2 new_node NULL queue A1 A2 B1 NULL front rear_a rear_b

加入佇列 目前無同級會員 前有更高級會員 前無更高級會員 rear_b B級會員 B1 new_node NULL queue A1 A2 front rear_a A級會員 rear_a A1 new_node A級會員 B1 B2 queue NULL NULL front rear_b B級會員

取出佇列 目前有多個同級會員 目前只有一個同級會員 queue A1 A2 B1 B2 NULL front rear_a rear_b