datastructureinc堆叠与伫列.ppt

Data Structure in C  ─ 堆疊與佇列 大綱 堆疊 基本概念 堆疊的加入與刪除 佇列 基本概念 佇列的加入與刪除 環狀佇列 其他型式的佇列 多個堆疊和多個佇列 堆疊與佇列的應用 堆疊 堆疊(stack) 為一有序串列(order list)，其加入(insert)和刪除(delete)動作都在同一端，此端通常稱之為頂端(top) 給予一個堆疊S=(a0, a1, …, an-1)，a0為底端元素、 an-1為頂端元素，且元素ai在元素ai-1之上，0in 加入一個元素於堆疊，此動作稱為推入(push)；從堆疊中刪除一個元素，此動作稱為彈出(pop) 堆疊 (續) 由於堆疊具有先進去的元素最後才會投出來的特性，所以堆疊又稱為後進先出(Last In First Out, LIFO)串列 堆疊 (續) 堆疊的加入(push) void push_f(void) { if(top = MAX-1) /* 當堆疊已滿，則顯示錯誤 */ printf(\n\nStack is full !\n); else { top++; printf(\n\n Please enter item to insert: ); gets(item[top]); } } 堆疊 (續) 堆疊的刪除(pop) void pop_f(void) { if(top 0) /* 當堆疊沒有資料存在，則顯示錯誤 */ printf(\n\n No item, stack is empty !\n); else { printf(\n\n Item %s deleted\n, item[top]); top--; } } 佇列 佇列(Queue) 為一有序串列(order list)，其中所有的插入發生在串列的一端，所有的刪除發生在串列的另一端 給予一個佇列Q=(a0, a1, …, an-1)，a0為前端元素、 an-1為後端元素，且元素ai在元素ai-1之上，0in 由於佇列具有先進去的元素亦會最先投出來的特性，所以佇列又稱為先進先出(First In First Out, FIFO)串列 佇列 (續) 佇列 (續) 佇列的加入 void enqueue_f(void) { if(rear = MAX-1) /* 當佇列已滿，則顯示錯誤 */ printf(\n\nQueue is full !\n); else { rear++; printf(\n\n Please enter item to insert: ); gets(item[rear]); } } 佇列 (續) 佇列的刪除 void dequeue_f(void) { if(front rear) /* 當資料沒有資料存在，則顯示錯誤 */ printf(\n\n No item, queue is empty !\n); else { printf(\n\n Item %s deleted\n, item[front]); front++; } } 佇列 (續) 佇列的表示方式是Q(1 : n)時，常常會發生佇列前端還有空位，但要加入元素時卻發現此佇列已滿的情形 為解決此問題，佇列常常以環狀佇列(circle queue)的方式來表示CQ(0 : n-1) 佇列 (續) 環狀佇列的加入 void enqueue_f(void) { rear = (rear + 1) % MAX; if(front == rear) { if(rear == 0) rear = MAX-1; /*退回原位*/ else rear == rear-1; /*退回原位*/ printf(\n\nQueue is full !\n);} else {printf(\n\n Please enter item to insert: ); scanf(%d“,cq[rear]);} } 佇列 (續) 環狀佇列的刪除 void dequeue_f(void) { if(front == rear) printf(\n\n No item, queue is empty !\n); else { front = (front + 1) % MAX; printf(\n\n Item %s deleted\n, cq[front]); } } 佇列 (續) 環狀佇列的加入 ─ 使用TAG變數