[模板] Queue(佇列)

2019-09-21

模板

Queue 主結構

#include <stdio.h>
#define ENTSIZ 1024

typedef struct
{
    struct Data
    {
        /* your data here */
    };
    struct Node* _next;
}Node;

typedef struct
{
    Node* front, * last;
}Queue;

Node entries[ENTSIZ], * entry = entries, * freeBuk;

inline void push(register Queue* que, register Node val)
{
    if (freeBuk)
    {
        Node* tmp = freeBuk->_next;
        *freeBuk = val, freeBuk->_next = NULL;
        if (que->last)  que->last = que->last->_next = freeBuk;
        else que->front = que->last = freeBuk;
        freeBuk = tmp;
    }
    else
    {
        *entry = val;
        if (que->last) que->last = que->last->_next = entry++;
        else que->front = que->last = entry++;
    }
}

inline Node pop(register Queue* que)
{
    Node* tmp = que->front;
    que->front = que->front->_next;
    tmp->_next = freeBuk;
    return *(freeBuk = tmp);
}

概述

本組模板為佇列模板，在已知元素數量上限時使用此模板可以省去動態宣告記憶體的時間，本模板可同時宣告並使用複數個 stack 和 queue，而只須保證資料結構相同且元素總數不超過定義上限即可。

結構

Node

本結構為資料的進入點，其中 struct Data 為供使用者存取資料的結構，_next 則是保證結構正運作的必要參數，請不要任意更改它除非你清楚了解它的作用。

Queue

本結構為佇列的主結構，使用他來宣告一個新的佇列，結構中的 front 和 last 指標分別恆指向該佇列的最前和最末端元素。

函式

push()

本函式會新增一筆資料至目標堆疊的最末端。

參數

stk (Queue*)

本參數為目標佇列。

val (Node)

本參數為存入目標佇列最末端的元素。

回傳值

本函式無回傳值。

pop()

本函式會將目標佇列最前端的資料取出並回傳該元素。

stk (Queue*)

本參數為目標佇列。

回傳值

本函式回傳目標佇列最前端的元素。

其他

ENTSIZ

此巨集用來定義元素的數量上限。

實例

#include <stdio.h>
#define ENTSIZ 1024

typedef struct
{
    struct Data
    {
        int a, b;
    };
    struct Node* _next;
}Node;

typedef struct
{
    Node* front, * last;
}Queue;

Node entries[ENTSIZ], * entry = entries, * freeBuk;

inline void push(register Queue* que, register Node val)
{
    if (freeBuk)
    {
        Node* tmp = freeBuk->_next;
        *freeBuk = val, freeBuk->_next = NULL;
        if (que->last)  que->last = que->last->_next = freeBuk;
        else que->front = que->last = freeBuk;
        freeBuk = tmp;
    }
    else
    {
        *entry = val;
        if (que->last) que->last = que->last->_next = entry++;
        else que->front = que->last = entry++;
    }
}

inline Node pop(register Queue* que)
{
    Node* tmp = que->front;
    que->front = que->front->_next;
    tmp->_next = freeBuk;
    return *(freeBuk = tmp);
}

int main()
{
    Queue queue = { 0 };
    Node n = { 0, 1 };
    push(&queue, n);
    n.b = 2;
    push(&queue, n);
    push(&queue, pop(&queue));
    n.b = 3;
    push(&queue, n);
    n = pop(&queue);
    printf("%d,%d\n", n.a, n.b);
    printf("%d,%d\n", queue.front->a, queue.front->b);
    printf("%d,%d\n", queue.last->a, queue.last->b);
    return 0;
}

編譯運行結果

0,2
0,1
0,3

注意事項

如果自定義資料較大，你應該將存取方式改為使用指標，並透過映射的方式存取資料來減少記憶體的操作次數。
在區域變數裡宣告新的 Queue 時必須將其初始化

Queue queue = { 0 };

否則會因為存取違規而出現 runtime error;
如果要同時使用 Stack 和 Queue，請將兩者的 push() 和 pop() 函式用不同名字區隔開來。
測試階段，謹慎使用。

更新紀錄

無