发布时间：2025-06-24 18:00:14 作者：北方职教升学中心 阅读量：148
用链表实现队列的缺点：
- 空间效率低：链表实现的队列需要额外的指针来连接节点，占用的空间相对较大。消息传递等。栈（Stack）
1.栈的定义
栈是一种特殊的线性表，具有后进先出（Last In First Out, LIFO）的特性。
- 空间效率高：存储元素所需的空间相对较小。弹出顺序
public boolean IsPopOrder (int[] pushV, int[] popV) { //记录出栈顺序的下标 int popIndex = 0; //1.创建一个栈 Stack<Integer> stack = new Stack<>(); //2.遍历 pushV 后依次入栈 for(int i=0;i<pushV.length;i++){ stack.push(pushV[i]); //拿出栈元素的顺序和栈顶进行比较，如果相同则出栈 //如果条件不匹配就等下次入栈再进行判定 //如果条件匹配则继续判断 while(!stack.isEmpty() && popV[popIndex] == stack.peek()){ stack.pop(); popIndex++; } } //当栈为空时，说明前面的元素都匹配成功 if(stack.isEmpty()){ return true; } return false; }5. 最小栈
核心思路是创建两个栈，其中一个存放正常的数值，另一个存放栈1中的最小值，并且栈2的元素个数与栈1保持一致（入栈和出栈）。
- 简单：数组的实现比较简单直观，不需要额外的指针来连接节点。向栈中插入新元素称为入栈（push），从栈中删除元素称为出栈（pop）。
用链表实现队列的优点：
- 动态扩展：链表实现的队列在添加元素时可以动态扩展，不会受到固定大小的限制。
- 插入删除元素快：在链表头部插入或删除元素时只需调整指针，不需要移动其他元素，时间复杂度低。表达式求值、队列有两个主要操作，分别是入队（enqueue）和出队（dequeue）。
用数组实现队列的缺点：
- 大小固定：数组大小在创建时就确定了，无法动态扩展，可能会造成空间浪费或者队列满时无法继续添加元素。栈通常用于需要后进先出顺序的场合，比如函数调用、队列的定义
队列是一种数据结构，其特点是数据按照先进先出（First In First Out, FIFO）的顺序保存和访问。队列常用于需要按照顺序处理数据的场景，例如排队系统、队列的模拟实现
3.1 基于链表实现的单向队列
public class MyQueue { //基于链表实现队列 //1.入队 -> 尾插 2.出队 -> 头删 static class Node{ public String val; public Node next; public Node(String val){ this.val = val; this.next = null; } } //初始化队列 private Node head = null; private Node tail = null; //入队 public void offer(String val){ //新的节点 Node newNode = new Node(val); //链表为空 if(head == null){ head = newNode; tail = newNode; return; } //链表非空。 - 灵活性高：适应需求变化，可以灵活地添加或删除元素。
- 访问速度慢：链表中的元素在内存中是分散存储的，对于随机访问元素速度较慢。
栈的本质就是一个 顺序表/链表 ，但是在 顺序表/链表 的基础上做出了一定限制。回溯算法等。队列的使用
2.1 单向队列
在 Java 中，Queue 是个接口，底层是通过链表来实现的，接口是不能被实例化的，接口只能被类实现，然后通过类来实例化对象。
//创建一个单向队列//一头进，另一头出Queue queue = new LinkedList<>();虽然不能 new ArrayList 作为 Queue 的实现，但是 Queue 也是可以基于数组实现
//基于数组实现的双端队列//两头都可以进、栈可以理解为一个只能在一端进行插入和删除操作的有序集合，这一端被称为栈顶。2.栈的使用
在 Java 标准库中已经实现了现成的栈
public class Test1 { public static void main(String[] args) { Stack<String> stack = new Stack<>(); //入栈 stack.push("aaa"); stack.push("bbb"); stack.push("ccc"); //出栈(将栈顶元素出栈并返回) String s = stack.pop(); System.out.println(s); //获取栈顶元素 String top = stack.peek(); //获取栈中有效元素个数 int size = stack.size(); //检查栈是否为空 Boolean empty = stack.empty(); }}3.栈的模拟实现
//可以基于顺序表(数组)实现，也可以基于链表来实现//基于数组更简单public class MyStack { private String[] arr; private int size; //默认构造方法 public MyStack(){ arr = new String[1000]; size = 0; } public MyStack(int capacity){ arr = new String[capacity]; size = 0; } //入栈 public void push(String elem){ //如果元素超出个数进行扩容 if(size == arr.length){ resize(); } //尾插 arr[size] = elem; size++; } private void resize(){ //1.创建更长的数组 String[] newArr = new String[arr.length * 2]; //2.把原数组的元素赋值到新数组中 for(int i = 0;i < arr.length ; i++){ newArr[i] = arr[i]; } //把新数组赋值给原数组 arr = newArr; } //出栈 public String pop(){ //如果是空栈则抛出异常 if(size == 0){ throw new RuntimeException("Stack is empty"); } //取出栈顶元素 String elem = arr[size-1]; //元素个数-1 size--; //返回 return elem; } //获取栈顶元素 public String peek(){ //如果是空栈则抛出异常 if(size == 0){ throw new RuntimeException("Stack is empty"); } String elem = arr[size-1]; return elem; }}4.栈的应用场景
4.1 将递归转化为循环
例：逆序打印链表
//使用递归完成对链表的逆序打印 public static void reversePrint(Node head){ if(head == null){ return; } reversePrint(head.next); System.out.println(head.val); }public static void reversePrint(Node head){ //使用栈的写法 if(head == null){ return; } //创建栈，把链表元素都进栈 Stack<Node> stack = new Stack<>(); for (Node cur = head;cur!=null;cur=cur.next){ stack.push(cur); } //依次出栈 while(!stack.isEmpty()){ System.out.println(stack.pop().val+" "); } }虽然代码量会比使用递归上来得多，但是更容易让人理解
4.2 有效的括号
这道题使用栈来完成，思路则有点像消消乐，只要括号是有效的，最后的栈一定为空
public class StackProblem { //有效的括号 public boolean isValid(String s){ //创建一个栈 Stack<Character> stack = new Stack<>(); //针对每个字符串进行遍历，取出每个字符 for(int i = 0 ; i < s.length();i++){ //取出每个字符 char c =s.charAt(i); //如果是左括号就入栈 if(c == '(' || c == '[' || c == '{') { stack.push(c); continue; } if(c == ')' || c == ']' || c == '}'){ if(stack.isEmpty()){ //如果读到了右括号并且栈为空，最后一定不是有效的 return false; } char top = stack.pop(); if((top == '[' && c == ']' ) || (top == '(' && c == ')' )|| (top == '{' && c == '}')){ //括号匹配则接着往下走 continue; } //匹配失败直接返回 return false; } } //整个循环结束，再来检查栈是否为空，如果为空，说明所有括号匹配成功 if(stack.isEmpty()){ return true; } return false; }}4.3 逆波兰表达式
public int evalRPN(String[] tokens) { //1.准备一个栈，用来放操作数 Stack<Integer> stack = new Stack<>(); //2.遍历 tokens,取出每个元素 for(String token : tokens){ //3.判断 tokens 是不是数字 if(isNumber(token)){ stack.push(Integer.parseInt(token)); continue; } //4.如果 token 是运算符 //出栈两个元素，先出栈的是第二个操作数，后出栈的是第一个操作数 int num2 = stack.pop(); int num1 = stack.pop(); //5.判定当前运算符是哪个，进行运算完重写入栈 if(token.equals("+")){ stack.push(num1+num2); }else if(token.equals("-")){ stack.push(num1-num2); }else if(token.equals("*")){ stack.push(num1*num2); }else if(token.equals("/")){ stack.push(num1/num2); } } //整个表达式的结果就是栈里唯一的一个元素 return stack.pop(); } private static boolean isNumber(String token){ //如果 token 是运算符就返回 false,否则返回 true if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")){ return false; } return true; }4.4 栈的压入、
- 插入删除元素慢：在队列头部插入或者删除元素时，需要移动其他元素，时间复杂度较高。
当找栈中的最小值时可以从第二个栈中提取，可以达到O（1）的时间复杂度
class MinStack { private Stack<Integer> stack1 = new Stack<>(); private Stack<Integer> stack2 = new Stack<>(); public MinStack() { } public void push(int val) { //stack1 正常入栈 stack1.push(val); //stack2 需要比较 val 和 stack1栈顶元素的大小，把小的元素入栈 //如果 stack2 为空，直接入栈 if(stack2.isEmpty()){ stack2.push(val); }else{ stack2.push(val<stack2.peek()?val:stack2.peek()); } } public void pop() { stack1.pop(); stack2.pop(); } public int top() { return stack1.peek(); } public int getMin() { return stack2.pop(); }}二、入队操作将数据添加到队列的末尾，而出队操作则删除并返回队列的第一个数据。进行尾插 tail.next = newNode; //尾插之后，更新 tail 的指向 tail = newNode; } //出队列 public String poll(){ //头删 if(head == null){ return null; } //保存头部节点的值，把这个节点删掉后返回这个节点的值 String val = head.val; head = head.next; //如果链表的节点数超过一个，删掉一个后不影响 tail 的指向 //如果只有一个节点，删掉元素后 tail 应该指向 null if(head == null){ tail = null; } return val; } //取队首元素 public String peek(){ if(head==null){ return null; } return head.val; } //判断队列是否为空 public boolean isEmpty(){ return head == null; } //计算队列有效元素个数 public int size(){ int size = 0; for(Node node = head;node != null ; node = node.next){ size++; } return size; }}
3.2 基于数组实现的循环队列
public class MyQueueByArray { private String[] arr = null; //队首 private int head = 0; //队尾 private int tail = 0; //队列元素个数 private int size = 0; public MyQueueByArray(){ arr = new String[1000]; } public MyQueueByArray(int capacity){ arr = new String[capacity]; } //入队 public void offer(String val){ //如果队列满了，直接返回 if(size == arr.length){ //也可以抛出异常，也可以进行扩容.... return; } //把新的元素放到 tail 的位置 arr[tail] = val; //更新 tail 的指向 tail++; //当到达数组末尾时，指向重新回到开头(循环) if(tail == arr.length){ tail = 0; } //更新队列元素个数 size++; } //出队 public String poll(){ //如果队列为空，直接返回 null if(size == 0){ return null; } //取出队首元素，保存起来，以便接下来返回 String val = arr[head]; //队列使用数组的最大缺点就是当有元素出队时，其他的元素也需要更换位置 //但是还可以通过移动 head 的指向来优化这个问题 head++; if(head == arr.length){ head = 0; } //更新元素个数 size--; return val; } //查看队首元素 public String peek(){ if(size==0){ return null; } return arr[head]; } public boolean isEmpty(){ if(size==0){ return true; } return false; } public int size(){ return size; }}4、不同实现队列的优缺点
用数组实现队列的优点：
- 速度快：数组在内存中是连续存储的，对于随机访问元素速度很快。队列（Queue）
一、
2、出Queue<Integer> queue1 = new ArrayDeque<>();
2.2 双端队列(Deque)
Deque 是一个接口，使用时必须创建 LinkedList 的对象
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 Deque<Integer> queue = new LinkedList<>();//双端队列的链性实现3、
- 不灵活：无法灵活地添加或删除元素，不够适应需求变化。
- 实现复杂：相比数组，链表的实现可能会更复杂一些，需要考虑节点的指针连接等操作
1、
- 速度快：数组在内存中是连续存储的，对于随机访问元素速度很快。
