C语言用指针支持栈

C语言用指针支持栈的完整使用攻略

栈是一种常见的数据结构，在C语言中可以使用指针来支持栈。下面是用指针实现栈的完整使用攻略：

数据结构

栈是一种后进先出（LIFO）的数据结构，可以用数组或链表实现。这里我们使用数组实现栈。

定义栈结构体：

#define MAXSIZE 10 // 栈的容量
typedef struct stack {
    int data[MAXSIZE]; // 存储数据的数组
    int top; // 栈顶指针
} Stack;

data数组用来存储栈中的数据，top指针指向栈顶元素。

核心操作

栈的核心操作有两个：入栈和出栈。

• 入栈操作

入栈操作将元素压入栈顶，同时将栈顶指针向上移动一个位置。

void push(Stack *s, int value) {
    if (s->top == MAXSIZE) {
        printf("Stack is full.\n");
        return;
    }
    s->data[s->top++] = value;
}

• 出栈操作

出栈操作将栈顶元素弹出，同时将栈顶指针向下移动一个位置。

int pop(Stack *s) {
    if (s->top == 0) {
        printf("Stack is empty.\n");
        return -1;
    }
    return s->data[--s->top];
}

示例说明

下面是两个示例，说明如何使用指针实现栈。

示例1：使用栈计算表达式

将中缀表达式转换为后缀表达式，再根据后缀表达式计算结果。中缀表达式需要使用栈来转换为后缀表达式，后缀表达式需要使用栈来计算。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h> // 包含isdigit()函数

#define MAXSIZE 10

typedef struct stack {
    int data[MAXSIZE];
    int top;
} Stack;

int priority(char c) { // 计算运算符优先级
    if (c == '(') {
        return 0;
    } else if (c == '+' || c == '-') {
        return 1;
    } else if (c == '*' || c == '/') {
        return 2;
    } else {
        return -1; // 非法运算符
    }
}

void infix_to_postfix(char *infix, char *postfix) {
    Stack s;
    s.top = 0;
    int i = 0, j = 0;
    char c;

    while ((c = infix[i++]) != '\0') {
        if (isdigit(c)) {
            postfix[j++] = c; // 直接输出数字
        } else if (c == '(') {
            push(&s, c); // 左括号入栈
        } else if (c == ')') {
            while ((c = pop(&s)) != '(') {
                postfix[j++] = c; // 弹出栈顶运算符并输出
            }
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (s.top != 0 && priority(c) <= priority(s.data[s.top-1])) {
                postfix[j++] = pop(&s); // 弹出栈顶运算符并输出
            }
            push(&s, c); // 运算符入栈
        } else {
            printf("Invalid input.\n");
            exit(EXIT_FAILURE);
        }
    }

    while (s.top != 0) {
        postfix[j++] = pop(&s); // 弹出栈中剩余的运算符并输出
    }
    postfix[j] = '\0';
}

int calculate(char *postfix) {
    Stack s;
    s.top = 0;
    int i = 0, a, b;

    while (postfix[i] != '\0') {
        if (isdigit(postfix[i])) {
            push(&s, postfix[i]-'0'); // 数字直接入栈
        } else {
            b = pop(&s);
            a = pop(&s);
            switch (postfix[i]) { // 计算栈顶两个元素的运算结果
                case '+': push(&s, a+b); break;
                case '-': push(&s, a-b); break;
                case '*': push(&s, a*b); break;
                case '/': push(&s, a/b); break;
                default: printf("Invalid postfix expression.\n"); exit(EXIT_FAILURE);
            }
        }
        i++;
    }

    return pop(&s);
}

int main(void) {
    char infix[MAXSIZE];
    char postfix[MAXSIZE];
    printf("Input an infix expression: ");
    fgets(infix, MAXSIZE, stdin);
    infix_to_postfix(infix, postfix);
    printf("The postfix expression is: %s\n", postfix);
    printf("The result is: %d\n", calculate(postfix));
    return 0;
}

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

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

#define MAXSIZE 10

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

int is_left_bracket(char c) {
    return (c == '(' || c == '[' || c == '{');
}

int is_right_bracket(char c) {
    return (c == ')' || c == ']' || c == '}');
}

int match(char left, char right) {
    switch (left) {
        case '(': return (right == ')');
        case '[': return (right == ']');
        case '{': return (right == '}');
        default: return 0;
    }
}

int check_brackets(char *str) {
    Stack s;
    s.top = 0;
    int i = 0;
    char c;

    while ((c = str[i++]) != '\0') {
        if (is_left_bracket(c)) {
            push(&s, c);
        } else if (is_right_bracket(c)) {
            if (s.top == 0 || !match(pop(&s), c)) {
                return 0; // 不匹配
            }
        }
    }

    return (s.top == 0); // 栈为空则匹配
}

int main(void) {
    char str[MAXSIZE];
    printf("Input a string: ");
    fgets(str, MAXSIZE, stdin);
    if (check_brackets(str)) {
        printf("All brackets match.\n");
    } else {
        printf("Not all brackets match.\n");
    }
    return 0;
}

以上就是使用指针实现栈的完整使用攻略，这里只列举了两个简单的示例，实际上栈还可以用来解决很多实际问题，比如回文判断、计算器等。