admin管理员组

文章数量:819699

数据结构与算法:队列——02

文章目录

  • 三、队列
    • 1、队列概述:
    • 2、单向队列【数组表现形式】:
    • 3、环形队列【数组表现形式】:

三、队列

1、队列概述:

定义:

  • 队列定义
    • 队列简称队,它也是一种操作受限的线性表。其限制为仅允许在表的一端插入,在表的另一端删除。可进行插入的一端为队尾,可进行删除的一端为队头。向队列插入新元素称为进队,从队列中删除元素称为出队。队列的特点概括起来就是:先进先出

队列跟数组的区别:

  • 数组对随机访问有较好性能
  • 链表对插入和删除元素有较好性能

应用方面:最常用的就是在宽度优先搜索 (BFS) 中,记录待扩展的节点。

2、单向队列【数组表现形式】:

问题引入:银行排队问题

  • front:初始值为-1,对应索引位待出列,若当前指向的数组下标的元素要出列,则front指针就要先向后一位,即front++;再执行出列动作。
  • rear:初始值为-1,对应索引位待入列,若当前指向的数组下标有元素要入列,则rear指针就要先向后一位,即rear++,再执行入列动作(索引位元素赋值)
  • 单向队列的判断条件:
    • 队空:front=rear
    • 队满:rear=maxsize-1

代码实现:

  • java

  • package 算法.数组.队列;import java.util.Scanner;public class Queue {public static void main(String[] args) {ArraryQueue queue = new ArraryQueue(3);boolean flag =true;Scanner scn = new Scanner(System.in);while (flag){System.out.println("添加【a】 获取单个【o】 获取所有【l】 退出程序【e】");String  key=scn.next();switch (key){case "a":try {System.out.print("请输入你的数:");queue.add(scn.nextInt());}catch (Exception e){System.out.println(e.getMessage());}break;case "o":try {queue.getone();}catch (Exception e){System.out.println(e.getMessage());}break;case "l":queue.getall();break;case "e":flag=false;System.out.println("程序终止~");break;}}}}
    class ArraryQueue{//头指针private int front;//尾指针private int rear;//初始化队列容量private int maxsize;//创建一个队列private int[] array;public ArraryQueue(int parameter) {maxsize=parameter;array = new int[maxsize];front=-1;rear=-1;}//判断队列是否为空public boolean IsEmpty(){return rear==front;}//判断队列是否已满public boolean IsFull(){return rear==maxsize-1;}//向对列中添加元素public void add(int number){//再添加元素时,我们需要判断队列是否已满,如果队列是满的情况下,我们不能进行添加if (IsFull()){throw new ArrayIndexOutOfBoundsException("对列容量已满,无法添加数据");}//初始化的尾指针为-1;因此我们需要先自增,在填充数据rear++;array[rear]=number;}//获取队列单个元素public void getone(){//要知道,我们这个数据是在队列中进行操作,要满足:先进先出的条件//1、要先判断队列是否为空,在空队列的情况下,进行异常抛出处理if (IsEmpty()){throw new RuntimeException("队列为空,不能获取数据");}//同理,队头指针是初始化为-1front++;System.out.println(array[front]);}//显示整个队列的现有所有元素public void getall(){//1、要先判断队列是否为空,在空队列的情况下,进行异常抛出处理if (IsEmpty()){System.out.println("队列在初始化的情况下,是空队列,且无法获取数据");return;}front++;for (int i = front; i < array.length; i++) {System.out.println(array[i]);}}
    }
    
  • 结果展示:

  • C语言实现:

    • 代码展示:

    • //标准输入输出库
      #include <stdio.h>
      //字符串操作库
      #include <string.h>
      //布尔类型库
      #include <stdbool.h>
      #include <stdlib.h>
      //宏定义,定义队列最大容量maxsize
      #define maxsize 7//创建队列结构体
      typedef struct queue{int arr[maxsize];int rear;int front;
      }queue;
      //队列初始化,一旦队列初始化,开始为队列分配堆空间
      struct queue* init(){struct queue* p=(queue*)malloc(sizeof(queue));if (p==NULL){printf("堆空间分配失败");exit(0);}//C语言中数组初始化后数组元素是随机的,因此我们要清洗数组memset(p->arr,0,sizeof(p->arr));//队列的头指针和尾指针p->front=-1;p->rear=-1;return p;
      }
      struct queue* p;
      bool flag=true;
      //声明函数
      extern bool isEmpty();
      extern bool isFull();
      extern void add(struct queue* p,int num);
      extern void getone();
      extern void getall();
      int main(void ) {//队列初始化p=init();char key;int num;while (flag){printf("添加【a】 获取单个【o】 获取所有【l】 退出程序【e】\n");scanf("%c",&key);switch (key) {case 'a':scanf("%d",&num);add(p,num);break;case 'o':getone();break;case 'l':getall();break;case 'e':flag = false;printf("程序终止~\n");break;default:break;}while(getchar() != '\n')continue;}return 0;
      }
      //1、判断队列是否为空
      bool isEmpty(){return p->rear==p->front;//当队列头指针与尾指针指向的位置相同即两者相等时,队列为空
      }
      //2、判断队列是否已满
      bool isFull(){return (maxsize-1)==p->rear;//当队列尾指针指向队列的最后一个位置时,队列已满。
      }
      //3、添加元素至队列
      void add(struct queue* p,int num){//添加元素至队列时需要判断队列是否已满if(isFull()){printf("当前队列已满,无法添加元素至队列");return;}//队列添加元素时,队列尾指针需要先进行移动,在进行赋值p->rear++;p->arr[p->rear]=num;
      }
      //4、获取单个元素
      void getone(){if (isEmpty()){printf("当前队列为空,无法获取具体值\n");return;}p->front++;printf("当前队列元素值:%d\n",p->arr[p->front]);
      }
      //5、获取队列所有元素
      void getall(){if (isEmpty()){printf("当前队列为空,无法获取具体值\n");return;}//获取队列的元素值时,我们需要将队列头指针先向前移动,在进行赋值while (!isEmpty()){p->front++;printf("当前队列元素值:%d\n",p->arr[p->front]);}
      }
    • 实现结果:

  • 单向队列的缺点:

    • 空间资源浪费:无法重复利用,只能进行一次入栈出栈操作
    • 因此我们引入环形队列,解决由于指针造成的队列空间浪费,避免假溢出。

