C語言實現棧結構：鏈式與數組兩種方式

編輯：關於C語言

棧（Stack）概述

棧是後進先出（LIFO）的線性數據結構。本文提供兩種經典 C 語言實現：鏈式棧（動態分配，無容量上限）與 數組棧（固定容量，訪問速度快）。兩者接口統一，便於替換。

1. 鏈式棧實現

頭文件 `stackli.h`

typedef int ElementType;
#ifndef STACKLI_H_INCLUDED
#define STACKLI_H_INCLUDED
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
#endif

源文件 `stackli.c`

#include "stackli.h"
#include "fatal.h"

struct Node {
    ElementType Element;
    PtrToNode Next;
};

int IsEmpty(Stack S) { return S->Next == NULL; }

Stack CreateStack(void) {
    Stack S = malloc(sizeof(struct Node));
    if (!S) FatalError("Out of space!!!");
    S->Next = NULL;
    return S;
}

void MakeEmpty(Stack S) {
    if (!S) Error("Must use CreateStack first");
    else while (!IsEmpty(S)) Pop(S);
}

void DisposeStack(Stack S) { MakeEmpty(S); free(S); }

void Push(ElementType X, Stack S) {
    PtrToNode TmpCell = malloc(sizeof(struct Node));
    if (!TmpCell) FatalError("Out of space!!!");
    TmpCell->Element = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

ElementType Top(Stack S) {
    if (!IsEmpty(S)) return S->Next->Element;
    Error("Empty stack"); return 0;
}

void Pop(Stack S) {
    if (IsEmpty(S)) Error("Empty stack");
    else {
        PtrToNode FirstCell = S->Next;
        S->Next = S->Next->Next;
        free(FirstCell);
    }
}

2. 數組棧實現

頭文件 `stackar.h`

typedef int ElementType;
#ifndef STACKAR_H_INCLUDED
#define STACKAR_H_INCLUDED
struct StackRecord;
typedef struct StackRecord *Stack;

int IsEmpty(Stack S);
int IsFull(Stack S);
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);
#endif

源文件 `stackar.c`

#include "stackar.h"
#include "fatal.h"
#define EmptyTOS -1
#define MinStackSize 5

struct StackRecord {
    int Capacity;
    int TopOfStack;
    ElementType *Array;
};

int IsEmpty(Stack S) { return S->TopOfStack == EmptyTOS; }
int IsFull(Stack S) { return S->TopOfStack == S->Capacity - 1; }

Stack CreateStack(int MaxElements) {
    if (MaxElements < MinStackSize) Error("Stack size is too small");
    Stack S = malloc(sizeof(struct StackRecord));
    if (!S) FatalError("Out of space!!!");
    S->Array = malloc(sizeof(ElementType) * MaxElements);
    if (!S->Array) FatalError("Out of space!!!");
    S->Capacity = MaxElements;
    MakeEmpty(S);
    return S;
}

void MakeEmpty(Stack S) { S->TopOfStack = EmptyTOS; }

void DisposeStack(Stack S) {
    if (S) { free(S->Array); free(S); }
}

void Push(ElementType X, Stack S) {
    if (IsFull(S)) Error("Full stack");
    else S->Array[++S->TopOfStack] = X;
}

ElementType Top(Stack S) {
    if (!IsEmpty(S)) return S->Array[S->TopOfStack];
    Error("Empty stack"); return 0;
}

void Pop(Stack S) {
    if (IsEmpty(S)) Error("Empty stack");
    else S->TopOfStack--;
}

ElementType TopAndPop(Stack S) {
    if (!IsEmpty(S)) return S->Array[S->TopOfStack--];
    Error("Empty stack"); return 0;
}

對比與選擇建議

特性	鏈式棧	數組棧
內存分配	動態，按需分配	創建時一次性分配
容量限制	僅受限於堆內存	固定，創建時指定
Push/Pop 性能	涉及 malloc/free，較慢	極快，僅指釧運算
內存碎片	可能產生	無
適用場景	大小不可預知、頻繁增減	大小可預估、高性能要求