栈和队列：数据结构中的栈操作与应用

"入栈算法-数据结构资料--3" 栈是一种特殊的数据结构，它遵循“先进后出”（FILO）或“后进先出”（LIFO）的原则。在栈中，元素的添加（称为入栈）和移除（称为出栈）只能在表的同一端进行，这一端被称为栈顶，而另一端则为栈底。当栈中没有元素时，我们称之为栈空；当栈中所有可用位置都被元素占用时，我们称之为栈满。 在计算机科学中，栈广泛应用于各种计算任务，如过程的嵌套调用和递归。在过程的嵌套调用中，每次函数调用都会将当前的返回地址、局部变量等信息压入栈中，以便在函数返回时恢复现场。递归则是函数调用自身的一种方式，每次递归调用同样会利用栈来保存状态。 **栈的存储结构** 栈有两种常见的存储方式：顺序栈和链栈。 1. **顺序栈**：使用一维数组实现，数组的一个端作为栈底，另一个端作为栈顶。初始时，栈顶指针`top`设为0，表示栈空。当`top`等于数组大小（M-1）时，栈满，再进行入栈操作会导致上溢。入栈操作是将元素存入数组的`top+1`位置并将`top`加1，出栈则是将栈顶元素弹出并减1。 入栈算法（假设数组长度为M）： ```c void push(Stack *s, int x) { if (s->top == M - 1) { // 栈满，上溢处理 printf("Stack Overflow!\n"); return; } s->top++; s->data[s->top] = x; // 将x存入栈顶 } ``` 出栈算法： ```c int pop(Stack *s) { if (s->top < 0) { // 栈空，下溢处理 printf("Stack Underflow!\n"); return INT_MIN; } int x = s->data[s->top]; // 获取栈顶元素 s->top--; return x; // 返回栈顶元素 } ``` 2. **链栈**：使用链表实现，每个节点包含一个数据域和一个指向下个节点的指针。链栈的优点在于动态扩展空间的能力，不会因预设数组大小而限制栈的容量。 链栈的节点定义： ```c typedef struct node { int data; struct node* link; } JD; ``` 链栈的入栈和出栈操作类似，但涉及节点的创建和链接，而非数组索引的修改。 **在一个程序中同时使用两个栈** 在一个程序中，可能会同时使用两个栈，例如在一个内存管理场景中，一个栈用于分配内存，另一个栈用于释放内存。这样可以有效地避免冲突，因为分配和释放操作分别在不同的栈上进行，确保了操作的独立性和安全性。 递归是栈应用的另一个重要例子。递归函数调用自身，每次调用都会将当前的状态（包括参数、局部变量等）压入栈中，直到达到基本情况（不再调用自身）。然后，栈逐级出栈，恢复之前的调用状态，直到返回最初的调用点。 以`print`函数为例，其递归地打印数字的序列： ```c void print(int w) { if (w != 0) { print(w - 1); // 递归调用 for (int i = 1; i <= w; ++i) printf("%3d,", w); printf("\n"); } } ``` 在执行过程中，栈会记录每个递归调用的状态，使得函数能够正确地回溯并完成所有必要的输出。 总结来说，栈是一种高效且灵活的数据结构，广泛应用于计算机科学的多个领域，包括算法实现、编译原理、操作系统以及图形用户界面等。理解栈的工作原理和操作方式对于解决复杂问题至关重要。