数据结构の线性结构の队列 | Monster

数据结构の线性结构の队列

队列
  • 队列是一个有序列表,可以用数组或是链表来实现
  • 遵循先入先出的原则,即:先存入队列的数据,要先取出,后存入的要后取出
  • 应用场景:排队叫号
数组模拟队列
  • 队列本身是一个有列表,若使用数组的结构来存储队列的数据

  • 模拟一个单向的基础队列

    • 设定maxSize为队列的最大容量,startIndex为队列的头部指针,endIndex为队列的尾部指针,arr为模拟队列存储数据的数组

    • 队列的入队与出队流程大概是这样的

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      // 使用数组模拟队列
      class MyArrayQueue{

      private int maxSize; // 队列的最大容量

      private int startIndex; // 队列头

      private int endIndex; // 队列尾

      private int[] arr; // 存放数据的数组


      // 初始化
      public MyArrayQueue(int size){
      this.arr = new int[size]; // 传参定义队列容量
      this.maxSize = size;
      this.startIndex = -1; // 初始化队列的头部为空队列的前一个位置 -1,当有元素出队列时增加到上一位
      this.endIndex = -1; // 初始化队列尾部为-1,当有元素入队列时增加
      }


      // 判断队列是否为空
      public boolean isEmpty(){
      // 同初始化的情况一样,当队列头与尾相同的时候,说明其之间并没有数据
      return this.startIndex == this.endIndex;
      }

      // 判断队列是否满
      public boolean isFull(){
      // 因为 endIndex 随着数据的插入而增加,endIndex一直维持与队列最后一个元素索引相同的位置,当索引为 max-1时说明已经到达最后一个位置
      return this.endIndex == this.maxSize - 1;
      }

      // 添加元素入队
      public void addQueue(int element){
      // 如果队列已经满了则不可添加
      if(this.isFull()){
      // TODO 队列已满
      return;
      }
      this.endIndex ++ ; //队列尾指针后移
      this.arr[endIndex] = element; //赋值元素
      }

      // 出队列
      public int getElement(){
      // 如果队列为空 则 没有数据出队
      if(this.isEmpty()){
      // TODO 队列为空
      throw new RuntimeException("queue is empty,nothing to get");
      }
      this.startIndex++; // 队列头指针后移
      int num = this.arr[startIndex]; // 此时的指针指向第一个元素,队列中的第一个元素出队,startIndex依旧指向第一个元素的前一个位置
      if(this.startIndex==endIndex){
      // TODO 队列中的数据已经被取完了 初始化队列
      this.startIndex = -1;
      this.endIndex = -1;
      this.arr = new int[this.maxSize];
      }
      return num;
      }


      // 获取队列的值
      public void showQueue(){
      if(this.isEmpty()){
      // TODO 队列为空
      System.out.println("queue is empty");
      return;
      }
      for (int i = 0; i <= this.endIndex ; i++) {
      if(i >= this.startIndex){
      System.out.printf("%d\t",this.arr[i]);
      }
      }

      }

      //测试
      public static void main(String[] args) {
      MyArrayQueue queue = new MyArrayQueue(5);
      // 往队列中添加数据
      queue.addQueue(1);
      queue.addQueue(2);
      queue.addQueue(3);
      queue.addQueue(4);
      queue.addQueue(5);
      queue.showQueue();
      System.out.println();
      // 出队两个
      System.out.println(queue.getElement());
      System.out.println(queue.getElement());
      queue.showQueue();



      }
      }
  • 使用上述队列会有一个问题,当队列的最后一个位置存放了数据,之后即便出队this.endIndex == this.maxSize也是成立的,无法继续入队数据,此时期望能在队列中找到空的位置能继续入队数据,使用循环队列

  • 模拟一个循环队列

    • 条件同上述一致,但是在满足构成循环队列要求时,对于startIndexendIndex的变化需要求模计算,对其队列中有空值的指针进行入队

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      // 使用数组 模拟环形队列
      class LoopMyQueue {
      private int maxSize;

      private int startIndex;

      private int endIndex;

      private int[] arr;

      public LoopMyQueue(int size) {
      this.arr = new int[size];
      this.maxSize = size;
      this.startIndex = -1; // 表示队列第一个数据的指针 没有数据则为-1
      this.endIndex = -1; // 表示队列最后一个数据的指针 没有数据则为-1
      }


      // 判断是否为空
      public boolean isEmpty() {
      return this.startIndex == -1; //为空时自动将startIndex设置为-1
      }

      // 判断是否满
      public boolean isFull() {
      // 因为此时队列是一个环形队列 通过求模的方式判断 也可以用绝对值
      return (this.endIndex + 1) % this.maxSize == this.startIndex; // 当startIndex的绝对值与enIndex的绝对值相等时 构成闭环 说明此队列已经填满
      }

      // 添加数据
      public void addQueue(int element) {
      if (this.isFull()) {
      // TODO 队列已满
      return;
      }
      if (this.isEmpty()){
      // TODO 队列为空 添加数据时候将startIndex指向第一个元素
      this.startIndex = 0;
      }
      this.endIndex = (this.endIndex + 1) % this.maxSize; // 求模得到下一个位置 等同 只是考虑了环形让其不越界 endIndex++

      this.arr[this.endIndex] = element; // 添加数据 endIndex指向最后一个元素的位置
      }


      // 从队列中删除元素 通过改变指针
      public void delElement(){
      if(this.startIndex == this.endIndex){
      // 队列中的数据已经被取完了 置空
      this.startIndex = -1;
      this.endIndex = -1;
      }
      this.startIndex = (this.startIndex + 1) % this.maxSize; // startIndex ++

      }

      // 出队列
      public int getQueue() {
      if (this.isEmpty()) {
      // TODO 队列为空
      throw new RuntimeException(" queue is empty");
      }

      int num = this.arr[this.startIndex]; // 得到元素
      // 改变 指针 删除出列的元素
      this.delElement();
      return num;
      }

      // 得到队列的有效数据个数
      public int getSum() {
      return (this.endIndex + this.maxSize - this.startIndex) % this.maxSize + 1;
      }

      // 输出队列
      public void showQueue() {
      int num = this.getSum();
      for (int i = startIndex; i < startIndex+num ; i++) {
      if(i < this.arr.length){
      System.out.printf("%d\t",this.arr[i]);
      }else{
      System.out.printf("%d\t",this.arr[i-arr.length]);
      }
      }

      }


      // 测试
      public static void main(String[] args) {
      LoopMyQueue myQueue = new LoopMyQueue(5);
      myQueue.addQueue(1);
      myQueue.addQueue(2);
      myQueue.addQueue(3);
      myQueue.addQueue(4);
      myQueue.addQueue(5);
      myQueue.showQueue();
      System.out.println();
      // 出列
      System.out.println(myQueue.getQueue());
      System.out.println(myQueue.getQueue());
      myQueue.showQueue();
      System.out.println();
      // 入列
      myQueue.addQueue(6);
      myQueue.addQueue(7);
      myQueue.showQueue();

      }


      }
-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%