数据结构：栈

---

栈

一，概述

栈（Stack）是一种特殊的线性表，它只允许在一端进行插入和删除操作，通常被称为“后进先出”（Last In First Out，LIFO）的数据结构。

栈由一系列元素组成，每个元素具有一个唯一的标识符，称为“栈顶”。栈顶是栈中最后一个被插入的元素，也是下一个要被删除的元素。栈中的元素按照后进先出的顺序排列。

栈的主要操作包括：

1. 入栈（Push）：将一个元素插入到栈顶。
2. 出栈（Pop）：删除栈顶元素并返回它。
3. 查看栈顶（Peek/Top）：返回当前栈顶元素但不删除它。
4. 判断栈是否为空（IsEmpty）。

栈在计算机科学中有广泛的应用，包括：

1. 函数调用和递归：在函数调用过程中，将参数和局部变量压入栈中，当函数执行完毕时，将它们从栈中弹出。递归函数也可以使用栈来保存中间结果。
2. 表达式求值：在算术表达式求值过程中，操作数和运算符被压入栈中，然后使用栈中的元素进行计算。
3. 括号匹配：在程序设计中，使用栈来检查括号是否匹配。
4. 后进先出数据结构：栈可以用于实现后进先出的数据结构，如浏览器的前进/后退功能、撤销/重做操作等。
5. 内存管理：操作系统使用栈来管理程序的内存分配和释放。当一个函数被调用时，它的代码和数据被压入栈中；当函数执行完毕时，它们被从栈中弹出并释放内存。

总之，栈是一种非常有用的数据结构，在计算机科学中有广泛的应用。

简介：

• 栈是一种线性数据结构，意味着数据在栈中的排序是按照它们加入的顺序。
• 栈遵循 LIFO（Last In First Out）原则，这意味着最后一个添加到栈中的元素将是第一个被移除的元素。
• 栈只允许在同一端（称为“顶部”）进行添加和删除操作。这一端通常被称为“栈顶”，另一端被称为“栈底”。
• 栈不需要在添加或删除元素时进行任何排序或搜索操作。

图示：

      top
    +-----+  
    |     |  
    |  3  |  
    +-----+  
    |     |  
    |  2  |  
    +-----+  
    |     |  
bottom|  1  |  
    +-----+
1
2
3
4
5
6
7
8
9
10
11

在这个栈的示例中，元素1、2、3依次被推入栈顶。当元素3被推入时，元素1和2仍然在栈中，但它们现在处于元素3的下方。如果我们要从栈中删除一个元素，元素3将会首先被删除，然后是元素2和1。这就是后进先出（LIFO）的原则。

Java示例：

在Java中，可以使用java.util.Stack类来实现栈。以下是一个简单的示例：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1); // 压入元素1
        stack.push(2); // 压入元素2
        stack.push(3); // 压入元素3
        System.out.println("Initial Stack: " + stack); // 打印初始栈
        System.out.println("Popped element: " + stack.pop()); // 弹出顶部元素并打印
        System.out.println("Stack after pop operation: " + stack); // 打印执行弹出操作后的栈
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在这个示例中，我们首先创建了一个整数类型的栈，然后将元素1、2、3压入栈中。然后我们打印出初始的栈，执行弹出操作并打印出弹出的元素，最后再次打印出执行弹出操作后的栈。

二，添加数据

在Java中，我们可以使用java.util.Stack类来实现栈数据结构。以下是添加数据（压入元素）的示例：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 添加元素到栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 打印栈
        System.out.println("Initial Stack: " + stack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这个示例中，我们首先导入了java.util.Stack类。然后，在main方法中，我们创建了一个整数类型的栈实例stack。我们使用push方法向栈中添加元素。最后，我们打印出初始的栈。

请注意，尽管java.util.Stack类是Java早期版本提供的，但现在并不推荐使用它。在多线程环境中，它的性能可能会有问题。在Java的后续版本中，建议使用java.util.Deque接口的实现，如java.util.ArrayDeque，来代替java.util.Stack。以下是使用ArrayDeque实现栈的示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 添加元素到栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 打印栈
        System.out.println("Initial Stack: " + stack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这个示例中，我们使用了java.util.ArrayDeque类来实现栈。与上面的示例类似，我们使用push方法向栈中添加元素，并打印出初始的栈。

三，删除数据

在Java中，我们可以使用java.util.Stack类来实现栈数据结构。以下是删除数据（弹出元素）的示例：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 添加元素到栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 打印初始栈
        System.out.println("Initial Stack: " + stack);

        // 删除元素（弹出）
        System.out.println("Popped element: " + stack.pop());

        // 打印执行弹出操作后的栈
        System.out.println("Stack after pop operation: " + stack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在这个示例中，首先导入了java.util.Stack类。然后，在main方法中，创建了一个整数类型的栈实例stack。使用push方法向栈中添加元素。然后，使用pop方法删除（弹出）栈顶的元素。最后，打印出执行弹出操作后的栈。

请注意，尽管java.util.Stack类是Java早期版本提供的，但现在并不推荐使用它。在多线程环境中，它的性能可能会有问题。在Java的后续版本中，建议使用java.util.Deque接口的实现，如java.util.ArrayDeque，来代替java.util.Stack。以下是使用ArrayDeque实现栈的示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 添加元素到栈
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 打印初始栈
        System.out.println("Initial Stack: " + stack);

        // 删除元素（弹出）
        System.out.println("Popped element: " + stack.pop());

        // 打印执行弹出操作后的栈
        System.out.println("Stack after pop operation: " + stack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

在这个示例中，使用了java.util.ArrayDeque类来实现栈。与上面的示例类似，使用push方法向栈中添加元素，并使用pop方法删除（弹出）栈顶的元素。最后，打印出执行弹出操作后的栈。