C语言数据结构之栈简单操作

C语言数据结构之栈简单操作

什么是栈？

栈（Stack）是一种线性数据结构，它具有“后进先出”（Last-In-First-Out）的特性。栈顶是栈的一端，另一端称为栈底。每次只能从栈顶插入数据（入栈）或者从栈顶取出数据（出栈）。

栈的简单操作

栈的简单操作包括：

1. 初始化栈
2. 判断栈是否为空
3. 判断栈是否已满
4. 入栈操作
5. 出栈操作
6. 获取栈顶元素

栈的初始化

栈的初始化可以通过动态分配内存的方式来实现。代码如下：

#define MAXSIZE 100
typedef int ElemType;

typedef struct {
    ElemType data[MAXSIZE];  // 存放栈数据
    int top;  // 栈顶指针
} SqStack;

// 初始化栈
void InitStack(SqStack *S) {
    S->top = -1;  // 栈顶指针初始化为-1，表示栈为空
}

判断栈是否为空

栈是否为空可以通过栈顶指针判断。如果栈顶指针等于-1，表示栈为空，否则栈不为空。代码如下：

// 判断栈是否为空
int IsEmpty(SqStack S) {
    if (S.top == -1) {
        return 1;  // 栈为空
    }
    return 0;  // 栈不为空
}

判断栈是否已满

静态数组实现的栈可以通过数组下标来判断栈是否已满。如果栈顶指针等于MAXSIZE-1，表示栈已满，否则栈未满。代码如下：

// 判断栈是否已满
int IsFull(SqStack S) {
    if (S.top == MAXSIZE-1) {
        return 1;  // 栈已满
    }
    return 0;  // 栈未满
}

入栈操作

入栈操作是将一个元素压入栈顶。入栈操作需要先判断栈是否已满。如果栈未满，将元素插入到栈顶，并将栈顶指针加1。代码如下：

// 入栈操作
int Push(SqStack *S, ElemType x) {
    if (IsFull(*S)) {
        return 0;  // 栈已满，入栈失败
    }
    S->top++;  // 栈顶指针加1
    S->data[S->top] = x;  // 将元素压入栈顶
    return 1;  // 入栈成功
}

出栈操作

出栈操作是将栈顶元素弹出。出栈操作需要先判断栈是否为空。如果栈非空，将栈顶元素弹出，并将栈顶指针减1。代码如下：

// 出栈操作
int Pop(SqStack *S, ElemType *x) {
    if (IsEmpty(*S)) {
        return 0;  // 栈为空，出栈失败
    }
    *x = S->data[S->top];  // 将栈顶元素弹出
    S->top--;  // 栈顶指针减1
    return 1;  // 出栈成功
}

获取栈顶元素

获取栈顶元素是返回栈顶元素的值，但不弹出栈顶元素。获取栈顶元素需要先判断栈是否为空。如果栈非空，返回栈顶元素的值。代码如下：

// 获取栈顶元素
int GetTop(SqStack S, ElemType *x) {
    if (IsEmpty(S)) {
        return 0;  // 栈为空，获取栈顶元素失败
    }
    *x = S.data[S.top];  // 返回栈顶元素的值
    return 1;  // 获取栈顶元素成功
}

示例说明

示例1：用栈模拟简单计算器

现在有一个简单的计算器，只支持+、-、*、/四则运算，不支持括号，我们需要用栈来模拟它。假设用户输入的表达式存放在一个字符数组exp中，我们可以通过以下步骤来实现：

1. 初始化栈S。
2. 从左到右遍历exp，依次读取每个字符。
3. 如果字符是数字字符，则将其转换为整数，并入栈S。
4. 如果字符是操作符，则从栈S中弹出两个操作数，进行计算，将计算结果压入栈S。
5. 最后栈顶就是表达式计算结果。

具体实现可以参考以下代码：

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

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;
} SqStack;

void InitStack(SqStack *S) {
    S->top = -1;
}

int IsEmpty(SqStack S) {
    if (S.top == -1) {
        return 1;
    }
    return 0;
}

