你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、口诀二、用法2.1 定义语法2.2 有哪些功能三、手搓栈push(int value) 入栈方法pop() 出栈方法peek() 获取栈顶方法realloc() 扩容私有方法main测试方法四、双端队列4.1 定义语法4.2 有哪些功能一、口诀栈后进先出LIFO所有增删操作只能在栈顶这一端完成。push压栈存入元素pop弹栈取出并删除栈顶peek 只查看栈顶元素、不移除。生活化理解栈就像一根羽毛球筒最先放进去的羽毛球压在最底下最后放进去的羽毛球最先拿出来。二、用法2.1 定义语法import java.util.Stack; public class StackTest { public static void main(String[] args) { // 创建原生Stack对象 StackInteger stack new Stack(); // 1.入栈 stack.push(10); stack.push(20); stack.push(30); // 2.查看栈顶元素不删除 System.out.println(stack.peek()); // 30 // 3.出栈移除并返回栈顶 System.out.println(stack.pop()); // 30 // 4.判断栈是否为空 System.out.println(stack.empty()); // false // 5.查找元素位置栈顶位置是1 System.out.println(stack.search(10)); // 2 // 循环清空栈 while (!stack.empty()) { System.out.println(stack.pop()); } } }2.2 有哪些功能Stack是 Java 提供的栈容器核心 5 个方法E push(E item)压栈把元素放到栈顶E pop()弹出栈顶元素取出同时删除空栈调用直接抛出 EmptyStackExceptionE peek()获取栈顶元素只查看、不删除元素空栈调用直接抛异常boolean empty()判断栈是否为空空栈返回 trueint search(Object o)从栈顶向下查找元素返回距离栈顶的偏移位置找不到返回-1三、手搓栈package stack; // 基于顺序表的方式实现栈. 暂时不考虑泛型, 只是存储 int 数据 public class MyStack { private int[] array; private int size; public MyStack() { array new int[1000]; size 0; }先看成员变量与构造方法。int[] array是底层用来存放栈元素的数组被private修饰外部代码不能直接操作数组保证栈只能按照后进先出的规则访问数据size是核心变量它既代表当前栈内有效元素的总数量同时下一次入栈元素存放的下标就是size栈顶元素下标永远是size-1size等于0就代表栈是空栈。无参构造方法在创建MyStack对象时自动执行初始化底层数组长度为1000给栈预留初始存储空间刚创建的栈没有任何数据所以size初始赋值为0。push(int value) 入栈方法public void push(int value) { if (size array.length) { realloc(); } array[size] value; size; }push方法负责入栈把元素添加到栈顶。执行逻辑分为三步首先判断当前有效元素数量size是否大于等于底层数组长度如果条件成立说明数组空间已经存满无法继续存放新元素需要调用realloc扩容空间充足之后把传入的数据value存入数组下标size的位置这个位置永远是第一个空闲位置存入完成后执行size自增。size增加后栈顶下标自动更新为size-1。整个入栈操作只在数组尾部操作符合栈只能在栈顶插入元素的规则。pop() 出栈方法public int pop() { if (size 0) { throw new RuntimeException(栈为空); } int ret array[size - 1]; size--; return ret; }pop方法实现出栈功能取出并且删除栈顶元素最后返回取出的元素。首先执行边界判断如果size等于0代表栈里面没有有效元素空栈不能执行出栈操作主动抛出异常避免后续访问array[-1]触发数组越界校验通过后栈顶元素保存在下标size-1先用变量ret保存这个栈顶数值随后执行size--这一步是逻辑删除数组里原本的数据还保留但后续代码只会访问下标小于size的元素下标size的数据会被认定为无效最后把保存好的栈顶元素返回。peek() 获取栈顶方法public int peek() { if (size 0) { throw new RuntimeException(栈为空); } return array[size - 1]; }peek作用是只查看栈顶元素不会删除任何数据和pop最大区别就是不修改size。同样先做空栈判断空栈无法读取栈顶抛出异常校验通过直接返回array[size-1]也就是栈顶的值方法全程不会改动size变量栈内所有元素位置、有效数量完全不变单纯读取数据。realloc() 扩容私有方法private void realloc() { int[] newArray new int[array.length * 2]; for (int i 0; i size; i) { newArray[i] array[i]; } this.array newArray; }realloc被private修饰只能在类内部调用外部无法访问只有push检测到数组存满时才会触发扩容。首先创建一个新数组容量扩大为原来底层数组的2倍接着循环拷贝旧数组里面所有有效元素循环条件i size只复制有效的元素不去拷贝数组空白位置拷贝完成后把成员变量array指向新数组旧数组没有引用指向等待垃圾回收释放内存。扩容完成之后后续入栈操作就会使用容量更大的新数组。main测试方法public static void main(String[] args) { MyStack stack new MyStack(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); } }main方法是程序入口用来验证手写栈功能。先创建栈对象依次压入1、2、3、4此时栈顶是4连续四次调用pop出栈输出顺序4、3、2、1存入顺序和取出顺序相反直观验证栈后进先出LIFO的核心特性。四、双端队列Deque口诀双端队列两端都可以做增加、删除。分为队头、队尾两个端点既可以模拟普通队列先进先出也可以模拟栈后进先出。生活化理解Deque 就像一条双向走廊走廊的头部和尾部都允许人进去也都允许人离开。普通队列只能尾巴进、头部出去栈只能同一头进出双端队列两头都支持插入删除灵活性更强。4.1 定义语法import java.util.Deque; import java.util.LinkedList; public class DequeTest { public static void main (String [] args) { // Deque 属于接口LinkedList 是它的实现类 DequeInteger deque new LinkedList(); // 原生双端操作队头、队尾添加元素 deque.addFirst (10); // 在队头插入 deque.addLast (20); // 在队尾插入 deque.addFirst (5); deque.addLast (25); // 当前内部顺序 5 , 10 , 20 , 25 // 查看两端元素只读取不删除 System.out.println (deque.peekFirst ()); // 获取队头5 System.out.println (deque.peekLast ()); // 获取队尾25 // 两端删除元素 System.out.println (deque.pollFirst ()); // 删除队头返回 5 System.out.println (deque.pollLast ()); // 删除队尾返回 25 // 把 Deque 当做普通队列使用队尾入队队头出队FIFO 先进先出 DequeInteger queue new LinkedList(); queue.offer (1); queue.offer (2); queue.offer (3); System.out.println (queue.poll ()); // 输出 1 // 把 Deque 当做栈使用官方推荐替代 Stack 类 DequeInteger stackSim new LinkedList(); stackSim.push (100); stackSim.push (200); System.out.println (stackSim.peek ()); // 查看栈顶 200 System.out.println (stackSim.pop ()); // 弹出栈顶 200 System.out.println (stackSim.isEmpty ()); // 判断集合是否为空 } }4.2 有哪些功能Deque 是接口日常开发用 LinkedList 作为它的实现。它一共有三套行为 API原生双端操作、模拟普通队列、模拟栈。这里有一个高频坑点Deque 的 push 是向队头存入元素不是队尾很多同学写代码在这里出错。原生双端核心方法addFirst () 在队头添加元素addLast () 在队尾添加元素peekFirst () 获取队头不删除peekLast () 获取队尾不删除pollFirst () 删除并返回队头pollLast () 删除并返回队尾模拟普通队列先进先出offer () 在队尾完成入队poll () 删除队头peek () 获取队头行为和 Queue 接口完全一致。模拟栈后进先出官方替代 Stackpush () 压栈等价 addFirstpop () 弹栈等价 pollFirstpeek () 查看栈顶。千万不要用 addLast 当做压栈栈的压入是加到队头。今天数据结构篇就到这了。诸位共勉