您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言實作棧：順序棧與鏈式棧完整 ADT 代碼、測試與記憶體管理細節

編輯：關於C

抽象資料類型 (ADT) 定義

// 介面
void initStack(Stack *s);
bool isEmpty(Stack s);
bool isFull(Stack s);       // 僅順序棧
int getLength(Stack s);
ElemType getTop(Stack s);
void push(Stack *s, ElemType e);
void pop(Stack *s, ElemType *e);
void traversal(Stack s);
void cleanStack(Stack *s);
void destroyStack(Stack *s);

順序棧（動態陣列）

#define STACK_INIT_SIZE 50
#define STACK_INCREMENT 10

typedef struct {
    ElemType *base;   // 底部指標
    ElemType *top;    // 頂部指標（指向下一個可用位置）
    int stackSize;    // 當前容量
} SqStack;

void initStack(SqStack *s) {
    s->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if (!s->base) exit(1);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

void push(SqStack *s, ElemType e) {
    if (s->top - s->base >= s->stackSize) { // 滿，擴容
        ElemType *newBase = (ElemType*)realloc(s->base,
            (s->stackSize + STACK_INCREMENT) * sizeof(ElemType));
        if (!newBase) exit(1);
        s->base = newBase;
        s->top = s->base + s->stackSize;
        s->stackSize += STACK_INCREMENT;
    }
    *s->top++ = e;
}

void pop(SqStack *s, ElemType *e) {
    if (s->top == s->base) exit(1); // 空
    *e = *--s->top;
}

鏈式棧（單向鏈表，頭插法）

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkStack;

void initStack(LinkStack *s) {
    *s = (LinkStack)malloc(sizeof(Node)); // 頭節點
    (*s)->next = NULL;
}

void push(LinkStack s, ElemType e) {
    Node *n = (Node*)malloc(sizeof(Node));
    n->data = e;
    n->next = s->next;
    s->next = n;
}

void pop(LinkStack s, ElemType *e) {
    if (s->next == NULL) exit(1);
    Node *p = s->next;
    *e = p->data;
    s->next = p->next;
    free(p);
}

測試主程式

int main(void) {
    SqStack sq; initStack(&sq);
    push(&sq, 'a'); push(&sq, 'b'); push(&sq, 'c');
    traversal(sq); // a b c
    ElemType e; pop(&sq, &e); printf("pop: %c\n", e); // c
    destroyStack(&sq);

    LinkStack lk; initStack(&lk);
    push(lk, 1); push(lk, 2);
    traversal(lk); // 2 1 (頭插法，顯示為逆序)
    destroyStack(&lk);
    return 0;
}

關鍵記憶體管理細節

操作	順序棧	鏈式棧
初始化	malloc 基址，top=base	malloc 頭節點，next=NULL
擴容/插入	realloc 保留資料，調整 top	malloc 新節點，頭插
銷毀	free(base), base=top=NULL	遍歷 free 每節點，頭節點最後 free
清空	top = base	逐個 pop 或遍歷 free 非頭節點