C 语言栈实现

C语言栈实现

介绍

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。在C语言中，栈可以通过数组或链表实现，常用于函数调用、表达式求值、内存管理等场景。本章将详细介绍栈的基本操作（如入栈、出栈、查看栈顶元素等）及其C语言实现方式。

栈的基本操作

栈的核心操作包括：

• push(x)：将元素x压入栈顶。
• pop()：移除并返回栈顶元素。
• peek()（或top()）：返回栈顶元素但不移除。
• isEmpty()：检查栈是否为空。
• isFull()（仅限数组实现）：检查栈是否已满。

栈的数组实现

以下是用数组实现栈的完整代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *s) {
    s->top = -1;
}

// 检查栈是否为空
bool isEmpty(Stack *s) {
    return s->top == -1;
}

// 检查栈是否已满
bool isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("栈已满，无法压入元素 %d\n", value);
        return;
    }
    s->data[++s->top] = value;
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空，无法弹出元素\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top--];
}

// 查看栈顶元素
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        exit(EXIT_FAILURE);
    }
    return s->data[s->top];
}

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("栈顶元素: %d\n", peek(&s));  // 输出: 30
    printf("弹出元素: %d\n", pop(&s));   // 输出: 30
    printf("栈顶元素: %d\n", peek(&s));  // 输出: 20

    return 0;
}

输入与输出示例

输入：

push(&s, 10);
push(&s, 20);
push(&s, 30);
peek(&s);
pop(&s);
peek(&s);

输出：

栈顶元素: 30
弹出元素: 30
栈顶元素: 20

栈的链表实现

链表实现的栈可以动态调整大小，避免数组实现的固定容量限制。以下是代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
} Stack;

void initStack(Stack *s) {
    s->top = NULL;
}

bool isEmpty(Stack *s) {
    return s->top == NULL;
}

void push(Stack *s, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        exit(EXIT_FAILURE);
    }
    Node *temp = s->top;
    int poppedValue = temp->data;
    s->top = s->top->next;
    free(temp);
    return poppedValue;
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        exit(EXIT_FAILURE);
    }
    return s->top->data;
}

栈的可视化表示

graph LR A[栈顶] --> B[元素3] B --> C[元素2] C --> D[元素1] D --> E[栈底]

实际应用案例

案例1：括号匹配检查

栈可用于检查表达式中的括号是否匹配，例如 ()[]\{}。

bool isBalanced(char *exp) {
    Stack s;
    initStack(&s);
    for (int i = 0; exp[i]; i++) {
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            push(&s, exp[i]);
        } else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            if (isEmpty(&s)) return false;
            char top = pop(&s);
            if ((exp[i] == ')' && top != '(') ||
                (exp[i] == ']' && top != '[') ||
                (exp[i] == '}' && top != '{')) {
                return false;
            }
        }
    }
    return isEmpty(&s);
}

案例2：函数调用栈

程序执行时，函数调用和返回地址通过栈管理。例如：

main() -> func1() -> func2()

调用顺序为 main 入栈，func1 入栈，func2 入栈；返回时按 func2、func1、main 顺序出栈。

复杂度分析

• 时间复杂度：

 * 入栈（push）、出栈（pop）、查看栈顶（peek）：$O(1)$。

• 空间复杂度：

 * 数组实现：$O(n)$（固定大小）。
 * 链表实现：$O(n)$（动态大小）。

总结

栈是一种高效且易于实现的数据结构，适用于需要后进先出逻辑的场景。通过数组或链表实现各有优劣：数组实现简单但容量固定，链表实现灵活但需要额外内存管理。