Java数据结构（五）——栈和队列

文章目录

  • 栈和队列
    • 栈
      • 基本概念
      • 栈的模拟实现
      • 集合框架中的栈
        • 栈的创建
        • 栈的方法
        • 栈的遍历
      • 栈的应用及相关练习
        • 括号匹配
        • 逆波兰表达式求值
        • 出栈入栈次序匹配
        • 最小栈
      • 几个含"栈"概念的区分
    • 队列
      • 基本概念
      • 队列的模拟实现
      • 循环队列
      • 双端队列
      • 集合框架中的队列
        • 队列的创建
        • 队列的方法
        • 队列的遍历
      • 队列的应用及相关练习
        • 用队列实现栈
        • 用栈实现队列

栈和队列

栈

基本概念

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，即 “先进后出”

栈顶，即进行数据插入和删除操作的一端；栈底，即与栈顶相对的另一端。

栈的插入操作叫做压栈/进栈/入栈；栈的删除操作叫做出栈/退栈/弹出。栈的插入和删除操作都在栈顶一端。

【数据结构入门】栈（Stack）的实现（定义、销毁、入栈、出栈等） | 图解数据结构，超详细哦~_销毁栈-CSDN博客

了解了基本的概念后，我们尝试做一道小题，体会栈的先进后出的特性：

进栈序列为1，2，3，4 ，并且进栈的过程中可以出栈，则不可能的出栈序列是（）

A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1

想象现在有一个栈，最好还是画图，对于A：1进1出2进3进4进4出3出2出，满足；对于B：1进2进2出3进3出4进4出1出，满足；对于C：1进2进3进3出，此时栈顶元素为2，只能先出2才能出1，所以该序列不可能为出栈序列，不满足；对于D：1进2进3进3出4进4出2出1出，满足

所以，答案为：C

栈的模拟实现

了解了栈以及栈的特性，思考，怎么实现一个栈，使其满足栈的特性？

其实，使用数组和链表都可以，我们需要实现的方法包括：

  • 入栈操作
  • 出栈操作
  • 获取栈顶元素
  • 获取栈中的有效元素个数
  • 判断栈是否为空

接下来我们就分别使用数组和链表实现一个栈：

【数组实现栈】

实现一个类，类中定义一个数组成员变量，为了满足栈的特性，数组只允许尾插和尾删：

大体框架如下：

public class MyStackByArray {public int[] elem;//栈public int capacity;//栈的容量public int usedSize;//栈的有效元素个数public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入栈public void push(int data) {}//出栈并返回出栈元素public int pop() {}//获取栈顶元素public int peek() {}//获取栈中的有效元素public int size() {}//检测栈是否为空public boolean empty() {}
}

public int size()

返回成员变量usedSize即可

    //获取栈中的有效元素public int size() {return this.usedSize;}

public boolean empty()

    //检测栈是否为空public boolean empty() {return this.usedSize == 0;}

public void push(int data)

由于数组下标从0开始，所以成员变量usedSize其实就是下一次入栈的下标位置。入栈前，我们要判断栈是否满，满了要扩容，之后进行入栈即可：

    //入栈public void push(int data) {//栈满则扩容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入栈this.elem[this.usedSize] = data;this.usedSize++;}

public int pop()

出栈前，我们判断栈是否为空，当为空时，我们选择抛出一个自定义异常：StackIsException

public class StackIsEmptyException extends RuntimeException {public StackIsEmptyException(String message) {super(message);}
}

如果不为空，执行出栈，注意，出栈直接让usedSize--即可，不需要特意将栈顶元素置成0，因为当下次入栈时会覆盖掉此元素

    //出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}//出栈this.usedSize--;return this.elem[this.usedSize];}

public int peek()

获取栈顶元素，判断为空？为空抛出异常，否则返回

    //获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return this.elem[this.usedSize - 1];}

完整代码：

public class MyStackByArray {public int[] elem;public int capacity;public int usedSize;public MyStackByArray() {this.elem = new int[10];this.capacity = 10;}//入栈public void push(int data) {//栈满则扩容if(this.capacity == usedSize) {this.elem = Arrays.copyOf(elem, this.capacity * 2);this.capacity *= 2;}//入栈this.elem[this.usedSize] = data;this.usedSize++;}//出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}//出栈this.usedSize--;return this.elem[this.usedSize];}//获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return this.elem[this.usedSize - 1];}//获取栈中的有效元素public int size() {return this.usedSize;}//检测栈是否为空public boolean empty() {return this.usedSize == 0;}
}

【链表实现栈】

对于出栈，我们选择头删，因为尾删得遍历链表找到倒数第二个结点，效率较低

对于入栈，我们选择头插，因为出栈选择的是头删，要满足先进后出，必须选择头插。

代码比较简单，我们直接给出完整实现：

