数据结构：栈 及其应用

逻辑结构：

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合 （受限的线性表）。这种数据结构只允许在栈顶进行添加（push）或删除（pop）元素的操作。栈是一种非常基础且重要的数据结构，广泛应用于计算机科学和软件开发中。

栈顶：插入和删除

栈底：固定的 不允许插入和删除

空栈：不含任何元素

栈的基本操作

1. push(element): 向栈顶添加一个元素。如果栈已满，则可能无法进行此操作。
2. pop(): 移除栈顶的元素，并返回该元素。如果栈为空，则可能无法进行此操作，并可能返回一个错误或特殊值（如null或undefined）。
3. peek() 或 top(): 返回栈顶元素的值，但不从栈中移除它。如果栈为空，则可能返回一个错误或特殊值。
4. isEmpty(): 检查栈是否为空。
5. size(): 返回栈中元素的数量。

栈的存储结构：

栈可以通过多种方式实现，包括使用数组（或列表）和链表。

顺序存储：

• 基于数组的栈（顺序栈）：在这种实现中，数组的一端被用作栈顶。添加元素时，新元素被添加到数组的末尾；移除元素时，数组的最后一个元素被移除。这种实现方式在大多数编程语言中都非常高效，因为数组的末尾操作通常很快。

初始化：

# define MaxSize 50
typedef struct
{Elemtype data[MaxSize];int top;//栈顶指针}SqStack;//iniiallize
void initStack(SqStack &s){ 
s.top=-1;
}

判断非空：

//empty
bool StackEmpty(SqStack s){if(s.top==-1)return true;elsereturn false;
}

 进栈：

//in
bool Push(SqStack &s,Elemtype e){if(s.top==MaxSize-1)return false;else{s.top++;s.data[s.top]=e;}return true;}

进栈和出栈的操作 根据s.top的初始值不同而不同：
s.top=-1先指针+1再进栈，先出栈再指针-1；

s.top=0先进栈再指针+1，先指针-1再出栈； 

 出栈：

bool Pop(SqStack &s,Elemtype &e){if(s.top==-1)return false;e=s.data[s.top];s.top--;return true;
}

读取栈顶元素：

//read
bool GetTop(SqStack s,Elemtype &x){if(s.top==-1)return false;x=s.data[s.top];
return true;
}

 链式存储：

• 基于链表的栈：下列代码规定没有头结点，LHead指向栈顶元素，链表的头部被用作栈顶。添加元素时，新元素被添加到链表的头部；移除元素时，链表的第一个元素（即头部元素）被移除。虽然链表在随机访问方面不如数组高效，但在某些情况下（如动态内存分配），链表可能更灵活。

//
typedef struct LinkNode
{Elemtype data;struct LinkNode *next;}LiStack;

栈的应用

栈的应用非常广泛，包括但不限于：

• 函数调用：

在大多数编程语言中，函数调用是通过栈来实现的。当函数被调用时，其返回地址和局部变量被推入栈中；当函数返回时，这些信息从栈中弹出。

• 表达式求值：

在编译器和解释器中，栈用于计算表达式的值。例如，在解析算术表达式时，可以使用栈来跟踪操作符和操作数。

中缀转后缀：

1）加括号：(( A +③( B *②( C -① D )))-©( E /④ F ))。

2）运算符后移：(( A ( B ( CD )-①)*②)+③( EF )/④)-⑤。

3）去除括号后，得到后缀表达式： ABCD -①*②+③ EF /④-⑤.

在计算机中，中缀表达式转后缀表达式时需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右依次扫描中缀表达式中的每一项，具体转化过程如下：
1）遇到操作数。直接加入后缀表达式。
2）遇到界限符。若为"("，则直接入栈；若为")"，则依次弹出栈中的运算符，并加入后缀表达式，直到弹出"("为止。注意，"("直接删除，不加入后缀表达式。

3）遇到运算符。若其优先级高于除"("外的栈顶运算符，则直接入栈。否则，从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到遇到一个优先级低于它的运算符或遇到"("时为止，之后将当前运算符入栈。按上述方法扫描所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

转后缀图解（例子）：

后缀表达式求值：

通过后缀表示计算表达式值的过程：从左往右依次扫描表达式的每一项，若该项是操作数，则将其压入栈中；若该项是操作符＜ op >，则从栈中退出两个操作数 Y 和 x ，形成运算指令 X < op > y ,并将计算结果压入栈中。当所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。

后缀求值图解：

• 括号匹配：

栈可以用来检查括号（如圆括号、方括号和花括号）是否正确匹配。

• 回溯算法：

在解决某些问题时（如迷宫问题、八皇后问题等），栈可以用来保存中间状态，以便在需要时回溯到之前的状态。

• 页面访问历史：

在Web浏览器中，栈可以用来保存用户访问的页面历史，以便用户可以通过“后退”按钮返回到之前的页面。

总之，栈是一种简单但功能强大的数据结构，其独特的后进先出原则使得它在许多应用场景中都非常有用。