int IsFull(SqStack S) {
    if (S.top == MAXSIZE-1) {
        return 1;
    }
    return 0;
}

int Push(SqStack *S, int x) {
    if (IsFull(*S)) {
        return 0;
    }
    S->top++;
    S->data[S->top] = x;
    return 1;
}

int Pop(SqStack *S, int *x) {
    if (IsEmpty(*S)) {
        return 0;
    }
    *x = S->data[S->top];
    S->top--;
    return 1;
}

int GetTop(SqStack S, int *x) {
    if (IsEmpty(S)) {
        return 0;
    }
    *x = S.data[S.top];
    return 1;
}

int main() {
    SqStack S;
    InitStack(&S);
    char exp[MAXSIZE];
    printf("请输入表达式：");
    fgets(exp, MAXSIZE, stdin);
    int len = strlen(exp);
    int i, num1, num2, result;
    for (i = 0; i < len; i++) {
        if (exp[i] >= '0' && exp[i] <= '9') {  // 如果是数字字符
            int num = exp[i] - '0';
            Push(&S, num);
        } else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {  // 如果是操作符
            Pop(&S, &num2);
            Pop(&S, &num1);
            switch (exp[i]) {  // 根据操作符进行计算
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num1 / num2;
                    break;
            }
            Push(&S, result);
        }
    }
    GetTop(S, &result);
    printf("计算结果：%d\n", result);
    return 0;
}

示例2：判断括号是否匹配

现在有一个括号字符串，我们需要用栈来判断其中的括号是否匹配。假设括号字符串存放在一个字符数组str中，我们可以通过以下步骤来实现：

1. 初始化栈S。
2. 从左到右遍历str，依次读取每个字符。
3. 如果字符是左括号，入栈S。
4. 如果字符是右括号，从栈S中弹出一个左括号，判断两者是否匹配。
5. 遍历完成后，如果栈S非空，则括号不匹配，否则括号匹配。

具体实现可以参考以下代码：

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

#define MAXSIZE 100

typedef struct {
    char data[MAXSIZE];
    int top;
} SqStack;

void InitStack(SqStack *S) {
    S->top = -1;
}

int IsEmpty(SqStack S) {
    if (S.top == -1) {
        return 1;
    }
    return 0;
}

int IsFull(SqStack S) {
    if (S.top == MAXSIZE-1) {
        return 1;
    }
    return 0;
}

int Push(SqStack *S, char x) {
    if (IsFull(*S)) {
        return 0;
    }
    S->top++;
    S->data[S->top] = x;
    return 1;
}

int Pop(SqStack *S, char *x) {
    if (IsEmpty(*S)) {
        return 0;
    }
    *x = S->data[S->top];
    S->top--;
    return 1;
}

int GetTop(SqStack S, char *x) {
    if (IsEmpty(S)) {
        return 0;
    }
    *x = S.data[S.top];
    return 1;
}

int main() {
    SqStack S;
    InitStack(&S);
    char str[MAXSIZE];
    printf("请输入括号字符串：");
    fgets(str, MAXSIZE, stdin);
    int len = strlen(str);
    int i;
    char ch, top;
    for (i = 0; i < len-1; i++) {
        ch = str[i];
        if (ch == '(' || ch == '[' || ch == '{') {  // 如果是左括号
            Push(&S, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {  // 如果是右括号
            if (IsEmpty(S)) {
                printf("括号不匹配\n");
                return 0;
            }
            Pop(&S, &top);
            if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {
                printf("括号不匹配\n");
                return 0;
            }
        }
    }
    if (!IsEmpty(S)) {
        printf("括号不匹配\n");
        return 0;
    }
    printf("括号匹配\n");
    return 0;
}

总结

本文主要介绍了栈（Stack）的基本概念和简单操作，包括栈的初始化、判断栈是否为空、判断栈是否已满、入栈操作、出栈操作、获取栈顶元素等。栈是一种非常常用的数据结构，它可以用于解决很多实际问题，例如用栈模拟计算器、用栈判断括号是否匹配等。通过本文的介绍，相信读者已经对栈有了更深入的了解，可以更加灵活地使用栈来解决实际问题。