public class MyStackByLinkedList {//链表结点类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//链表第一个结点的引用public ListNode head;//入栈public void push(int data) {ListNode newNode = new ListNode(data);if(head == null) {head = newNode;return;}newNode.next = head;head = newNode;}//出栈并返回出栈元素public int pop() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}int ret = head.val;head = head.next;return ret;}//获取栈顶元素public int peek() {if(empty()) {throw new StackIsEmptyException("The Stack Is Empty!: 栈为空!");}return head.val;}//获取栈中的有效元素public int size() {int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}//检测栈是否为空public boolean empty() {return head == null;}
}

集合框架中的栈

集合框架中，顺序表对应ArrayList，链表对应LinkedList，那么栈对应什么呢？

栈的创建

栈对应三个：Stack、LinkedList、ArrayDeque，即这三个类都可以作为栈

  • Stack类就是原生的栈类。只有无参构造方法
  • LinkedList实现了Deque接口，Deque接口是双端队列接口，其中包含了操作栈的方法，所以LinkedList可作为链栈类。构造方法有两个：无参构造和利用其他容器的构造
  • ArrayList也实现了Deque接口，实现了操作栈的方法，是基于数组的数据结构。构造方法有三个：无参构造、指定初始容量的构造、利用其他容器的构造
    在这里插入图片描述
    public static void main(String[] args) {Stack<Integer> stack0 = new Stack<>();//StackLinkedList<Integer> stack1 = new LinkedList<>();//LinkedListArrayDeque<Integer> stack2 = new ArrayDeque<>();//ArrayDeque}
栈的方法
方法功能
E push(E e)将e入栈，并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中的有效元素的个数
boolean empty()检测栈是否为空
  • 注意：如果使用LinkedList或ArrayDeque实现栈，那么判空的方法为boolean isEmpty()，而不是boolean empty()
栈的遍历

关于栈的遍历，有三种方法，分别是迭代器、for-each和方法遍历：

  • 对于Stack、LinkedList和ArrayDeque来说，利用方法遍历的结果是一致的，都是按照"先进后出’'的原则，并且这也是最常用的方法：
    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");while(!s1.empty()) {System.out.print(s1.pop() + " ");}System.out.println();System.out.println("=====LinkedList=====");while(!s2.isEmpty()) {System.out.print(s2.pop() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");while(!s3.isEmpty()) {System.out.print(s3.pop() + " ");}System.out.println();}

在这里插入图片描述

  • Stack使用迭代器打印的顺序是从栈底到栈顶，并不是出栈顺序，这是因为Stack是基于数组实现的，每次入栈都是在尾部；而LinkedList和ArrayDeque是按照出栈顺序打印的，这是因为它们入栈都是在头部/顶部进行的（头插）
    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");Iterator<Integer> it1 = s1.iterator();while(it1.hasNext()) {System.out.print(it1.next() + " ");}System.out.println();System.out.println("=====LinkedList=====");Iterator<Integer> it2 = s2.iterator();while(it2.hasNext()) {System.out.print(it2.next() + " ");}System.out.println();System.out.println("=====ArrayDeque=====");Iterator<Integer> it3 = s3.iterator();while(it3.hasNext()) {System.out.print(it3.next() + " ");}System.out.println();}

在这里插入图片描述

  • for-each遍历的结果与迭代器遍历的结果一致
    public static void main(String[] args) {Stack<Integer> s1 = new Stack<>();LinkedList<Integer> s2 = new LinkedList<>();ArrayDeque<Integer> s3 = new ArrayDeque<>();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println("=====Stack=====");for(Integer x : s1) {System.out.print(x + " ");}System.out.println();System.out.println("=====LinkedList=====");for(Integer x : s2) {System.out.print(x + " ");}System.out.println();System.out.println("=====ArrayDeque=====");for(Integer x : s3) {System.out.print(x + " ");}System.out.println();}

在这里插入图片描述

栈的应用及相关练习

栈的"先进后出’'的特性，使得栈的应用场景十分广泛，比如，将序列逆序、递归转化为非递归等等。

下面是几道关于栈的经典题目：

括号匹配

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
class Solution {public boolean isValid(String s) {//补充代码}
}

【思路】

遍历字符串的每个字符，如果是左括号就入栈，如果是右括号，就从栈中弹出一个元素，看左右括号是否匹配。

最终结果不匹配的原因可能是：

  • 只有左括号 或 只有右括号 或 左右括号数量不一致
  • 左右括号类型不匹配
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();int i = 0;for(i = 0; i < s.length(); i++) {char ch = s.charAt(i);if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {if(stack.empty()) {return false;}else {char top = stack.pop();switch(top) {case '(':if(ch != ')') {return false;}break;case '[':if(ch != ']') {return false;}break;case '{':if(ch != '}') {return false;}break;}}}}if(!stack.empty()) {return false;}return true;}
}

