一、栈的定义
栈（Stack）是一种特殊的线性数据结构，它具有后进先出（Last In First Out，LIFO）的特点。就像一摞叠起来的盘子，只能从最上面取盘子（最后放上去的盘子最先被取出）。
二、栈的基本操作
- 入栈（Push）：将一个元素添加到栈的顶部。这个操作的时间复杂度通常为 O (1)。
- 出栈（Pop）：从栈的顶部移除一个元素，并返回该元素。这个操作的时间复杂度也为 O (1)。
- 查看栈顶元素（Peek/Top）：返回栈顶的元素，但不删除它。同样时间复杂度为 O (1)。
- 判断栈是否为空（IsEmpty）：检查栈中是否没有任何元素。时间复杂度为 O (1)。
三、栈的存储方式
栈可以用数组或链表来实现。
- 数组实现：
- 可以定义一个固定大小的数组来存储栈中的元素。需要一个变量来记录栈顶的位置。
- 入栈操作就是将元素放入数组中当前栈顶位置，并更新栈顶指针。
- 出栈操作则是取出栈顶元素，并将栈顶指针减一。
- 优点是实现简单，访问元素速度快。缺点是如果定义的数组大小不够大，可能会出现栈溢出；如果定义的数组过大，又会浪费空间。
- 链表实现：
- 每个节点包含一个数据元素和一个指向下一个节点的指针。栈顶就是链表的头部。
- 入栈操作就是在链表头部添加一个新节点。
- 出栈操作就是删除链表头部的节点。
- 优点是可以动态地调整栈的大小，不会出现栈溢出的情况。缺点是需要额外的空间来存储指针，访问元素的速度相对较慢。
四、栈的应用场景
- 表达式求值：在编译器中，用于解析和计算算术表达式。例如，将中缀表达式转换为后缀表达式，然后利用栈进行计算。
- 函数调用：在程序执行过程中，函数的调用和返回可以用栈来管理。每次调用一个函数时，将函数的参数、局部变量等信息压入栈中，当函数返回时，这些信息从栈中弹出。
- 深度优先搜索：在图的遍历和搜索算法中，栈可以用来实现深度优先搜索。每次访问一个节点时，将该节点压入栈中，然后继续访问其未被访问过的邻接节点。当没有更多的邻接节点可访问时，从栈中弹出一个节点，继续搜索。
- 回溯算法：在解决一些组合问题和搜索问题时，栈可以用来记录搜索路径，当需要回溯时，从栈中弹出上一步的状态。
五、代码实现
以下是用 Java 语言实现栈的代码示例：
class Stack<T> {
private int top;
private T[] stack;
private int capacity;
@SuppressWarnings("unchecked")
public Stack(int capacity) {
this.capacity = capacity;
stack = (T[]) new Object[capacity];
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
public void push(T item) {
if (isFull()) {
throw new RuntimeException("Stack is full");
}
stack[++top] = item;
}
public T pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top--];
}
public T peek() {
if (isEmpty()) {
throw new RuntimeException("Stack is empty");
}
return stack[top];
}
}
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>(5);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素：" + stack.peek());
System.out.println("弹出元素：" + stack.pop());
System.out.println("栈顶元素：" + stack.peek());
System.out.println("栈是否为空：" + stack.isEmpty());
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
评论（0）