C语言数据结构 栈的基础操作

1. 栈的基本概念

栈（Stack）是一种基于LIFO（后进先出）原理的数据结构，类似于一组盘子，只能在盘子的顶部进行操作。每次从顶部添加或移除盘子。

栈具有两个基本操作：入栈（push）和出栈（pop）。当添加一个元素时，我们称其为“push”，当移除一个元素时，我们称其为“pop”。

2. 栈的实现

栈可以使用数组或链表来实现。

2.1 使用数组

使用数组实现栈时，我们可以在数组的末尾添加新元素，同时在末尾移除元素。

以下是使用数组实现栈的基本操作代码：

#define MAXSIZE 100 //定义栈的最大长度

typedef struct {
    int data[MAXSIZE]; // 存放栈中元素的数组
    int top; // 栈顶下标，如果top等于-1，则表示栈为空
} Stack;

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

int isEmpty(Stack s) {
    return s.top == -1;
}

int isFull(Stack s) {
    return s.top == MAXSIZE - 1;
}

int push(Stack *s, int data) {
    if (isFull(*s)) {
        return 0;
    }
    s->data[++s->top] = data;
    return 1;
}

int pop(Stack *s) {
    if (isEmpty(*s)) {
        return 0;
    }
    --s->top;
    return s->data[s->top + 1];
}

2.2 使用链表

使用链表实现栈时，我们可以在链表的头部添加新元素，同时在头部移除元素。

以下是使用链表实现栈的基本操作代码：

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;
}

int push(Stack *s, int data) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = data;
    node->next = s->top;
    s->top = node;
    return 1;
}

int pop(Stack *s) {
    if (isEmpty(*s)) {
        return 0;
    }
    Node *node = s->top;
    int data = node->data;
    s->top = node->next;
    free(node);
    return data;
}

3. 栈的示例

3.1 判断字符串括号是否匹配

使用栈可以很容易地判断字符串中的括号是否匹配。我们可以将每个左括号入栈，在遇到一个右括号时，弹出栈顶元素并检查是否是相应的左括号。如果不匹配，则说明字符串中的括号不是匹配的。

以下是判断字符串括号是否匹配的代码：

int isMatch(char *s) {
    Stack stack;
    initStack(&stack);
    while (*s != '\0') {
        if (*s == '(' || *s == '[' || *s == '{') {
            push(&stack, *s);
        } else if ((*s == ')' && !isEmpty(stack) && stack.top->data == '(') ||
                   (*s == ']' && !isEmpty(stack) && stack.top->data == '[') ||
                   (*s == '}' && !isEmpty(stack) && stack.top->data == '{')) {
            pop(&stack);
        } else {
            return 0; // 括号不匹配
        }
        ++s;
    }
    return isEmpty(stack);
}

3.2 倒转栈中的元素

我们可以倒转栈中的元素，将栈底元素变成栈顶元素。

以下是倒转栈中元素的代码：

void reverse(Stack *s) {
    if (isEmpty(*s)) {
        return;
    }
    int data = pop(s);
    reverse(s);
    push(s, data);
}

4. 总结

栈是一种基本的数据结构，是许多算法的基础。我们可以使用数组或链表来实现栈，并进行基本操作，如入栈和出栈。同时，栈还可以解决许多实际问题，如括号匹配、表达式求值等。