原题链接：20. 有效的括号 - 力扣（LeetCode）

逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

class Solution {public int evalRPN(String[] tokens) {//补充代码}
}

【思路】

逆波兰表达式，也叫后缀表达式，即将运算符写在操作数的后面。（我们平时习惯使用中缀表达式）举个简单的例子：

对于中缀表达式：(1 + 2) * 3，转化为后缀表达式：1 2 + 3 *

对于上面的后缀表达式的计算过程为： 寻找运算符，即找到了+，然后将+前的两个操作数执行+运算，得到3，此时表达式化简为3 3 *，继续向后找到*运算符，将前面两个操作数执行*运算，得到9，此时9就是表达式的结果。

了解了后缀表达式的求解，我们就可以解决这道题目：

遍历字符串数组，如果是数字就入栈，如果是运算符就不入栈并从栈中弹出两个元素，执行运算，将结果入栈，以此循环，最终栈中会剩余一个元素，这个元素就是表达式的结果

注意的问题：

  • 题目给的是字符串数组，进行运算时，要将字符串类型转换为int类型
  • 弹出时，先弹出的是右操作数，后弹出的是左操作数，注意两者的顺序，以免计算出错
class Solution {public int evalRPN(String[] tokens) {Stack<String> stack = new Stack<>();for(int i = 0; i < tokens.length; i++) {String s = tokens[i];if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {int op2 = Integer.valueOf(stack.pop());int op1 = Integer.valueOf(stack.pop());switch(s) {case "+":stack.push(String.valueOf(op1 + op2));break;case "-":stack.push(String.valueOf(op1 - op2));break;case "*":stack.push(String.valueOf(op1 * op2));break;case "/":stack.push(String.valueOf(op1 / op2));break;} }else {stack.push(s);}}return Integer.valueOf(stack.pop());}
}

原题链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

出栈入栈次序匹配

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000
  2. -1000<=pushV[i]<=1000
  3. pushV 的所有数字均不相同
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {//补充代码}
}

【思路】

遍历入栈序列，每次将该次遍历到的元素入栈，然后判断当前的栈顶元素是否与出栈序列的元素相等，即是否可以出栈，如果可以，就出栈（出栈一次后，遍历出栈序列的指针也要后移），直到不能出栈了，继续遍历入栈序列，遍历完成后，如果栈为空说明匹配。

    public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j < popV.length && !stack.isEmpty() && stack.peek() == popV[j]) {stack.pop();j++;}}return stack.isEmpty();}

注意：

  • while循环判断是否可以出栈前，要判断栈是否为空，否则可能会抛出栈空异常
  • j < popV.length在本题目中可以不写，因为题目保证两个序列长度相等，如果测试用例给出的长度不一定相等，那就需要加上

原题链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {public MinStack() {}public void push(int val) {}public void pop() {}public int top() {}public int getMin() {}
}

【思路】

维护两个栈，一个是普通的栈，一个是存放最小值的栈，它的栈顶元素就是当前状态下的普通栈中的最小值，具体操作：

当入栈时，普通的栈直接入栈，如果最小值栈为空或者最小值栈的栈顶元素>=入栈元素，那么最小值栈也入栈该元素

当出栈时，普通的栈直接出栈，同时判断普通栈的出栈元素是否与当前最小值栈的栈顶元素一致，如果一致，最小值栈也弹出元素一次

当想要获取当前栈中的最小元素时，直接返回最小值栈的栈顶元素

如此，维护了两个栈。

class MinStack {public Stack<Integer> stack;public Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty() || minStack.peek() >= val) {minStack.push(val);}}public void pop() {if(stack.empty()) {return;}if(stack.pop().equals(minStack.peek())) {minStack.pop();}}public int top() {if(stack.empty()) {return -1;}return stack.peek();}public int getMin() {if(minStack.empty()) {return -1;}return minStack.peek();}
}

