5月 20, 2008

【演算】佇列 - Queue

@
  與堆疊(stack)類似,佇列(queue)也是一種是一種同質元素集合的資料結構。與之不同的是,佇列只允許資料在後端(rear)進行插入(add)操作、在前端(front)進行刪除(delete)操作。

  同樣的,讓我們舉個實例:相對於堆疊的疊盤子,你可以把佇列想像成一個正在排隊買甜甜圈的隊伍。每執行一次 "delete" 的動作就像是隊伍最前端,成功的買到甜甜圈而離開隊伍。而執行一次 "add" 就像是多了一個想買甜甜圈的客人,而在隊伍的最後端開始排隊(請忽略掉插隊問題)。

  也因此,不同於堆疊的 LIFO,佇列的操作方式被稱為 FIFO (First In First Out,先入先出)。換句話說,就是越早加入佇列的人(資料)會越早離開佇列。

  所以,佇列的應用範圍也相當廣泛。從剛剛舉例說明的排隊、圖形的廣度追蹤、使用印表機時的列印佇列等等,都可以見到佇列應用的蹤影。


  而模擬一個佇列的運作,最簡單的方式還是使用陣列。同樣定義一個大小為 MAX_SIZE 的陣列,並使用兩個變數 front 與 rear 分別代表佇列的前後端。以下是一個簡易佇列實現的虛擬碼實例:

void add(Queue &queue, Type data)
{
    Index front, rear;

    if (rear = MAX_SIZE)
    {
        print("The queue is full!");
    }
    else
    {
        stack[rear] = data;
        rear = rear + 1;
    }
}

void delete(Queue &queue)
{
    Index front, rear;

    if (front = rear)
    {
        print "The queue is empty!";
    }
    else
    {
        front = front + 1;
    }
}

  同樣的,陣列之外模擬方式與 C++ STL 實現的佇列相關函式這裡我們不討論,請有興趣者自行查詢相關資料。

  以下是 C 使用陣列實現的原始碼,可以參考看看:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 10

void addQ(int);
void deleteQ(void);

int queue[MAX_SIZE], front = 0, rear = 0;

int main(void)
{
    addQ(0);
    addQ(1);
    deleteQ();
    addQ(2);
    addQ(3);
    addQ(4);
    deleteQ();
    deleteQ();
    addQ(5);
    addQ(6);
    addQ(7);
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();

    system("pause");
}

void addQ(int data)
{
    if (rear == MAX_SIZE)
    {
        printf("The queue is full!\n");
    }
    else
    {
        queue[rear++] = data;
    }
}

void deleteQ(void)
{
    if (front == rear)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", queue[front++]);
    }
}

2 回覆:

匿名 提到...

轉貼文章於
http://www.facebook.com/inbox/?ref=mb#/home.php?filter=app_2309869772
如果有不妥 請通知我 我會馬上刪除 謝謝

小參 提到...

沒問題, 歡迎引用:)

張貼留言