Queue (佇列)

假設有一群人排隊買電影票，那是不是先來的可以先買票，那這種資料結構叫做 Queue

這種資料結構有特性 先進先出(First-In-First-Out, FIFO)

Queue 支援那些操作呢

Push (Enqueue) x - 把 x 塞到Queue的尾部
Pop (Dequeue) - 把 Queue 最前面的元素抽
Front - 看看 Queue 最前面的元素是什麼
Clear - 把 Queue 清空
Full - rear(queue的尾巴)剛好等於陣列的長度時

玩玩看 : https://www.cs.usfca.edu/~galles/JavascriptVisual/QueueArray.html

範例 - 自製 Queue

[操作說明]

push x : 放入整數 x 進入queue

pop : 將queue中的整數拿出來

[input]

push 9
push 5
push 2
push 7
pop
pop
pop
push 1
pop
pop
pop

[output]

 pop: 9
 pop: 5
 pop: 2
 pop: 7
 pop: 1
 pop: nothing in queue

[說明]

讓 queue_back 永遠等於最後一個元素的位置+1, queue_front 永遠等於最前面元素位置
一開始 queue 中沒有任何元素，令 queue_front = queue_back = 0
當 queue 中沒有元素時( queue_front = queue_back )就不能 pop

[Code]

#include<bits/stdc++.h>
using namespace std;

int que[105], queue_front, queue_back;


int main ()
{
    string cmd;
    int i;

    queue_front = queue_back = 0;

    while( cin >> cmd ){
        if( cmd == "push" ){
            cin >> i;
            que[ queue_back ] = i;
            queue_back++;
        }
        else if( cmd == "pop" ){
            if( queue_front == queue_back )
                cout << " pop: nothing in queue" << endl;
            else{
                cout << " pop: " << que[queue_front] << endl;
                queue_front++;
            }
        }
    }

    return 0;
}

想想看，如果 push 100 次後，再 pop 100 次，想要再 push 100 次時，該怎麼做?

環形佇列 - Circular Queue

概念上的Circular Queue

實際上的Circular Queue

下圖是一個運用 Circular Buffer 製作的 Queue

只要 buffer 的空間比 Queue 裡面平均資料的長度長, 就可以循環地使用 buffer

Head 指的位置就是 Queue 的最前端, 也就是可以讀出資料的地方, 除非 buffer 已經空了
Tail 指的位置就是 Queue 的尾巴的後一個位置, 也就是可以把資料寫進去的地方, 除非 buffer 已經滿了
移除一筆資料後把 Head 往後移一格新增一筆資料後把 Tail 往後移一格
此例中 buffer 有 8 個空間, 但是最多只能存放 7 個元素, 不能把 buffer 完全填滿, 否則分不出 buffer 是滿的還是空的
例如當 Head 為 0, Tail 為 7 時就是滿的, Head 和 Tail 指到相同的地方代表 buffer 裡面是空的, 例如 Head 為 5, Tail 為 5

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = 0, rear =0;

bool isFull()
{
    if( front == (rear + 1)%SIZE ) return true;
    return 0;
}

bool isEmpty()
{
    if(front == rear) return true;
    return 0;
}

void enQueue(int element)
{
    if(isFull()) printf("\n Queue is full!! \n");
    else
    {
        rear = (rear + 1) % SIZE;
        items[rear] = element;
        printf("\n Inserted -> %d", element);
    }
}


int deQueue()
{
    int element;
    if(isEmpty()) {
        printf("\n Queue is empty !! \n");
        return(-1);
    } else {
        element = items[front];
        front = (front + 1) % SIZE;
        printf("\n Deleted element -> %d \n", element);
        return(element);
    }
}

void display()
{
    int i;
    if(isEmpty()) printf(" \n Empty Queue\n");
    else
    {
        printf("\n Front -> %d ",front);
        printf("\n Items -> ");
        for( i = front; i!=rear; i=(i+1)%SIZE) {
            printf("%d ",items[i]);
        }
        printf("%d ",items[i]);
        printf("\n Rear -> %d \n",rear);
    }
}

int main()
{
    // Fails because front = -1
    deQueue();

    enQueue(1);
    enQueue(2);
    enQueue(3);
    enQueue(4);
    enQueue(5);

    // Fails to enqueue because front == 0 && rear == SIZE - 1
    enQueue(6);

    display();
    deQueue();

    display();

    enQueue(7);
    display();

    // Fails to enqueue because front == rear + 1
    enQueue(8);

    return 0;
}

[題目練習]

d406: 倒水時間 : https://zerojudge.tw/ShowProblem?problemid=d406

解答 :

#include <bits/stdc++.h>
using namespace std;
int arriveTime[105][105];
int pipe[105][105];

int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; // d在此代表direction的縮寫
// 如果用座標軸來看
// ( dx[0] ,dy[0] ) = (0 , 1)
// ( dx[1] ,dy[1] ) = (0 ,-1)
// ( dx[2] ,dy[2] ) = (1 , 0)
// ( dx[3] ,dy[3] ) = (-1, 0)

int N, M , S, casen = 1;
struct Node{
    int x, y;
    Node( int _y, int _x ){
        x = _x;
        y = _y;
    }
};
int main(){
    // 若 S = 2  代表水不能往上流， S = 1  代表水可以往上流。
    while ( cin >> S ){
        // 流水時間初始化
        cin >> N >> M; // N列 M欄
        for ( int i = 1 ; i <= N ; i++ )
            for ( int j = 1 ; j <= M ;j ++ )
                cin >> pipe[i][j];

        // 抵達時間初始化，抵達時間預設都為0
        for ( int i = 1 ; i <= N ; i++ )
            for ( int j = 1 ; j <= M ; j++ )
                arriveTime[i][j] = 0;

        queue<Node> que;

        for ( int i = 1 ; i <= M ; i++ )
            if ( pipe[1][i] == 1 ){
                arriveTime[1][i] = 1;
                que.push(Node(1,i) );
            }

        while ( !que.empty() ){
            Node currentNode = que.front();
            que.pop();
            for ( int d = 0 ; d < 4 ; d++ ){

                // 如果水不能往上流，我們就不檢查y方向是-1的狀況
                if ( S == 2 && dy[d] < 0 ) continue;

                int nx = currentNode.x + dx[d];
                int ny = currentNode.y + dy[d];

                //超出邊界的話，就不繼續做
                if ( nx < 1 || ny < 1 || nx > M || ny > N )
                    continue;
                // 如果這邊的水管不通就不繼續做
                if ( pipe[ny][nx] != 1 ) continue;
                // 如果這邊已經有水流過，就不再重複計算
                if ( arriveTime[ny][nx] != 0 ) continue;

                   // currentNode旁的水管的arriveTime，代表這些地方會被水流過
                   arriveTime[ny][nx] = arriveTime[currentNode.y][currentNode.x] + 1;

                   // 把這個新水管加到queue裡面
                   que.push( Node(ny,nx) );
            }
        }

        // 輸出答案
        cout << "Case " << casen++ << ":" << endl;
        for ( int i = 1 ; i <= N ; i++ ){

            for ( int j = 1 ; j <= M ; j++ ){
                if ( arriveTime[i][j] == 0 )
                    cout << 0 << " ";
                else
                    cout << arriveTime[i][j] << " ";
            }
            cout << endl;
        }
    }

    return 0;
}

3-4 Queue