注意：

  • 最小值栈入栈的条件：当入栈元素与当前最小值栈的栈顶元素相等时，也要入栈，相当于有多个相等的最小值。

  • 这一条是笔者在解决该问题时出现的问题，如果我将pop()方法改成如下代码，是否可行？

        public void pop() {if(stack.empty()) {return;}if(stack.pop() == minStack.peek()) {minStack.pop();}}

    不可行！

    因为，Stack类中的pop()和peek()方法返回的是类型实参的类型，即实现泛型时<>里传入的类型，是引用类型，如果像上面这样书写，本质上是对两个引用类型使用==比较，引用类型==比较的是地址，而不是值，所以不可行！

    但是，对于该题目，泛型实现时传入的是Integer类型，通过==比较时，可能会出现true的情况，这是因为Integer有缓存机制：

    缓存机制：

    • Java对于Integer类型的对象在值位于-128到127之间时有特殊的缓存处理。JVM会为这个范围的每个数字缓存一个Integer对象。

      例如，Integer a = 127; Integer b = 127; System.out.println(a == b); // 输出 true，因为a和b都指向同一个缓存的对象。

    • 对于超出该范围的数字，即使值相同，也会创建不同的对象实例，所以==会比较返回false。

      如 Integer c = 128; Integer d = 128; System.out.println(c == d); // 输出 false。

    我们无法保证题目给出的值在缓存区间内，所以不可以像上面那样书写，我们可以使用equals方法判断它们的值是否相等（就如答案所示），或者这么写：

        public void pop() {if(stack.empty()) {return;}int tmp = stack.pop();if(tmp == minStack.peek()) {minStack.pop();}}

    上面这个代码将Stack类中的pop方法的返回值用int类型的一个变量接收，返回值是Integer类型，所以会自动拆箱为int类型，再用int类型与peek方法返回值的Integer类型使用==比较，而当使用==比较Java中的Integer类型与int类型时，会将Integer类型拆箱为int类型，所以本质上是两个int类型的比较，可行！

    原题链接：155. 最小栈 - 力扣（LeetCode）

几个含"栈"概念的区分

区分栈、虚拟机栈和栈帧：

栈、虚拟机栈和栈帧是Java虚拟机（JVM）中的三个相关但不同的概念，它们在定义功能、数据结构以及生命周期等方面存在明显的区别：

  1. 定义功能
    • Java栈：通常指的是一种后进先出（LIFO）的数据结构，用于存储程序执行过程中的临时数据。例如，方法的局部变量和返回地址等。
    • 虚拟机栈：特指JVM为每个线程分配的独立内存区域，用于存放栈帧，即方法调用的信息。它与线程同时创建和销毁，主要支持方法的调用和执行。
    • 栈帧：是虚拟机栈中的一个元素，对应于正在执行的每个方法。每个方法执行时都会创建一个对应的栈帧，包含局部变量表、操作数栈、动态链接以及方法出口等信息。
  2. 数据结构
    • Java栈：作为一种数据结构，其实现可以基于数组或链表，主要用于算法中数据的临时存储。
    • 虚拟机栈：作为JVM内部的一个运行时数据区，其内部由多个栈帧组成，每个栈帧对应一个方法调用的相关信息。
    • 栈帧：具有固定的数据结构，包括局部变量表、操作数栈等，这些组成部分在编译期间就已经确定大小。
  3. 生命周期
    • Java栈：根据程序逻辑进行入栈和出栈操作，使用完毕后即可销毁。
    • 虚拟机栈：与线程绑定，线程结束时对应的虚拟机栈也会被销毁。
    • 栈帧：在方法调用时创建，方法执行完毕或异常终止时销毁。
  4. 存储内容
    • Java栈：可用于存储任何类型的对象，如基本类型、引用类型等。
    • 虚拟机栈：专门用于存储方法调用的相关信息，如局部变量、操作数等。
    • 栈帧：具体存储了方法的局部变量表、操作数栈、动态链接以及方法的返回地址等信息。
  5. 应用场景
    • Java栈：广泛应用于各类算法中，如深度优先搜索、递归计算等。
    • 虚拟机栈：在JVM的执行引擎中应用，用于支持方法的调用和执行。
    • 栈帧：直接关联到每个方法的具体执行过程，记录了方法执行所需的全部信息。

总的来说，Java栈、虚拟机栈和栈帧各自承担着不同的功能和角色。Java栈是一个通用的数据结构，而虚拟机栈和栈帧则是JVM内部专门设计的机制，用于支持方法的调用和执行。这三者共同协作，确保了Java程序能够高效、安全地运行。

队列

基本概念

队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，其特点概括为 “先进先出”，就像现实生活中的排队一样，在最早排队的总是先出队。

队头：进行删除操作的一端；队尾：进行插入操作的一端

在这里插入图片描述

注意区分栈和队列。

队列的模拟实现

了解了队列的基本概念后，思考怎样实现一个队列？使用数组还是链表？

假设使用数组，通常我们会定义一个队头变量和队尾变量，以方便入队和出队操作，入队操作使用尾插，那么出队操作就必须是头删。当队列不为空，每次出队，队头变量要不断地向后移动，最终会导致数组的前半部分空间都被浪费了，且队列容量越来越少，所以简单的数组实现队列是不方便的，如果要使用数组，那么最好实现成循环队列（后面会讲）。

一般来说，队列使用链表实现，问题是入队和出队操作怎么实现？对于单链表，定义两个引用，分别指向队头和队尾，如果出队采用尾删，那么我们就得遍历链表找到倒数第二个结点，让它的next为null，效率较低，所以出队采用头删，相应地，入队采用尾插，从而达到"先进先出"的特点，并且保证了入队和出队的时间复杂度都是O(1)。

