C语言实现栈的示例详解

栈(Stack)是一种非常重要的数据结构，在许多编程语言中都有广泛的应用。在C语言中，我们可以利用数组来实现栈数据结构。下面将介绍C语言实现栈的示例详解。

栈的结构

栈是一种线性数据结构，它具有以下特点：

• 后进先出(LIFO)：最后压入栈的元素最先出栈；
• 插入(入栈)和删除(出栈)操作都在栈顶进行。

示意图如下：

|_______| <--- top
|_______|
|_______|
|_______|
|_______|

实现步骤

1. 定义栈的结构体

首先，你需要定义一个结构体来表示栈，其中包含以下元素：

• 一个指向栈顶元素的指针 top
• 一个整数数组 data，用于存储栈中的数据
• 一个整数 size，表示栈的容量

#define STACK_SIZE 10

typedef struct {
    int *data;
    int top;
    int size;
} Stack;

2. 实现初始化函数

栈的初始化函数会创建一个新的栈结构体，并动态分配存储栈元素用的内存。

void init_stack(Stack *s, int size)
{
    s->data = (int*)malloc(size * sizeof(int));
    s->top = -1;
    s->size = size;
}

3. 实现入栈函数

入栈函数需要将元素压入栈，并将 top 指针指向它。这个函数还要检查栈是否已满，如果已满就打印一个错误信息并返回。

int push(Stack *s, int value)
{
    if (s->top >= s->size - 1) {
        printf("Error: stack overflow\n");
        return -1;
    } else {
        s->top++;
        s->data[s->top] = value;
        return 0;
    }
}

4. 实现出栈函数

出栈函数需要从栈中删除元素，并将 top 指针指向栈中的新顶部元素。这个函数还要检查栈是否为空，如果为空就打印一个错误信息并返回。

int pop(Stack *s)
{
    if (s->top <= -1) {
        printf("Error: stack underflow\n");
        return -1;
    } else {
        int value = s->data[s->top];
        s->top--;
        return value;
    }
}

5. 实现栈销毁函数

最后，你需要释放存储栈元素使用的内存。

void destroy_stack(Stack *s)
{
    free(s->data);
}

示例说明

示例1：栈的基本操作

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

#define STACK_SIZE 10

typedef struct {
    int *data;
    int top;
    int size;
} Stack;

void init_stack(Stack *s, int size)
{
    s->data = (int*)malloc(size * sizeof(int));
    s->top = -1;
    s->size = size;
}

int push(Stack *s, int value)
{
    if (s->top >= s->size - 1) {
        printf("Error: stack overflow\n");
        return -1;
    } else {
        s->top++;
        s->data[s->top] = value;
        return 0;
    }
}

int pop(Stack *s)
{
    if (s->top <= -1) {
        printf("Error: stack underflow\n");
        return -1;
    } else {
        int value = s->data[s->top];
        s->top--;
        return value;
    }
}

void destroy_stack(Stack *s)
{
    free(s->data);
}

int main()
{
    Stack s;
    init_stack(&s, STACK_SIZE);

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

    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));

    destroy_stack(&s);

    return 0;
}

该示例中，我们创建一个栈，并将三个元素压入栈中。然后我们依次弹出这三个元素，它们的值分别为30、20、10。 最后，我们销毁栈并释放存储元素的内存。

示例2：栈的括号匹配

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

#define STACK_SIZE 100

typedef struct {
    char *data;
    int top;
    int size;
} Stack;

void init_stack(Stack *s, int size)
{
    s->data = (char*)malloc(size * sizeof(char));
    s->top = -1;
    s->size = size;
}

int push(Stack *s, char value)
{
    if (s->top >= s->size - 1) {
        printf("Error: stack overflow\n");
        return -1;
    } else {
        s->top++;
        s->data[s->top] = value;
        return 0;
    }
}

char pop(Stack *s)
{
    if (s->top <= -1) {
        printf("Error: stack underflow\n");
        return -1;
    } else {
        char value = s->data[s->top];
        s->top--;
        return value;
    }
}

void destroy_stack(Stack *s)
{
    free(s->data);
}

int is_matching_pair(char left, char right)
{
    if (left == '(' && right == ')') {
        return 1;
    } else if (left == '[' && right == ']') {
        return 1;
    } else if (left == '{' && right == '}') {
        return 1;
    } else {
        return 0;
    }
}

int is_balanced(char *expression)
{
    Stack s;
    init_stack(&s, STACK_SIZE);

    for (int i = 0; i < strlen(expression); i++) {
        if (expression[i] == '(' || expression[i] == '[' || expression[i] == '{') {
            push(&s, expression[i]);
        } else if (expression[i] == ')' || expression[i] == ']' || expression[i] == '}') {
            if (s.top == -1 || !is_matching_pair(pop(&s), expression[i])) {
                return 0;
            }
        }
    }

    if (s.top == -1) {
        return 1;
    } else {
        return 0;
    }

    destroy_stack(&s);
}

int main()
{
    char expression[100];
    printf("Enter an expression: ");
    fgets(expression, 100, stdin);
    if (is_balanced(expression)) {
        printf("The expression is balanced.\n");
    } else {
        printf("The expression is not balanced.\n");
    }
    return 0;
}

该示例中，我们利用栈实现了一个括号匹配的程序。我们首先定义了一个函数 is_matching_pair，用于判断左括号和右括号是否匹配。然后我们构建了一个函数 is_balanced，用于检查传入的表达式是否是平衡的，即每个左括号都有一个匹配的右括号。我们遍历输入字符串中的每个字符。如果字符是左括号，我们将它压入栈中。如果字符是右括号，我们弹出栈顶元素并检查它是否与当前字符匹配。如果弹出的栈顶元素与当前字符不匹配或者栈为空，我们就表示该表达式不是平衡的。

总结

这个示例为你展示了如何在C语言中实现一个简单的栈数据结构。你可以使用这个栈来实现许多有趣的算法和数据结构，例如：表达式求值、字符串反转、逆波兰表达式等。