C 語言數據結構：順序棧完整實現（初始化、入棧、遍歷、銷毀、清空、取頂、長度）

編輯：關於C語言

結構體定義

typedef int SElemType;  // 可替換為任意類型

typedef struct {
    SElemType *base;   // 棧底指針
    SElemType *top;    // 棧頂指針（指向下一可用位置）
    int stackSize;     // 當前分配容量
} SqStack;

常量

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
#define TRUE 1
#define FALSE 0
typedef int Status;

核心操作實現

1. 初始化

Status InitStack(SqStack *s) {
    s->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
    if (!s->base) return FALSE;
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
    return TRUE;
}

2. 入棧（動態擴容）

Status Push(SqStack *s, SElemType e) {
    if (s->top - s->base >= s->stackSize) {  // 滿
        SElemType *newBase = (SElemType*)realloc(s->base,
            (s->stackSize + STACK_INCREMENT) * sizeof(SElemType));
        if (!newBase) return FALSE;
        s->top = newBase + s->stackSize;  // 保持相對偏移
        s->base = newBase;
        s->stackSize += STACK_INCREMENT;
    }
    *s->top++ = e;
    return TRUE;
}

3. 出棧

Status Pop(SqStack *s, SElemType *e) {
    if (s->top == s->base) return FALSE;  // 空
    *e = *--s->top;
    return TRUE;
}

4. 取棧頂

Status GetTop(SqStack s, SElemType *e) {
    if (s.top == s.base) return FALSE;
    *e = *(s.top - 1);
    return TRUE;
}

5. 判空/長度

Status StackEmpty(SqStack s) { return s.base == s.top; }
int StackLength(SqStack s) { return s.top - s.base; }

6. 清空/銷毀/遍歷

Status ClearStack(SqStack *s) { s->top = s->base; return TRUE; }

Status DestroyStack(SqStack *s) {
    free(s->base);
    s->base = s->top = NULL;
    s->stackSize = 0;
    return TRUE;
}

Status StackTraverse(SqStack s) {  // 從棧底到棧頂
    if (StackEmpty(s)) return FALSE;
    SElemType *p = s.base;
    while (p != s.top) printf("%d ", *p++);
    printf("\n");
    return TRUE;
}

測試主程序

int main() {
    SqStack s; InitStack(&s);
    for (int i=0; i<20; i++) Push(&s, i);
    StackTraverse(s);           // 0 1 ... 19
    printf("Length: %d\n", StackLength(s)); // 20
    int e; GetTop(s, &e); printf("Top: %d\n", e); // 19
    ClearStack(&s); StackTraverse(s); // 空
    DestroyStack(&s); StackTraverse(s); // 不存在
    return 0;
}