但如果是双向链表，那么就不需要考虑上面的问题，入队出队操作都是O(1)，我们这里采用双向链表模拟实现一个队列：

实现如下（双向链表的头删、尾插操作，较为简单）：

public class MyQueue {//链表结点类static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//队头引用public ListNode tail;//队尾引用private int size;//队列有效元素个数//入队public void offer(int data) {ListNode newNode = new ListNode(data);if(tail == null) {head = newNode;tail = newNode;size++;return;}tail.next = newNode;newNode.prev = tail;tail = newNode;size++;}//出队并返回出队元素public int poll() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}int ret = head.val;if(head == tail) {head = null;tail = null;}else {head.next.prev = null;head = head.next;}size--;return ret;}//获取队头元素public int peek() {if(this.head == null) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}return this.head.val;}//获取队列中的有效元素个数public int size() {return this.size;}//判断队列是否为空public boolean isEmpty() {return this.head == null;}}

循环队列

前面提到，单纯的数组实现队列会导致空间的浪费以及队列大小的缩减，这时候引出了循环队列的概念：

循环队列是一种优化的队列数据结构，旨在解决顺序队列中存在的“假溢出”问题。

循环队列采用了头尾相接的环状存储结构，通过将顺序队列的数组视为一个循环结构，使得当存储空间的最后一个位置已被使用时，新元素可以继续从第一个位置开始存储，形成一个逻辑上的环。这种设计极大地提高了存储空间的利用率。

接下来我们就讲解一下循环队列的思想，关于循环队列，我们要解决两大问题：

当存储空间的最后一个位置已被使用时，新元素怎样继续从第一个位置开始存储?

怎样区分循环队列的 空 和 满 两个状态？

【问题一】

在实现循环队列时，我们仍然会定义两个"指针"：rear(指向队尾，这个队尾实际上是下一次入队的位置，而不是指队尾元素)、front(指向队头，即队头元素)，于是就可能会出现下图的情况：

在这里插入图片描述

此时，存储空间的最后一个位置已被使用，rear指向了最后位置后面的一个位置（此位置不能入新元素了），而此时由于进行过出队操作，数组的前面还有剩余空间可以使用，我们就得想办法让空闲空间被利用到，即让rear重新回到数组开始的位置，怎么办？

传统的rear += 1肯定不行，我们采用这样的语句 rear = (rear + 1) % len，len就是数组长度。对于上面的情况，我们代入公式：

rear = (8 + 1) % 9，得到0，此时rear就重新回到了数组0下标位置，这个公式在任何位置都是可以的。有了这个公式，front和rear就可以循环起来了。

【问题二】

怎样区分循环队列的 空 和 满 两个状态？ 我们看如下图表示的情况，为了突出循环，我们将数组在视觉上改成环：
在这里插入图片描述

在这里插入图片描述

图1表示队列为空，图2表示队列已满，但是两种情况下都是rear == front，怎么区分呢？

我们有三种解决方案：

  • 定义成员变量size表示队列中的有效元素个数：当size和数组长度相等时，表示满；为0时表示空
  • 定义一个boolean类型的标记：最开始为false，当入队新元素后变为true，当出队元素后rear == front，说明最后一个元素出队了，将其置为false。这样，当rear == front && 标记为false时，表示空，当rear == front && 标记为true时，表示满
  • 浪费一个空间：即留出一个空间不放元素，当rear == front时，表示空；当(rear + 1) % len == front(下一个位置是队头)时，表示满

解决完上面的两个问题，我们以第二种解决方案动手实现一下，（分析与注意事项在代码后面）：

public class CircularQueue {public int[] elem;//数组private boolean flag;//标记public int rear;//队尾指针public int front;//队头指针public CircularQueue() {elem = new int[10];}public void offer(int data) {if(rear == front && flag == true) {System.out.println("队列已满");return;}elem[rear] = data;rear = (rear + 1) % elem.length;flag = true;}public int poll() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}int ret = elem[front];front = (front + 1) % elem.length;if(rear == front) {flag = false;}return ret;}public int peek() {if(isEmpty()) {throw new QueueIsEmptyException("The Queue Is Empty!: 队列为空!");}return elem[front];}public int size() {if(rear > front) {return rear - front;}else if(rear < front) {return rear + (elem.length - front);}else {return flag == true ? elem.length : 0;}}public boolean isEmpty() {return rear == front && flag == false;}
}
  • rear实际上指向下一次入队的位置，而不是指向队尾元素；而front是指向队头元素
  • offer方法最后一定要将标记置为true
  • poll方法内部在front因出队改变后，要检查是否要将标记置为false，即检查该次出队的是否是队列中最后一个元素
  • size方法考虑的就比较多了，循环队列的思想导致rear和front的相对位置会发生变化，如代码：分为rear > front、rear < front以及rear == front，特别注意第三种相等的情况，可能是满了，也可能是空，这要根据标记判断。

不妨做个练习，尝试使用问题二中的其他方案设计循环队列：

class MyCircularQueue {public MyCircularQueue(int k) {}public boolean enQueue(int value) {}public boolean deQueue() {}public int Front() {}public int Rear() {}public boolean isEmpty() {}public boolean isFull() {}
}

给出以浪费一个空间方案完成该题目的代码：

class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k + 1];}public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear + 1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}if(rear == 0) {return elem[elem.length - 1];}return elem[rear - 1];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear + 1) % elem.length == front;}
}
  • 既然要浪费一个空间，那么我们在构造方法初始化数组时要创建一个比参数大1个空间的数组，保证一部分测试用例能够顺利通过。
  • Rear方法要求返回队尾元素，由于我们的rear是队尾元素之后的一个位置，所以我们必须向前一个位置找，这里就有一个特殊情况，当rear == 0，此时不能减一，前一个应该是数组最后一个下标的位置，所以有如上代码。

