【数据结构】线性表----栈详解
栈
栈（Stack）是一种常见的数据结构，它具有**后进先出（Last In, First Out, LIFO）**的特点。栈的运作类似于物理世界中的叠盘子：最新放上去的盘子最先被拿走，而最底部的盘子最后才能被取出。
如果你先拿底下的盘子，那么就有可能出现整个盘子组全部倒塌碎落一地——这也就是所谓的栈出错。
出栈和入栈
栈有着先进后出的特点。所以它的出栈和入栈也遵循着这个特点。
我们在存取元素的时候，一般是在栈顶进行——也就是所谓的盘子顶；
而另一端称为栈底，一般就是数据结构的头结点。
入栈出栈的顺序只需记住：顺序必须有规律，例如
入栈：1234
出栈可以是：
1 432
234 1
但不能是：
3 1 4 2
栈的实现
栈既可以用数组也可以用链表形式实现，但由于栈本来就是连续的数据结构，所以使用数组刚好。如果非要使用链表，那么就使用单链表。（单链表可以解决的问题没必要使用双链表）
栈的基本操作
栈的主要操作包括：
- 入栈（Push）： 将一个元素放入栈顶。
- 出栈（Pop）： 移除并返回栈顶的元素。
- 查看栈顶元素（Peek/Top）： 返回栈顶的元素但不移除它。
- 判断栈是否为空（IsEmpty）： 检查栈中是否有元素。
- 获取栈的大小（Size）： 返回栈中元素的数量。
接下来对其进行具体介绍和代码实现。
1.初始化和前期准备
#include
#include
#include
#define MAX 100 // 栈的最大容量，根据情况设置
typedef struct {
int items[MAX];//容量
int top;//栈顶元素
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->top = -1;栈顶指针指向-1的位置
}
// 检查栈是否为空
bool isEmpty(Stack* s) {
return s->top == -1;
}
// 检查栈是否已满
bool isFull(Stack* s) {
return s->top == MAX - 1;
}
2.入栈
// 入栈
void push(Stack* s, int item) {
if (isFull(s)) {
printf("Stack overflow\n");
return;
}
s->items[++(s->top)] = item;
}
3.出栈
// 出栈
int pop(Stack* s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
return s->items[(s->top)--];
}
4.删除和插入元素
// 删除栈中的元素（第n个位置）
void deleteElement(Stack* s, int position) {
if (isEmpty(s) || position s->top)//不在栈中无法进行删除
{
printf("Invalid position\n");
return;
}
for (int i = position; i top; i++)//进行遍历寻找要删除的元素
{
s->items[i] = s->items[i + 1];
}
s->top--;
}
// 在栈中插入元素（第n个位置）
void insertElement(Stack* s, int position, int item) {
if (isFull(s))//栈溢出
{
printf("Stack overflow\n");
return;
}
if (position s->top + 1) {
printf("Invalid position\n");
return;
}
for (int i = s->top; i >= position; i--) {
s->items[i + 1] = s->items[i];
}
s->items[position] = item;
s->top++;
}
栈的使用场景
栈在计算机科学和编程中有广泛的应用，如：
- 函数调用管理： 编译器使用栈来管理函数调用和返回地址。
- 表达式求值： 中缀表达式转换为后缀表达式，以及后缀表达式求值。
- 撤销操作： 许多软件中的撤销（Undo）功能基于栈实现。
栈的注意事项
- 溢出问题： 在某些编程语言或环境中，栈的大小是有限的。如果不断入栈而不出栈，可能会导致栈溢出（Stack Overflow）。
- 访问限制： 栈只允许对栈顶进行操作，这意味着在栈中间的元素无法直接访问或修改。
- 异常处理： 在出栈或查看栈顶元素时，需要处理栈为空的情况，否则会引发错误。
另一种栈
实际上，以上都是栈在计算机科学以及数据结构中的解释，而在另一个计算机领域——计算机系统中，栈实际上是另一种事物。接下来对其进行简单的介绍。
在计算机系统中，栈（堆栈，Stack）是一种用于管理函数调用和局部变量的内存区域。它是计算机内存的一部分，负责存储函数调用过程中的临时数据，包括函数的参数、局部变量、返回地址等。
工作原理
-
栈帧（Stack Frame）：
- 每次函数调用时，都会在栈上分配一个新的栈帧。栈帧包含该函数的局部变量、参数和一些控制信息（如返回地址）。
- 函数执行完毕后，其对应的栈帧会被弹出，返回控制权给调用它的函数。
-
入栈（Push）和出栈（Pop）：
- 入栈：当一个函数被调用时，相关数据（如参数和返回地址）会被推入栈中。
- 出栈：当函数执行完毕后，其栈帧会被弹出，恢复之前的状态。
-
栈指针（Stack Pointer, SP）：
- 栈指针是一个寄存器，用于指向当前栈的顶端。每次入栈和出栈操作都会更新栈指针。
-
调用约定（Calling Convention）：
- 调用约定定义了函数如何传递参数、如何返回值以及如何维护堆栈。常见的调用约定有Cdecl、Stdcall、Fastcall等。
栈的用途
-
函数调用管理：
- 栈用于管理函数调用和返回，确保函数可以正确地调用其他函数，并在完成后返回调用点。
-
局部变量存储：
- 函数的局部变量通常存储在栈帧中，便于管理和清理。
-
递归支持：
- 栈结构天然支持递归调用，每次递归调用都会在栈上创建新的栈帧。
栈溢出（Stack Overflow）
栈的空间是有限的，如果函数调用层次过深（如递归调用过多），可能会导致栈空间耗尽，发生栈溢出。这种情况下，程序通常会崩溃或抛出异常。
这种栈的机制确保了函数调用的有序进行和局部变量的有效管理。
通过以上的介绍和代码示例，相信你对栈这种数据结构有了一个基本的了解。栈作为一种基础而重要的数据结构，我们会经常使用到它，所以需要熟练掌握。
ck Overflow）**
栈的空间是有限的，如果函数调用层次过深（如递归调用过多），可能会导致栈空间耗尽，发生栈溢出。这种情况下，程序通常会崩溃或抛出异常。
这种栈的机制确保了函数调用的有序进行和局部变量的有效管理。
通过以上的介绍和代码示例，相信你对栈这种数据结构有了一个基本的了解。栈作为一种基础而重要的数据结构，我们会经常使用到它，所以需要熟练掌握。
