怎样在 C 语言中实现栈？

🍅关注博主🎗️ 带你畅游技术世界，不错过每一次成长机会！
📙C 语言百万年薪修炼课程 通俗易懂，深入浅出，匠心打磨，死磕细节，6年迭代，看过的人都说好。

分割线

文章目录

如何在 C 语言中实现栈
一、栈的基本概念
二、栈的操作
三、使用数组实现栈
四、使用链表实现栈
五、两种实现方式的比较
- （一）空间复杂度
- （二）时间复杂度
- （三）灵活性
- （四）适用场景
六、栈的应用场景
- （一）函数调用
- （二）表达式求值
- （三）括号匹配
- （四）回溯算法
七、总结

分割线

如何在 C 语言中实现栈

在 C 语言中，栈（Stack）是一种常见的数据结构，它遵循后进先出（Last In First Out，LIFO）的原则。这意味着最后添加到栈中的元素将首先被移除。

一、栈的基本概念

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

栈顶（Top）：栈的顶部元素，是进行插入和删除操作的一端。
栈底（Bottom）：栈的底部元素，是相对固定的一端。

二、栈的操作

常见的栈操作包括：

push：将元素压入栈顶。
pop：弹出栈顶元素。
peek（或者 top）：获取栈顶元素但不弹出。
isEmpty：判断栈是否为空。

三、使用数组实现栈

以下是使用数组来实现栈的 C 语言代码示例：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int items[MAX_SIZE];int top;
} Stack;// 初始化栈
void initStack(Stack *stack) {stack->top = -1;
}// 判断栈是否为空
bool isEmpty(Stack *stack) {return stack->top == -1;
}// 判断栈是否已满
bool isFull(Stack *stack) {return stack->top == MAX_SIZE - 1;
}// 压入元素到栈
void push(Stack *stack, int element) {if (isFull(stack)) {printf("Stack Overflow!\n");return;}stack->items[++stack->top] = element;
}// 弹出栈顶元素
int pop(Stack *stack) {if (isEmpty(stack)) {printf("Stack Underflow!\n");return -1;}int element = stack->items[stack->top];stack->top--;return element;
}// 获取栈顶元素但不弹出
int peek(Stack *stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return -1;}return stack->items[stack->top];
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("Top element: %d\n", peek(&stack));int poppedElement = pop(&stack);if (poppedElement!= -1) {printf("Popped element: %d\n", poppedElement);}printf("Top element after pop: %d\n", peek(&stack));return 0;
}

在上述代码中：

initStack 函数用于初始化栈，将栈顶指针设置为 -1，表示栈为空。
isEmpty 函数通过检查栈顶指针是否为 -1 来判断栈是否为空。
isFull 函数通过检查栈顶指针是否达到数组的最大索引来判断栈是否已满。
push 函数在压入元素之前，先检查栈是否已满。如果未满，将元素添加到栈顶，并更新栈顶指针。
pop 函数在弹出元素之前，先检查栈是否为空。如果不为空，返回栈顶元素，并更新栈顶指针。
peek 函数返回栈顶元素，但不修改栈的状态。

四、使用链表实现栈

除了使用数组，我们还可以使用链表来实现栈。以下是使用链表实现栈的 C 语言代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node *next;
} Node;typedef struct {Node *top;
} Stack;// 初始化栈
void initStack(Stack *stack) {stack->top = NULL;
}// 判断栈是否为空
bool isEmpty(Stack *stack) {return stack->top == NULL;
}// 压入元素到栈
void push(Stack *stack, int element) {Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) {printf("Memory allocation failed!\n");return;}newNode->data = element;newNode->next = stack->top;stack->top = newNode;
}// 弹出栈顶元素
int pop(Stack *stack) {if (isEmpty(stack)) {printf("Stack Underflow!\n");return -1;}Node *temp = stack->top;int element = temp->data;stack->top = stack->top->next;free(temp);return element;
}// 获取栈顶元素但不弹出
int peek(Stack *stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return -1;}return stack->top->data;
}// 打印栈
void printStack(Stack *stack) {Node *current = stack->top;printf("Stack: ");while (current!= NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack);int poppedElement = pop(&stack);if (poppedElement!= -1) {printf("Popped element: %d\n", poppedElement);}printStack(&stack);printf("Top element: %d\n", peek(&stack));return 0;
}

在这个链表实现的栈中：

每个节点包含数据和指向下一个节点的指针。
initStack 函数将栈顶指针初始化为 NULL，表示空栈。
push 函数创建一个新节点，将其数据设置为要压入的元素，并将其链接到当前栈顶节点之前，更新栈顶指针。
pop 函数如果栈不为空，删除栈顶节点，返回其数据，并更新栈顶指针，同时释放已删除节点的内存。
peek 函数返回栈顶节点的数据。
printStack 函数用于打印栈中的所有元素。

五、两种实现方式的比较

（一）空间复杂度

数组实现：在创建栈时需要预先分配固定大小的连续内存空间。如果栈的实际使用空间小于预分配的空间，会造成一定的内存浪费；如果栈的实际使用空间超过预分配的空间，还需要进行扩容操作，可能涉及到数据的复制和内存的重新分配，增加了额外的开销。
链表实现：每个节点在需要时动态分配内存，不会造成内存的预先浪费。但是，每个节点除了存储数据外，还需要额外的空间来存储指针，因此会有一些额外的内存开销。

（二）时间复杂度

数组实现：
- push 操作：在栈未满的情况下，时间复杂度为 O(1)。
- pop 操作：在栈不为空的情况下，时间复杂度为 O(1)。
- 访问栈顶元素：时间复杂度为 O(1)。
链表实现：
- push 操作：需要创建新节点并更新指针，时间复杂度为 O(1)。
- pop 操作：需要删除节点并更新指针，时间复杂度为 O(1)。
- 访问栈顶元素：时间复杂度为 O(1)。