原题链接：622. 设计循环队列 - 力扣（LeetCode）

双端队列

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

双端队列 - youngliu91 - 博客园

在集合框架中，双端队列对应Deque接口，在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

实现双端队列可以用LinkedList（链式实现）或ArrayDeque（线性实现）：

    public static void main(String[] args) {Deque<Integer> deque1 = new LinkedList<>();//链式实现Deque<Integer> deque2 = new ArrayDeque<>();//线性实现}

所以，到这里我们发现：

LinkedList可以作为链表、栈、(普通)队列、双端队列

ArrayList可以作为栈、(普通)队列、双端队列

集合框架中的队列

集合框架中的队列是Queue接口，Deque接口继承自它，LinkedList和ArrayDeque都实现了该接口。

在这里插入图片描述

队列的创建

我们可以通过ArrayDeque或者LinkedList创建一个队列：

    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();//链式队列Queue<Integer> queue2 = new ArrayDeque<>();//线性队列}
队列的方法
方法功能
boolean offer(E e)入队列
E poll()出队列
E peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空
队列的遍历
    public static void main(String[] args) {Queue<Integer> queue1 = new LinkedList<>();queue1.offer(1);queue1.offer(2);queue1.offer(3);queue1.offer(4);queue1.offer(5);System.out.println("=====for-each=====");for(Integer x : queue1) {System.out.print(x + " ");}System.out.println();System.out.println("=====迭代器=====");Iterator<Integer> it = queue1.iterator();while(it.hasNext()) {System.out.print(it.next() + " ");}System.out.println();System.out.println("=====while=====");while(!queue1.isEmpty()) {System.out.print(queue1.poll() + " ");}System.out.println();}

在这里插入图片描述

队列的应用及相关练习

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

class MyStack {public MyStack() {}public void push(int x) {}public int pop() {}public int top() {}public boolean empty() {}
}

【思路】

以画图+文字介绍：

在这里插入图片描述

现在我们要模拟出栈，如图向栈中依次加入21、56、23、11，此时栈顶元素应为11，出栈时要弹出11。

我们只有两个队列，所以让不为空的队列中的元素出队，直到只剩1个元素，这个元素就是"栈顶"元素，将它"弹出"；此时如果再次入队

在这里插入图片描述

此时，如果再添加新元素，继续向非空队列添加，而它就是新的"栈顶元素"，如果接着"出栈"，就重复上面的工作：将元素出队到空队列，直到只剩一个元素，弹出。

所以有：

入栈： 向非空队列中添加元素，初始都为空时随意选择

出栈： 非空队列将元素出到空队列中，直到只剩下一个元素，这个元素就是栈顶元素，弹出

class MyStack {public Queue<Integer> q1;public Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size - 1; i++) {q2.offer(q1.poll());}return q1.poll();}else{int size = q2.size();for(int i = 0; i < size - 1; i++) {q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q1.poll();q2.offer(ret);}return ret;}else{int size = q2.size();int ret = 0;for(int i = 0; i < size; i++) {ret = q2.poll();q1.offer(ret);}return ret;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}

原题链接：225. 用队列实现栈 - 力扣（LeetCode）

用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

class MyQueue {public MyQueue() {}public void push(int x) {}public int pop() {}public int peek() {}public boolean empty() {}
}

【思路】

在这里插入图片描述

如上图，如果不再添加新元素，按照图解思路出队，得到序列：[10, 44, 31, 12, 101, 88, 36]，满足队列的先进先出。

class MyQueue {public Stack<Integer> sIn;public Stack<Integer> sOut;public MyQueue() {sIn = new Stack<>();sOut = new Stack<>();}public void push(int x) {sIn.push(x);}public int pop() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.pop();}public int peek() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.peek();}public boolean empty() {return sIn.empty() && sOut.empty();}
}

原题链接：232. 用栈实现队列 - 力扣（LeetCode）

