前言

栈（stack）是一种线性数据的逻辑存储结构。栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

1. 概念

它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。如下图所示，向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。特点是先进后出。在这里插入图片描述

2. 存储原理

栈是逻辑结构，底层存储结构，既可以用数组来实现，也可以用链表来实现。

2.1 数组实现

栈的数组实现如下，数组实现的栈也叫顺序栈或静态栈：
在这里插入图片描述

2.2 链表实现

栈的链表实现如下，链表实现的栈也叫做链式栈或动态栈：
在这里插入图片描述

3. 操作

下面代码演示以数组为底层存储结构为例，链表代码逻辑类似。

3.1 定义栈

package org.wanlong.stack;/*** @author wanlong* @version 1.0* @description: 数组实现的栈* @date 2023/5/22 19:04*/
public class ArrayStack {//私有化数组，禁止外部直接访问，限制对数组的操作只能通过，提供的出栈，入栈操作实现private Object[] nums; // 数组private int count; // 栈中元素个数// 初始化数组，申请一个大小为n的数组空间public ArrayStack(int n) {this.nums = new Object[n];this.count = 0;}
}

3.2 入栈


/*** @Description:入栈操作* @Author: wanlong* @Date: 2023/5/22 19:08* @param n:  入栈元素* @return boolean**/
public boolean push(Object n) {// 数组空间不够了，直接返回false，入栈失败。 这里不扩容，后续可以完善代码实现扩容if (count >= nums.length)return false;// 将item放到下标为count的位置，并且count加一nums[count] = n;count++;return true;
}

3.3 出栈

/*** @return Object 栈顶元素* @Description:出栈操作* @Author: wanlong* @Date: 2023/5/22 19:07**/
public Object pop() {// 栈为空，则直接返回0if (count == 0) return 0;// 返回下标为count-1的数组元素，并且栈中元素个数count减一Object n = nums[count - 1];count--;return n;
}

3.4 测试类

package org.wanlong.stack;import org.junit.BeforeClass;
import org.junit.Test;/*** @author wanlong* @version 1.0* @description: 测试栈的使用* @date 2023/5/22 19:11*/
public class Client {static ArrayStack arrayStack = new ArrayStack(10);@BeforeClasspublic static void init() {//入栈两个元素arrayStack.push(1);arrayStack.push(2);arrayStack.push(23);arrayStack.push("我是栈顶元素");}@Testpublic void testPush() {arrayStack.push(1);arrayStack.push(2);}@Testpublic void testPop() {Object pop = arrayStack.pop();System.out.println("栈顶出栈元素为:" + pop);Object pop2 = arrayStack.pop();System.out.println("出栈一个后的栈顶元素为：" + pop2);}
}

3.5 运行结果

栈顶出栈元素为:我是栈顶元素
出栈一个后的栈顶元素为：23

4. 时间复杂度

入栈和出栈的时间复杂度都是O(1)
支持动态扩容的顺序栈，因为需要扩容，所以入栈的时间复杂度是O(n)

5.应用

5.1 函数调用

每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈，我们在开发工具debug代码的典型应用。 如下图所示，即为栈帧。
在这里插入图片描述

5.2 浏览器的后退功能

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。