[模板] Stack(堆疊)

2019-09-20

模板

Stack 主結構

#define ENTSIZ 1024

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

typedef struct
{
    Node* top;
}Stack;

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

inline void push(register Stack* stk, register Node val)
{
    if (freeBuk)
    {
        Node* tmp = freeBuk->_next;
        *freeBuk = val, freeBuk->_next = stk->top;
        stk->top = freeBuk;
        freeBuk = tmp;
    }
    else
    {
        *entry = val, entry->_next = stk->top;
        stk->top = entry++;
    }
}

inline Node pop(register Stack* stk)
{
    Node* tmp = stk->top;
    stk->top = stk->top->_next;
    tmp->_next = freeBuk;
    return *(freeBuk = tmp);
}

概述

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

結構

Node

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

Stack

本結構為堆疊的主結構，使用他來宣告一個新的堆疊，結構中的 top 指標恆指向該堆疊最頂端的元素。

函式

push()

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

參數

stk (Stack*)

本參數為目標堆疊。

val (Node)

本參數為存入目標堆疊頂層的元素。

回傳值

本函式無回傳值。

pop()

本函式會將目標堆疊頂層的資料取出並回傳該元素。

stk (Stack*)

本參數為目標堆疊。

回傳值

本函式回傳目標堆疊頂層元素。

其他

ENTSIZ

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

實例

#include <stdio.h>
#define ENTSIZ 1024

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

typedef struct
{
    Node* top;
}Stack;

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

inline void push(register Stack* stk, register Node val)
{
    if (freeBuk)
    {
        Node* tmp = freeBuk->_next;
        *freeBuk = val, freeBuk->_next = stk->top;
        stk->top = freeBuk;
        freeBuk = tmp;
    }
    else
    {
        *entry = val, entry->_next = stk->top;
        stk->top = entry++;
    }
}

inline Node pop(register Stack* stk)
{
    Node* tmp = stk->top;
    stk->top = stk->top->_next;
    tmp->_next = freeBuk;
    return *(freeBuk = tmp);
}

int main()
{
    Stack stack1 = { 0 }, stack2 = { 0 };
    Node n = { 0, 1 };
    push(&stack1, n);
    n.b = 2;
    push(&stack2, n);
    push(&stack1, pop(&stack2));
    n = pop(&stack1);
    printf("%d,%d\n", n.a, n.b);
    printf("%d,%d\n", stack1.top->a, stack1.top->b);
    n = pop(&stack1);
    printf("%d,%d", n.a, n.b);
    return 0;
}

編譯運行結果

0,2
0,1
0,1

注意事項

如果自定義資料較大，你應該將存取方式改為使用指標，並透過映射的方式存取資料來減少記憶體的操作次數。
如果要同時使用 Stack 和 Queue，請將兩者的 push() 和 pop() 函式用不同名字區隔開來。
測試階段，謹慎使用。

更新紀錄

2019-9-21

調整運作結構使其能和 Queue 混用同一塊記憶體 (在資料結構相同的情況)
優化 pop()，現在比之前少執行一行命令。