完

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/388899.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

数据结构（邓俊辉）学习笔记】词典 01—— 散列

数据结构（邓俊辉）学习笔记】词典 01—— 散列

文章目录 1. 从服务到电话2. 循值访问3. 数组4. 原理5. 散列6. 冲突 1. 从服务到电话 现在进入新的一章词典。将学习实现词典 adt 的重要技术&#xff0c;也就是散列。我们将看到散列实际上并不是一种简单的技术&#xff0c;从某种意义上讲&#xff0c;它甚至是一种思想&#x…
阅读更多...
记录一次环境的安装

记录一次环境的安装

目录 新添加的代码 代码解释 为啥ubuntu用debian软件源 为啥修改sources.list.d S权限意思 php缺少和数据库连接的模块 使用root登陆数据库1698错误 字段解释 auth_socket解释 使用root登陆数据库方法 详细解释 首先在安装的时候&#xff0c;有一个dockerfile文件&a…
阅读更多...
day 18流的定位、文件IO以及Linux系统中时间的获取

day 18流的定位、文件IO以及Linux系统中时间的获取

流的定位 偏移量&#xff1a;读和写都在偏移量的位置进行 文件IO 相对于标准IO来说&#xff0c;文件IO直接在Linux的内核中操作&#xff0c;也更加的简洁精炼 对文件的操作也是三个部分 1.打开文件 open 2.读写文件 read write 3.关闭文件 close 还有一些其他的函数接口…
阅读更多...
vue3 命令运行窗口暴露网络地址，以及修改端口号

vue3 命令运行窗口暴露网络地址，以及修改端口号

一般情况下这里的地址是隐藏的 这里加上 --host 可以暴露网络地址&#xff0c;再加上--port --8080 就可以将端口号修改为8080&#xff08;修改后边的数字就可以修改为你想要的端口号&#xff09;
阅读更多...
linux安装配置jdk

linux安装配置jdk

①下载jdk安装包&#xff0c;放在/opt/app/software/java下 cd /opt/app/software/java②进行解压操作 tar -zxvf jdk-8u251-linux-x64.tar.gz③解压完成之后&#xff0c;进行环境变量的配置&#xff0c;shell下执行 vi ~/.bash_profile根据jdk的安装目录&#xff0c;加入 …
阅读更多...
【C++】学习笔记——智能指针

【C++】学习笔记——智能指针

文章目录 二十一、智能指针1. 内存泄漏2. 智能指针的使用及原理RAII智能指针的原理auto_ptrunique_ptrshared_ptrshared_ptr的循环引用weak_ptr删除器 未完待续 二十一、智能指针 1. 内存泄漏 在上一章的异常中&#xff0c;我们了解到如果出现了异常&#xff0c;会中断执行流…
阅读更多...
LocalDateTime计算两个时间之间的间隔

LocalDateTime计算两个时间之间的间隔

LocalDateTime计算两个时间之间的间隔 嘚吧嘚LocalDateTimeLocalDateLocalTime 嘚吧嘚 自从认识了LocalDateTime之后&#xff0c;使用的频率越来越高了&#xff0c;使用多了就不可避免的涉及到日期的比较、加减以及计算日期间隔这些操作。 但是我发现自己好像不会&#x1f605…
阅读更多...
2024年钉钉杯大学生大数据挑战赛倒计时，最后冲刺

2024年钉钉杯大学生大数据挑战赛倒计时，最后冲刺

2024第三届钉钉杯大学生大数据挑战赛倒计时&#xff0c;小编给大家带来非常实用的最后冲刺助力【A题】&#xff0c;&#xff08;看图资料预览&#xff09;&#xff1a; 中国烟草行业作为国家税收和财政收入的重要支柱&#xff0c;近年来销售收入持续增长。国家对此实行严格的专…
阅读更多...
一键测量仪，能否彻底解决燃气灶配件缺陷问题？

一键测量仪，能否彻底解决燃气灶配件缺陷问题？

燃气灶配件是指用于燃气灶的附件或零部件&#xff0c;用于安装、维护或改进燃气灶的功能和性能。这些配件通常包括各种零部件、附件和替换件&#xff0c;以确保燃气灶的正常运行和安全使用。燃气灶的火焰头是产生火焰的部件&#xff0c;通常根据不同的燃气类型和火力需求选择合…
阅读更多...
ETL数据集成丨快速将MySQL数据迁移至Doris数据库

ETL数据集成丨快速将MySQL数据迁移至Doris数据库

随着大数据技术的迅速发展&#xff0c;越来越多的企业开始寻求高效、灵活的数据存储与分析解决方案。Apache Doris&#xff08;原名 Palo&#xff09;作为一款高性能的MPP&#xff08;大规模并行处理&#xff09;分析型数据库&#xff0c;凭借其在OLAP场景下的卓越表现&#xf…
阅读更多...
Minio多主机分布式 docker-compose 集群部署

