栈（Stack）是一种重要的数据结构，它具有后进先出（Last In First Out，LIFO）的特性，就像一个只能在一端进行插入和删除操作的容器。以下是关于栈的详细介绍：
基本概念
- 栈顶：栈的一端被称为栈顶，所有的插入和删除操作都在栈顶进行。
- 栈底：与栈顶相对的另一端是栈底，栈底的元素是最先被插入到栈中的元素。
操作
- 入栈（Push）：将一个元素添加到栈顶的操作。例如，若有一个空栈，依次将元素1、2、3入栈，此时栈顶元素为3，栈底元素为1。
- 出栈（Pop）：将栈顶元素从栈中移除的操作。对于上述栈，执行一次出栈操作后，栈顶元素变为2，栈底元素仍为1。
- 查看栈顶元素（Peek）：只获取栈顶元素的值，但不移除它。在上述栈中，执行Peek操作将返回3，但栈的状态不变。
实现方式
顺序存储实现（数组）：可以使用数组来实现栈。定义一个数组来存储栈中的元素，并使用一个变量来记录栈顶的位置。入栈操作时，将元素放入数组中栈顶位置的下一个位置，并更新栈顶变量；出栈操作时，将栈顶位置的元素移除，并更新栈顶变量。以下是一个简单的Java示例：
class ArrayStack { private int[] stack; private int top; public ArrayStack(int capacity) { stack = new int[capacity]; top = -1; } public void push(int item) { if (top == stack.length - 1) { // 栈已满，可进行扩容操作 System.out.println("Stack is full."); return; } stack[++top] = item; } public int pop() { if (top == -1) { // 栈为空 System.out.println("Stack is empty."); return -1; } return stack[top--]; } public int peek() { if (top == -1) { // 栈为空 System.out.println("Stack is empty."); return -1; } return stack[top]; } }链式存储实现：也可以使用链表来实现栈。定义一个链表节点类，每个节点包含数据域和指向下一个节点的指针。栈顶指针指向链表的头节点，入栈操作时，创建一个新节点，并将其插入到链表的头部，使其成为新的栈顶；出栈操作时，移除链表的头节点，并更新栈顶指针。以下是一个简单的Java示例：
```java
class Node {
int data;
Node next;public Node(int data) {
this.data = data; this.next = null;}
}
class LinkedStack {
private Node top;
public void push(int item) {
Node newNode = new Node(item);
newNode.next = top;
top = newNode;
}
public int pop() {
if (top == null) {
// 栈为空
System.out.println("Stack is empty.");
return -1;
}
int data = top.data;
top = top.next;
return data;
}
public int peek() {
if (top == null) {
// 栈为空
System.out.println("Stack is empty.");
return -1;
}
return top.data;
}
}
```
应用场景
- 函数调用栈：在程序执行过程中，当一个函数被调用时，系统会为该函数创建一个栈帧，并将其压入函数调用栈。栈帧中包含了函数的参数、局部变量、返回地址等信息。当函数执行完毕后，对应的栈帧会被弹出，程序控制返回到调用该函数的位置。这种机制实现了函数的嵌套调用和递归调用。
- 表达式求值：栈可以用于实现表达式求值算法，如后缀表达式求值。将中缀表达式转换为后缀表达式后，利用栈来存储操作数和进行运算，可以方便地计算表达式的值。
- 括号匹配：用于检查表达式中的括号是否匹配。遍历表达式，遇到左括号时将其入栈，遇到右括号时，检查栈顶元素是否为相应的左括号，若是则出栈，否则表达式括号不匹配。
- 浏览器的后退和前进功能：浏览器的历史记录可以使用两个栈来实现。一个栈用于存储用户访问过的页面，当用户点击后退按钮时，从该栈中弹出页面；另一个栈用于存储用户点击前进按钮时需要访问的页面，当用户点击前进按钮时，从另一个栈中弹出页面。
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
