程式扎記: [ 資料結構 小學堂 ] 佇列 : 認識佇列

標籤

2010年10月4日 星期一

[ 資料結構 小學堂 ] 佇列 : 認識佇列

前言 : 
佇列 (Queue) 與堆疊都是一種有序串列, 也屬於抽象資料型態. 它所有加入與刪除的動作都發生在不同的兩端, 並且符合 "First In, First Out" 的特性. 佇列的觀念就好比搭捷運買票的隊伍, 先到的人可以優先買票, 買完後就從前端離去準備搭捷運, 而隊伍的後端又陸續有新的乘客加入排隊. 

認識佇列 : 
在佇列實作上可以採用陣列或是串列來建立一個佇列. 不過堆疊只需要一個top 指標指向堆疊頂, 但佇列則需要使用 front 與 rear 兩個指標分別指向前端與尾端. 如下 : 
 

由於佇列是一種抽象式資料結構, 它有以下特性 : 

1. 具有先進先出 (FIFO) 的特性.
2. 擁有兩種基本動作加入與刪除, 而且使用 front 與 rear 兩個指標來分別指向佇列的前端與尾端.

至於佇列的基本運算可以具備以下五種工作定義 : 
* CREATE : 建立空佇列 
* ADD : 將新資料加入住列的尾端, 傳回新佇列. 
* FRONT : 傳回佇列前端的值 
* DELETE : 刪除佇列前端的值, 並傳回新佇列. 
* EMPTY : 若佇列為空集合, 則為真, 否則為偽. 

範例代碼 : 
底下我們就簡單以陣列來實作佇列的工作運算, 這裡我們固定將 front 指標指向陣列的第0 個位置, 而 rear 指標則隨著添加成員而移動. 且一開始 rear 設為 -1 表示空佇列. 
* JQueue.h 代碼 : 

  1. #include   
  2. #include   
  3.   
  4. using namespace std;  
  5. #define MAX_QUEUE_SIZE 20 // 定義佇列的大小  
  6.   
  7. class JQueue{  
  8. protected:  
  9.     int rear;  
  10.     int _queue[MAX_QUEUE_SIZE];  
  11. public:  
  12.     JQueue(){     
  13.         rear = -1;  
  14.     }  
  15.     bool add(int val);  // 添加新資料到佇列  
  16.     bool isEmpty();  //判斷佇列是否為空  
  17.     bool isFull();  // 判斷佇列是否已滿  
  18.     bool get(int *val); // 取回佇列的值  
  19.     int length(); // 目前佇列的資料數量.  
  20. };  
* JQueue.cpp 代碼 : 

  1. #include "JQueue.h"  
  2.   
  3. bool JQueue::add(int val){  
  4.     if(!this->isFull()) {  
  5.         rear++;  
  6.         this->_queue[rear] = val;  
  7.         return true;  
  8.     }  
  9.     cout << "[佇列已滿]" << endl;  
  10.     return false;  
  11. }  
  12.   
  13. bool JQueue::isFull() {  
  14.     if((rear+1)==MAX_QUEUE_SIZE) {  
  15.         return true;  
  16.     } else {  
  17.         return false;  
  18.     }  
  19. }  
  20.   
  21. bool JQueue::isEmpty() {  
  22.     if(rear>=0) {  
  23.         return false;  
  24.     } else {  
  25.         return true;  
  26.     }  
  27. }  
  28.   
  29. bool JQueue::get(int *val) {  
  30.     if(!this->isEmpty()) {  
  31.         *val = this->_queue[0];  
  32.         for(int i=0; i
  33.             this->_queue[i] = this->_queue[i+1];  
  34.         }  
  35.         rear--;  
  36.         return true;  
  37.     } else {  
  38.         cout << "[佇列為空!]" << endl;  
  39.         *val = -1;  
  40.         return false;  
  41.     }  
  42. }  
  43.   
  44. int JQueue::length(){  
  45.     return rear+1;  
  46. }  
* 呼叫演算法代碼 : 

  1. void ch05_01(bool b) {  
  2.     if(b) {  
  3.         char ch = 'S';  
  4.         int val;  
  5.         int gval=-1;  
  6.         JQueue queue;  
  7.         while(ch != 'E') {  
  8.             cout << "[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :";  
  9.             cin >> ch;  
  10.             switch(ch) {  
  11.                 case 'A':  
  12.                     cout << "請輸入數值: ";  
  13.                     cin >> val;  
  14.                     queue.add(val);  
  15.                     break;  
  16.                 case 'G':  
  17.                     queue.get(&gval);  
  18.                     if(gval>=0) {  
  19.                         cout << "取出數值為: " << gval << endl;  
  20.                     }  
  21.                     break;  
  22.                 case 'E':  
  23.                     cout << "[離開程式]" << endl;  
  24.                     break;  
  25.                 case 'L':  
  26.                     cout << "目前佇列資料數目為: " << queue.length() << endl;  
  27.                     break;  
  28.                 default:  
  29.                     cout << "不合法字元! (" << ch << ")"  << endl;  
  30.                     break;  
  31.             }  
  32.         }  
  33.     }  
  34. }  

執行結果 : 

[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :A <添加新資料>
請輸入數值: 1
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :A <添加新資料>
請輸入數值: 2
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :L <檢查目前佇列資料數目>
目前佇列資料數目為: 2
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :G <取回佇列資料>
取出數值為: 1
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :G
取出數值為: 2
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :G
[佇列為空!]
[A]存入一個數值, [G] 取出一個數值, [E] 結束, [L] 目前佇列長度 :E <離開程式>
[離開程式]


補充說明 : 
* [ 資料結構 小學堂 ] 堆疊 : 認識堆疊

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!