資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.

Presentation on theme: "資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用."— Presentation transcript:

1 資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用 版權所有 禁止重製

2 佇列 佇列(Queue) 佇列也是一個有序串列 資料的插入和刪除分別發生在佇列結構的兩端
插入資料的一端叫做尾端(Rear)，刪除資料的一端叫做前端(Front) 資料進出佇列的次序形成「先進者先出」的特性 排隊

3 佇列的表示法及基本運作 佇列的表示法及基本運作 1.產生佇列結構： 宣告一個陣列結構或鏈結串列結構，並設定成空佇列， 2.將資料加入佇列：
即 Front=Rear=-1 或 Front=Rear=NULL(=0)。 2.將資料加入佇列： 若佇列未滿溢，則改變Rear指標(加1)後將資料存入佇列之Rear位置。 3.從佇列刪除一個元素： 若非空佇列，則改變Front指標(加1)後將Front所指到之佇列元素刪除。 4.判斷佇列是否滿溢： 當Rear=N-1時，表示佇列滿溢。(假設陣列之大小為N， 並且資料從第0個索引開始存放)。 5.判斷是否為空佇列： 當 Front=Rear時，為空佇列。

4 佇列的基本運作 佇列的插入和刪除(以陣列製作)

5 佇列的基本運作(採用陣列結構) 定義一個佇列類別 class Queue{ private: int *data; int front;
int rear; public: Queue(int size); ~Queue( ); bool empty( ); bool full(int size); void insert(int key); //放入佇列 int erase( ); //取出佇列前端資料 };

6 佇列的基本運作(採用陣列結構) Constructor 產生佇列 Queue :: Queue(int size) {
data = new int[size]; front = -1; rear = -1; cout << "已產生一個大小為" << size << " 的佇列物件! "; } Destructor 銷毀佇列 Queue :: ~Queue( ) cout << "佇列已銷毀! " << endl;

7 佇列的基本運作(採用陣列結構) 判斷是否為空佇列 bool Queue :: empty(void) {
return (front = = rear) ? true : false; } 判斷佇列是否滿溢 bool Queue :: full(int size) return (rear = size - 1) ? true : false;

8 佇列的基本運作(採用陣列結構) 將資料key 放入佇列尾端 void Queue :: insert(int key) {
data[++rear] = key; } 將佇列前端的資料取出 int Queue :: erase( ) return data[++front];