C语言实现栈：从基础到实践

简介

在计算机科学中，栈是一种重要的数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。简单来说，最后进入栈的数据会最先被取出。栈在许多算法和程序设计场景中都有广泛应用，比如表达式求值、深度优先搜索（DFS）等。本文将深入探讨如何使用C语言来实现栈，并介绍其使用方法、常见实践以及最佳实践。

栈的基础概念

栈有两个主要操作：入栈（push）和出栈（pop）。入栈操作将元素添加到栈顶，而出栈操作则从栈顶移除元素并返回该元素。此外，还有一些辅助操作，如查看栈顶元素（peek）、判断栈是否为空（isEmpty）以及获取栈的大小（size）。

C语言实现栈的方法

基于数组的实现

基于数组实现栈是一种简单直观的方法。我们可以使用一个数组来存储栈中的元素，并使用一个变量来记录栈顶的位置。

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

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

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

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("栈溢出\n");
        return;
    }
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;
    }
    return s->data[(s->top)--];
}

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

// 获取栈的大小
int size(Stack *s) {
    return s->top + 1;
}

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

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

    printf("栈顶元素: %d\n", peek(&s));
    printf("弹出元素: %d\n", pop(&s));
    printf("栈的大小: %d\n", size(&s));

    return 0;
}

基于链表的实现

基于链表实现栈更灵活，因为它没有固定的大小限制。我们可以使用一个单链表来实现栈，链表的头节点作为栈顶。

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 定义栈结构体
typedef struct {
    Node *top;
} Stack;

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

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == NULL;
}

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

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;
    }
    Node *temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

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

// 获取栈的大小
int size(Stack *s) {
    int count = 0;
    Node *current = s->top;
    while (current!= NULL) {
        count++;
        current = current->next;
    }
    return count;
}

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

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

    printf("栈顶元素: %d\n", peek(&s));
    printf("弹出元素: %d\n", pop(&s));
    printf("栈的大小: %d\n", size(&s));

    return 0;
}

常见实践

表达式求值

栈在表达式求值中非常有用，特别是对于中缀表达式。我们可以使用两个栈，一个用于操作数，一个用于操作符，通过特定的规则将中缀表达式转换为后缀表达式并求值。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

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

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, char value) {
    if (isFull(s)) {
        printf("栈溢出\n");
        return;
    }
    s->data[++(s->top)] = value;
}

// 出栈操作
char pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return '\0';
    }
    return s->data[(s->top)--];
}

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

// 获取操作符的优先级
int precedence(char op) {
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

// 执行二元操作
int applyOp(int a, int b, char op) {
    switch (op) {
    case '+': return a + b;
    case '-': return a - b;
    case '*': return a * b;
    case '/': return a / b;
    }
    return 0;
}

// 计算后缀表达式
int evaluatePostfix(char *exp) {
    Stack s;
    initStack(&s);

    for (int i = 0; i < strlen(exp); i++) {
        if (isdigit(exp[i]))
            push(&s, exp[i] - '0');
        else {
            int val2 = pop(&s);
            int val1 = pop(&s);
            int result = applyOp(val1, val2, exp[i]);
            push(&s, result);
        }
    }
    return pop(&s);
}

// 中缀转后缀
void infixToPostfix(char *infix, char *postfix) {
    Stack s;
    initStack(&s);

    int j = 0;
    for (int i = 0; i < strlen(infix); i++) {
        if (isdigit(infix[i]))
            postfix[j++] = infix[i];
        else if (infix[i] == '(')
            push(&s, infix[i]);
        else if (infix[i] == ')') {
            while (!isEmpty(&s) && peek(&s)!= '(')
                postfix[j++] = pop(&s);
            pop(&s);
        } else {
            while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i]))
                postfix[j++] = pop(&s);
            push(&s, infix[i]);
        }
    }
    while (!isEmpty(&s))
        postfix[j++] = pop(&s);
    postfix[j] = '\0';
}

int main() {
    char infix[MAX_SIZE], postfix[MAX_SIZE];
    printf("请输入中缀表达式: ");
    scanf("%s", infix);

    infixToPostfix(infix, postfix);
    printf("后缀表达式: %s\n", postfix);
    printf("计算结果: %d\n", evaluatePostfix(postfix));

    return 0;
}

函数调用栈模拟

栈在函数调用过程中起着重要作用，我们可以使用栈来模拟函数调用和返回的过程。

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

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

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

// 判断栈是否为空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈操作
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("栈溢出\n");
        return;
    }
    s->data[++(s->top)] = value;
}

// 出栈操作
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return -1;
    }
    return s->data[(s->top)--];
}

// 模拟函数调用
void functionCall(Stack *s, int funcNum) {
    printf("调用函数 %d\n", funcNum);
    push(s, funcNum);
}

// 模拟函数返回
void functionReturn(Stack *s) {
    if (isEmpty(s)) {
        printf("没有函数在调用栈中\n");
        return;
    }
    int funcNum = pop(s);
    printf("返回函数 %d\n", funcNum);
}

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

    functionCall(&s, 1);
    functionCall(&s, 2);
    functionCall(&s, 3);

    functionReturn(&s);
    functionReturn(&s);
    functionReturn(&s);

    return 0;
}

最佳实践

内存管理

在基于链表实现栈时，要特别注意内存管理。每次入栈时分配内存，每次出栈时释放内存，防止内存泄漏。

错误处理

在实现栈的操作时，要进行充分的错误处理。比如，当栈为空时进行出栈操作，或者栈满时进行入栈操作，都应该给出相应的提示信息。

小结

本文详细介绍了栈的基础概念，并通过C语言实现了基于数组和链表的栈。同时，展示了栈在表达式求值和函数调用栈模拟等常见场景中的应用。在实际使用中，遵循最佳实践，如正确的内存管理和错误处理，可以使代码更加健壮和可靠。希望读者通过本文能够深入理解并高效使用C语言实现栈。

参考资料

《数据结构与算法分析（C语言描述）》
《C Primer Plus》
GeeksforGeeks