数据结构的栈

栈（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;
}

}
```

应用场景

• 函数调用栈：在程序执行过程中，当一个函数被调用时，系统会为该函数创建一个栈帧，并将其压入函数调用栈。栈帧中包含了函数的参数、局部变量、返回地址等信息。当函数执行完毕后，对应的栈帧会被弹出，程序控制返回到调用该函数的位置。这种机制实现了函数的嵌套调用和递归调用。
• 表达式求值：栈可以用于实现表达式求值算法，如后缀表达式求值。将中缀表达式转换为后缀表达式后，利用栈来存储操作数和进行运算，可以方便地计算表达式的值。
• 括号匹配：用于检查表达式中的括号是否匹配。遍历表达式，遇到左括号时将其入栈，遇到右括号时，检查栈顶元素是否为相应的左括号，若是则出栈，否则表达式括号不匹配。
• 浏览器的后退和前进功能：浏览器的历史记录可以使用两个栈来实现。一个栈用于存储用户访问过的页面，当用户点击后退按钮时，从该栈中弹出页面；另一个栈用于存储用户点击前进按钮时需要访问的页面，当用户点击前进按钮时，从另一个栈中弹出页面。

栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。