3、环形队列【数组表现形式】:

环形队列分析:

  • front:初始值为0,对应索引位待出列,若当前指向的数组下标的元素要出列,则先执行出列动作(实际上不用操作,出列的索引位可以被新入队的元素覆盖),随后front指针就要向后一位,即front++

  • rear:初始值为0,对应索引位待入列,若当前指向的数组下标有元素要入列,则先执行入列动作(索引位元素赋值),随后front指针就要向后一位,即rear++

  • 环形队列的几个判断条件

    • front:指向队列的第一个元素,初始值front=0
    • rear: 指向队列的最后一个元素的后一个位置(预留一个空间作为约定),初始值rear=0
    • maxSize: 数组的最大容量
    • 队空:front == rear
    • 队满:(rear+1)%maxSize == front
    • 队列中的有效数据个数:(rear+maxSize-front)% maxSize或者(rear + 1-front) % maxSize,为什么会这样?实际上只是因为指针从0记起,而容量是从1记起。错位1.
  • 注意事项:

    • front=rear=0的歧义

      • 在循环队列中,我们发现空载时front=rear=0,满载时依然有front=rear=0!这样子我们就无法判断front=rear时,队列是空还是满,因此rear=rear%maxSize这种解决方案是不被允许的
      • 因此我们引入置空位,人为规定,数组中必须留有一个索引位不得放置元素,必须置空!!!,由此得到队满公式:(rear+1)%maxSize == front
    • 队列中的有效数据个数:(rear+maxSize-front)% maxSize

      • 如上图所示,出队列中,环形队列中含有三个元素,对头指针为front=2,队尾指针rear=5【先先执行入列,后指针后移,rear++】,maxsize=6,因此有效数据为(5+6-2)%6=3