Minio多主机分布式 docker-compose 集群部署

参考 docker-compose搭建多主机分布式minio - 会bk的鱼 - 博客园 (cnblogs.com) 【运维】docker-compose安装minio集群-CSDN博客 Minio 是个基于 Golang 编写的开源对象存储套件&#xff0c;虽然轻量&#xff0c;却拥有着不错的性能 中文地址&#xff1a;MinIO | 用于AI的S3 …
阅读更多...
SYD88xx代码复位不成功和解决办法

SYD88xx代码复位不成功和解决办法

原来的复位代码如下: void ota_manage(void){#ifdef _OTA_if(ota_state){switch(ota_state){case 1 : #if defined(_DEBUG_) || defined(_SYD_RTT_DEBUG_)dbg_printf("start FwErase\r\n");#endifCmdFwErase();#if defined(_DEBUG_) || defined(_SYD_RTT_DEBUG_)db…
阅读更多...
Spring Boot 动态数据源

Spring Boot 动态数据源

目录 前言 前置环境 pom yml Entity Dao 枚举类 数据源 AOP Controller 启动类 演示 前言 大多数系统中&#xff0c;都需要数据库来持久化数据&#xff0c;在大多数情况下&#xff0c;一个系统只需要配置一个数据源便能够完成所有业务的查询&#xff0c;保存操作。…
阅读更多...
为什么Transformer需要进行 Multi-head Attention？

为什么Transformer需要进行 Multi-head Attention？

目录 1. 前言 2. 基本概念 2.1. Word2Vec 2.2. Attention is all you need 2.3. Self-attention 2.3.1. 概述self-attention 2.3.2. 训练细节 2.4. Multi-head Attention 2.4.1. 多头理论细节 2.4.2. 多头代码实现 2.5. 总结 3. 讨论观点 3.1. 观点1&#xff1a; …
阅读更多...
【工具插件类教学】vHierarchy 2工具编辑器扩展使用

【工具插件类教学】vHierarchy 2工具编辑器扩展使用

目录 一、下载导入 二、使用介绍 1.便捷小工具 a.图标和颜色Icons and colors b.对象组件缩略图Component minimap c.层级线展示Hierarchy lines d.极简模式Minimal mode e.斑马条纹图案Zebra striping f.激活切换Activation toggle 2、快捷键 一、下载导入 资源官方…
阅读更多...
二维码门楼牌管理应用平台建设：流程优化与全面考量

二维码门楼牌管理应用平台建设：流程优化与全面考量

文章目录 前言一、工作流程优化&#xff1a;移动端采集与实时更新二、数据完整性与准确性保障三、效率提升与成本节约四、扩展性与未来发展五、数据安全与隐私保护六、用户培训与技术支持 前言 随着智慧城市建设的不断深入&#xff0c;二维码门楼牌管理应用平台作为城市管理的…
阅读更多...
数据库事务处理技术——故障恢复

数据库事务处理技术——故障恢复

1. 数据故障恢复的宏观思路 我们知道DBMS是利用内存&#xff08;主存&#xff09;和外存&#xff08;辅存&#xff09;这样的存储体系进行数据库的管理&#xff0c;其中内存也就是我们常说的缓存是易失的。而事务时DBMS对数据库进行控制的基本单元&#xff0c;宏观上是由程序设…
阅读更多...
算法训练.

算法训练.

一.奶牛晒衣服 题解&#xff1a; 这应该是个二分题&#xff0c;但是我用的是贪心暴力写的&#xff0c;思想就是循坏每次都让湿度最高的使用一次烘衣机&#xff0c;要是湿度最高的可以在自然条件下都能晒干就结束循环&#xff0c;这样内部我第一想法就是每次都排个降序&#xf…
阅读更多...
windows下在线预览服务kkFileView4.4.0问题记录

windows下在线预览服务kkFileView4.4.0问题记录

前几天找到一个开源项目&#xff1a;kkFileView&#xff0c;感觉可能以后可能会用到&#xff0c;所以尝试了下。 通过git下载下来&#xff0c;版本是4.4.0&#xff0c;通过idea打开项目&#xff0c;发现老是无法找到组件aspose-cad&#xff0c;版本是23.9. 找了好多文章&#x…
阅读更多...
AI学习（1）软件的选择，cuda和pytorch的安装

AI学习（1）软件的选择，cuda和pytorch的安装

文章目录 1.使用VScode开发&#xff0c;结合anaconda配置python环境2.安装pytorch库3.深度学习相关的库1.numpy&#xff08;科学计算库&#xff09;2.pandas(数据分析处理库)3.matplotlib&#xff08;可视化库&#xff09;4.seaborn&#xff08;可视化库&#xff09; 1.使用VSc…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023