数据结构中的栈（C语言版）
一.栈的概念
栈是一种常见的数据结构，它遵循后进先出的原则。栈可以看作是一种容器，其中的元素按照一种特定的顺序进行插入和删除操作。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.栈的特点
1.元素的插入和删除操作只能在栈的一端进行，该端被称为栈顶。
2.最后插入的元素是第一个被删除的元素，因此称为后进先出。
3.栈中的元素没有编号或索引，只有栈顶指针来指示栈的当前位置。
2.栈的优点
-
简单高效：栈的操作是基于后进先出（LIFO）的原则，入栈和出栈操作都只涉及栈顶元素，因此操作的时间复杂度都是O(1)，使得栈的操作非常高效。
-
空间效率高：栈的底层实现可以使用数组或链表，无论是使用静态数组还是动态链表，都可以根据实际需要灵活分配内存，因此在空间利用上比较高效。
-
递归和回溯：栈在递归和回溯算法中扮演着重要的角色。递归函数调用时会将当前函数的状态（包括局部变量、返回地址等）压入栈中，当递归函数返回时，栈顶的状态会被弹出，恢复到上一层递归函数的状态。
-
撤销操作：栈可以用于实现撤销操作，比如文本编辑器中的撤销功能。每当执行一个操作时，将操作的状态存储在栈中，当需要撤销时，只需从栈中弹出最近的状态。
3.栈的缺点
-
容量限制：栈的容量是有限的，无论是基于数组还是链表实现的栈，都会受到内存大小的限制。当栈的元素个数超过容量时，会发生栈上溢（stack overflow）的错误。
-
无随机访问：栈的特点是只能在栈顶进行插入和删除操作，没有提供随机访问的能力。如果需要访问或修改栈中的其他元素，必须先将栈顶的元素弹出，直到达到目标位置。
-
不灵活：栈的特性决定了它的使用场景受到一定的限制。对于需要随机访问、频繁插入和删除的场景，栈可能不是最佳选择。
二.栈的功能
栈作为一种数据结构，具有以下几个主要的功能：
-
入栈：将元素添加到栈的顶部（栈顶）。新元素成为栈顶，原有的栈顶元素依次向下移动。入栈操作可以用于将数据添加到栈中。
-
出栈：从栈的顶部（栈顶）移除元素。被移除的元素是最后一个入栈的元素，即栈顶元素。出栈操作会改变栈的结构，并返回被移除的元素。
-
获取栈顶元素：获取栈顶的元素，但不对栈进行修改。这个操作可以让我们查看栈顶的元素，而不改变栈的结构。
-
判断栈是否为空：检查栈是否不包含任何元素。如果栈中没有元素，即栈为空，该函数返回真；否则，返回假。
-
判断栈是否已满：检查栈是否已达到其容量上限。对于基于数组实现的栈，如果数组已满，即栈已满，该函数返回真；否则，返回假。
三.栈的实现
1.创建栈
创建一个结构体，里面的成员是数组以及指针。（在这里，为了大家能够方便理解，用静态的顺序表来实现）
#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针，指向栈顶元素的索引
} Stack;2.初始化栈
将栈顶的指针初始化为-1，表示此栈为空。
// 初始化栈
void initStack(Stack* stack) {stack->top = -1; // 栈顶指针初始化为-1，表示栈为空
}3.判断栈是否为空
判断栈是否为空。如果栈顶指针top等于-1，表示栈为空，返回1；否则，返回0。
// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1; // 栈为空时，栈顶指针为-1
}4. 判断是否已满
判断栈是否已满。如果栈顶指针top等于数组最大索引（MAX_SIZE - 1），表示栈已满，返回1；否则，返回0。
// 判断栈是否已满
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1; // 栈满时，栈顶指针等于数组最大索引
}5.入栈
入栈操作。首先使用isFull函数检查栈是否已满，如果已满，则打印错误信息并返回；否则，将栈顶指针top加1，并将元素item放入栈顶位置data[top]。
// 入栈
void push(Stack* stack, int item) {
if (isFull(stack)) {
printf("Stack overflow!\n"); // 栈已满，无法入栈
return;
}
stack->data[++stack->top] = item; // 栈顶指针加1，并将元素放入栈顶
}6.出栈
出栈操作。首先使用isEmpty函数检查栈是否为空，如果为空，则打印错误信息并返回-1；否则，返回栈顶元素data[top]，并将栈顶指针top减1。
// 出栈
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n"); // 栈为空，无法出栈
return -1;
}
return stack->data[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}7.获取栈顶元素
获取栈顶元素。首先使用isEmpty函数检查栈是否为空，如果为空，则打印错误信息并返回-1；否则，返回栈顶元素data[top]，但不修改栈的结构。
/ 获取栈顶元素
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n"); // 栈为空，无栈顶元素
return -1;
}
return stack->data[stack->top]; // 返回栈顶元素，不修改栈的结构
}8.打印栈中元素
打印栈中的元素。首先使用isEmpty函数检查栈是否为空，如果为空，则打印提示信息；否则，使用循环从栈底到栈顶依次打印栈中的元素。
/ 打印栈中的元素（用于调试）
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}四.栈的源码呈现
#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存储栈中的元素int top; // 栈顶指针，指向栈顶元素的索引
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1; // 栈顶指针初始化为-1，表示栈为空
}// 判断栈是否为空
int isEmpty(Stack* stack) {return stack->top == -1; // 栈为空时，栈顶指针为-1
}// 判断栈是否已满
int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1; // 栈满时，栈顶指针等于数组最大索引
}// 入栈
void push(Stack* stack, int item) {if (isFull(stack)) {printf("Stack overflow!\n"); // 栈已满，无法入栈return;}stack->data[++stack->top] = item; // 栈顶指针加1，并将元素放入栈顶
}// 出栈
int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack underflow!\n"); // 栈为空，无法出栈return -1;}return stack->data[stack->top--]; // 返回栈顶元素，并将栈顶指针减1
}// 获取栈顶元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n"); // 栈为空，无栈顶元素return -1;}return stack->data[stack->top]; // 返回栈顶元素，不修改栈的结构
}// 打印栈中的元素（用于调试）
void printStack(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return;}printf("Stack: ");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}// 主函数用于测试栈的功能
int main() {Stack stack;initStack(&stack); // 初始化栈push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack); // 打印栈中的元素printf("Top element: %d\n", peek(&stack)); // 获取栈顶元素while (!isEmpty(&stack)) {printf("Popped element: %d\n", pop(&stack)); // 依次出栈并输出元素}return 0;
}