环形队列的优点:

避免假溢出现象(由于入队和出队的操作,头尾指针只增加不减少,致使被删元素的空间永远无法重新利用,当队列继续存储元素时,出现尾指针已经到达了队列尾,而实际头指针前面并未满的情况),可以将队列空间充分重复利用
首尾相连的FIFO的数据结构,采用数据的线性空间,数据组织简单,能快速知道队列是否满/空
广泛用于网络数据收发,和不同程序间数据交换,均使用了环形队列

代码实现:

  • java

  • package 算法.队列;import java.util.Scanner;public class CircleQueue {public static void main(String[] args) {CircleArraryQueue queue = new CircleArraryQueue(4);boolean flag =true;Scanner scn = new Scanner(System.in);while (flag){System.out.println("添加【a】 获取单个【o】 获取所有【l】 退出程序【e】 尾下标【p】头下标【h】");String  key=scn.next();switch (key) {case "a":try {System.out.print("请输入你的数:");queue.add(scn.nextInt());} catch (Exception e) {System.out.println(e.getMessage());}break;case "o":try {queue.getone();} catch (Exception e) {System.out.println(e.getMessage());}break;case "l":queue.getall();break;case "e":flag = false;System.out.println("程序终止~");break;case "h":queue.head();break;case "p":queue.party();break;}}}
    }
    class CircleArraryQueue{//头指针private int front;//尾指针private int rear;//初始化队列容量private int maxsize;//创建一个队列private int[] array;public CircleArraryQueue(int parameter) {maxsize=parameter;array = new int[maxsize];front=0;rear=0;}//判断队列是否为空public boolean IsEmpty(){return rear%maxsize==front%maxsize;}//判断队列是否已满public boolean IsFull(){return (rear+1)%maxsize==front;}//向对列中添加元素public void add(int number){//再添加元素时,我们需要判断队列是否已满,如果队列是满的情况下,我们不能进行添加if (IsFull()){throw new ArrayIndexOutOfBoundsException("对列容量已满,无法添加数据");}array[rear]=number;//初始化的尾指针为0;因此我们需要先填充数据,再将指针后移,因为我们这里默认初始指针为0,在数组中,array[0]其实是含有值得的,如果使用自增,我们可能存在漏用空间的情况,因此必须考虑取模。rear=(rear+1)%maxsize;}//获取队列单个元素public void getone(){//要知道,我们这个数据是在队列中进行操作,要满足:先进先出的条件//1、要先判断队列是否为空,在空队列的情况下,进行异常抛出处理if (IsEmpty()){throw new RuntimeException("队列为空,不能获取数据");}System.out.println(array[front]);//注意这里的一个事项,如果我们在这里进行取模,它是进行一个相对运动,为什么?简单讲,数组未运动,对应指针会进行移位,这里驱魔过后,我们相对进行数组后前移front=(front+1)%maxsize;}//显示整个队列的现有所有元素public void getall(){//1、要先判断队列是否为空,在空队列的情况下,进行异常抛出处理if (IsEmpty()){System.out.println("队列在初始化的情况下,是空队列,且无法获取数据");return;}for ( ;front <front+size(); front++) {System.out.println("array["+front%maxsize+"]:"+array[front%maxsize]);}}//获取循环队列有效数据个数public int  size(){return (rear+maxsize-front)%maxsize;}//获取队头指针public void  head(){System.out.println(front);}//获取队尾指针public void party(){System.out.println(rear);}
    }
  • 效果展示:

  • 注意事项【上述代码中】:

    • front=(front+1) % maxsize;rear=(rear+1)%maxsize;探究原理:
    • 如果使用指针自增,而不进行取模运算,这里会照成下标越界【这里的队列是在数组上进行模拟的,初始化的数组容量为4,不能造成数组下标越界。跟单向队列造成同理缺点】:

单向队列与循环队列的根本在于不能让下标进行越界,我们在优化过程进行了取模运算【循环队列】,从而造成空间的重复利用,队头指针跟队尾指针在满载情况下能进行复原。

  • C语言实现:

    • 代码展示:

    • /*
      *文件名:CircleQueue.c
      *作者  :张水图
      *日期  : 2023/2/16
      *功能  :利用C语言实现环形队列相关操作,这里用数组模拟
      */
      #include<stdio.h>
      #include<math.h>
      #include<string.h>
      #include<stdlib.h>
      #include<stdbool.h>
      //宏定义:创建环形队列的最大容量maxsize
      #define maxsize 7
      //创建关于环形队列的结构体
      typedef struct CircleQueue{int data[maxsize];int front;//头指针int rear;//尾指针
      }cq;
      //队列的结构体指针:提高作用域为全局变量
      struct CircleQueue* q;
      //环形队列初始化
      struct CircleQueue* init(){//为结构体初始化分配对空间q=(cq*)malloc(sizeof(cq));if (q==NULL){printf("申请分配堆空间失败");exit(0);}//C语言中数组初始化后数组元素是随机的,因此我们要清洗数组memset(q->data,0,sizeof(q->data));//初始化环形队列的头指针跟尾指针,q->front=0;q->rear=0;return q;
      }
      bool flag=true;
      //函数声明
      static bool isFull();
      static bool isEmpty();
      static void add(int num);
      static void getone();
      static void getall();
      static int size();
      static int gethead();
      static int getrear();
      int main(void) {//队列结构体指针初始化q=init();char key;int num;while (flag){printf("添加【a】 获取单个【o】 获取所有【l】 退出程序【e】 尾下标【p】头下标【h】\n");//刷新缓存,清除上一次的scanf的键入值.fflush(stdin);scanf("%c",&key);switch (key) {case 'a':scanf("%d",&num);add(num);break;case 'o':getone();break;case 'l':getall();break;case 'e':flag=false;break;case 'p':printf("尾下标:%d\n",getrear());break;case 'h':printf("头下标:%d\n",gethead());break;}}return 0;
      }
      //注:环形队列的规定:人为规定,数组中必须留有一个索引位不得放置元素,必须置空!
      //判断环形队列是否为空
      static bool isEmpty(){return (q->front)%maxsize==q->rear%maxsize;//当前头指针与尾指针
      }
      //判断环形队列是否已满
      static bool isFull(){return (q->rear+1)%maxsize==q->front;//因此判断队列已满时,必须预留一个数组空位,否则与队列判空冲突。
      }
      //添加函数
      static void add(int num){if (isFull()){printf("当前循环队列已满,无法添加其余元素\n");return;}q->data[q->rear]=num;q->rear=(q->rear+1)%maxsize;
      }
      //获取环形队列单个元素
      static void getone(){if (isEmpty()){printf("当前链表元素为空,无法获取具体值\n");return;}printf("当前队列元素值:%d\n",q->data[q->front]);q->front=(q->front+1)%maxsize;
      }
      //获取环形队列所有元素
      static void getall(){if (isEmpty()){printf("当前链表元素为空,无法获取具体值\n");return;}while (q->front<(q->front+size())){printf("当前队列值:%d\n",q->data[q->front%maxsize]);q->front++;}
      }
      //获取队列剩余个数
      static int size(){return (q->rear+maxsize-q->front)%maxsize;
      }
      //获取头指针
      int gethead(){return q->front;
      }
      //获取尾指针
      int getrear(){return q->rear;
      }
    • 结果展示:

本文标签: 数据结构与算法队列02