数据结构|深入理解数据结构原理(1)—栈(Stack) 链表|数据结构

目录
一、栈的定义
二、栈的基本操作
三、栈的实际操作

一、栈的定义栈（Stack）是一种只允许在一端进行插入或者删除的操作的线性表。可以理解为一个桶里装进去的一层一层叠加压入进去的东西，栈的性质是进行先入后出的原则，也就是说最先进入栈的元素最后才出来。

文章图片

栈包含：
1、栈顶（Top）：线性表允许进行插入和删除的一端。
2、栈底（Bottom）：是固定的，和栈顶相反，不允许进行插入和删除的一端。
3、空栈：不含有任何的元素的空表。
二、栈的基本操作 1、InitStack（&s）：初始化一个空的栈记为：s。（&：表示引用调用C语言中使用）
2、StakeEmpty（s）：判断栈是否空，空返回 turn，否则返回 false。
3、Push（&s）：进栈，当栈处于未满的状态，将这个元素 x（新进入的元素）作为新栈顶。
4、Pop（&s，&x）：出栈，当栈处于非空状态，则弹出栈顶元素，用 x 返回。
5、GetTop（s，&x）：拿去栈顶元素，当栈处于非空状态，用 x 返回。
6、DestroyStack（&s）：销毁这个栈，释放栈所占的储存空间。

文章图片

java代码：

public class lc003 { public static void main(String[] args) { Stack stack = new Stack(); // 定义一个栈 // push 进栈 stack.push("111"); stack.push("aaa"); stack.push("11aa"); // pop 出栈 String st1 = stack.pop(); String st2 = stack.pop(); String st3 = stack.pop(); // 输出 System.out.println("第一个出来："+st1); System.out.println("第二个出来："+st2); System.out.println("第三个出来："+st3); } }

注意看出栈顺序：

第一个出来：11aa 第二个出来：aaa 第三个出来：111Process finished with exit code 0

三、栈的应用一、栈的简单应用场景 1、子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
2、处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3、表达式的转换[中缀表达式转后缀表达式]与求值（实际解决）。
4、二叉树的遍历。
5、图形的深度优先（depth-first）搜索法
6、递归-汉若塔
7、迷宫求解
二、代码实现栈 1、java中用数组实现
top为栈顶，初始值为-1（如果进入第一元素top++，索引就成了0开始）

class ArrayStack{ private int maxStackSize; // 定义栈的大小 private int[] stack; // 定义数组模拟栈 private int top = -1; // 定义栈顶初始值为-1// 定义构造器初始化栈 public ArrayStack(int maxStackSize){ this.maxStackSize = maxStackSize; stack = new int[maxStackSize]; }// 栈的满 public boolean isFull() { return top == maxStackSize-1; }// 栈的空 public boolean isEmpty() { return top == -1; }// 入栈 public void push(int value) { // 判断栈是否是空状态 if (isFull()) { System.out.printf("栈满了……"); return; } //每当进入一个元素 top往上加一 top++; stack[top] = value; }// 出栈出栈是返回的是栈顶的元素 public int pop(){ // 判断栈是否是空状态 if (isFull()) { // 异常处理 throw new RuntimeException("栈是空的，里面没有数据……") } int value = https://www.it610.com/article/stack[top]; // 返回的元素为栈顶元素 top--; return value; }// 遍历栈 public void listArrayStack(){ if (isEmpty()) { System.out.println("栈是空的，里面没有数据……"); } // 遍历时，需要从栈顶开始显示数据 for (int i = top; i >= 0; i--) { System.out.println("遍历的栈为"+stack[i]); } } }

在java中的操作方法有

序号	方法描述
1	boolean empty() 测试堆栈是否为空。
2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4	Object push(Object element) 把项压入堆栈顶部。
5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。