JAVA数据结构和算法（2）之队列

骑猪看日落 2022-12-23 02:00 163阅读 0赞

上周学习JAVA 数据结构和算法中的队列，写点东西，记录下来，以备后查，主要从四个方面介绍（1）队列应用场景 （2）队列详细介绍（3）数组模拟队列的思路分析和代码实现（4）环形队列的思路分析和代码实现（5）总结。

### **（一）队列的应用场景** ###

现实场景：队列在日常生活中十分常见，例如：银行排队办理业务、食堂排队打饭等等。银行排队叫号，四个业务员，为排队的人的服务，每有一个业务员服务完成后，这时下一位被服务者从下面的队列中产生。排队的人遵循先来后到的原则一次等待被窗口叫到，以提供所需的服务，那么，排队的人群就相当于队列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70][]

比如我们去电影院排队买票，第一个进入排队序列的都是第一个买到票离开队列的人，而最后进入排队序列排队的都是最后买到票的。

比如在计算机操作系统中，有各种队列在安静的工作着，比如打印机在打印列队中等待打印。

那么，什么时队列呢？又如何利用Java来实现队列呢？

### （二）队列详细介绍 ###

队列是一个有序的线性列表，可以用数组或链表来实现，遵循先入先出的原则，即先存入队列的数据，要先取出，后存入的数据，要后取出。与堆栈不同在于，队列是两端都可以被使用的结构，一端用于添加新元素而另一端删除元素，，也可以只有一端插入或删除数据。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

![å¨è¿éæå¥å¾çæè¿°][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM1MDEyMA_size_16_color_FFFFFF_t_70_pic_center]

队列分为：

> 1.  　　单向队列（Queue）：只能在一端插入数据，另一端删除数据。
> 2.  　　双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。

在队列中，队头与队尾：允许元素插入的一端称为队尾，允许元素删除的一端称为队头。入队：队列的插入操作，出队：队列的删除操作，如下，我们向一个完整的队列展示入栈操作，向其中添加数字 1，2，3，流程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3OTE3OA_size_16_color_FFFFFF_t_70][]

向一个队列取出1，2，3；出栈的操作如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3OTE3OA_size_16_color_FFFFFF_t_70 1][]

### （三）数组模拟队列的思路分析和代码分析 ###

队列本身是有序列表，那么，如何利用数组实现队列的增删改查呢？

若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:

![å¨è¿éæå¥å¾çæè¿°][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：

思路分析 将尾指针往后移：rear+1 , 当front == rear 【空】 ，若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear  == maxSize - 1\[队列满\]；即：

>  *  front 是队列最前元素之前一个位置【不含最前】
>  *  rear 是队列最后元素 【含最后】
>  *  插入队列，判断是否已满，将尾指针往后移：rear++，然后插入arr\[rear\]
>  *  移出队列，判断是否为空，将前指针往后移：front++，然后移出arr\[front\]
>  *  队列为空判断条件：当front == rear 【空】
>  *  队列是否满判断条件：rear == maxSize - 1【队列满】

当我们明白对于队列的实现逻辑之后，利用数组的实现代码为：

package JAVADATASTRTUCRE;
    
    import java.util.Scanner;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/16
     * Time: 17:06
     * Description: No Description
     */
    
    /*
    问题：队列不能重复使用
     */
    public class arrayQueueDemo {
        public static void main(String[] args) {
            ArrayQueue arrayQueue = new ArrayQueue(3);
            char key;//接受用户输入
            Scanner scanner =new Scanner(System.in);
            boolean loop=true;
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get)：从队列中取数据");
                System.out.println("h(head):查看队列头部数据");
                key=scanner.next().charAt(0);
                switch (key){
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数");
                        int value=scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try{
                            int res =arrayQueue.getQueue();
                            System.out.println("去除的数据为"+res);
                        }catch(Exception E){
                            System.out.println(E.getMessage());
                        }
                        break;
                    case 'h':
                        try{
                            int head =arrayQueue.headQueue();
                            System.out.println("头部的数据为"+head);
                        }catch(Exception E){
                            System.out.println(E.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop=false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出！！！！");
        }
    }
    
    class ArrayQueue{
    
        private int maxSiaze;//队列的最大容量
        private int front;//队列头部
        private int rear;//队列尾部
        private int []arr;//用于1存放数据，模拟队列
    
        //创建队列的构造器
        public ArrayQueue(int arrMaxSize){
              maxSiaze=arrMaxSize;
              arr=new int[maxSiaze];
              front=-1;//指向队列头部的前一个位置，
              rear=-1;//指向队列尾部的数据（即队列的最后一个数据）
        }
    
    //判断队列是否满
        public  boolean isFull(){
            return rear==maxSiaze-1;
        }
    //判断队列是否为空
        public boolean isEmpty(){
         return rear==front;
        }
    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if(isFull()){
            System.out.println("队列已满，");
            return;
        }
          rear++;
          arr[rear]=n;
    
    }
    //出队列
    public  int getQueue(){
            //判断队列是否为空
    
        if(isEmpty()){
            //抛出异常
            throw new RuntimeException("队列空，不能取数据");
        }
        front++;
        return arr[front];
    }
    //显示队列所有数据
    public void showQueue(){
     if(isEmpty()){
         System.out.println("队列为空，没有数据");
         return;
     }
       for(int i=0;i<arr.length;i++){
           System.out.printf("arr[%d]=%d\n",i,arr[i]);
       }
    }
    //显示队列的头数据，并非取数据
    public int headQueue(){
            if(isEmpty()){
                //System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front+1];
        }
    }

运行结果为：

s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    队列为空，没有数据
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    12
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    23
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    32
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    arr[0]=12
    arr[1]=23
    arr[2]=32
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    g
    去除的数据为12
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    h
    头部的数据为23
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据

实现思路二：

package DataStrtureDemo;
    
    import java.util.LinkedList;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/20
     * Time: 8:57
     * Description: No Description
     */
    public class arrayQueueDemo {
        public static void main(String[] args) {
            ArrayQueue queue = new ArrayQueue(5);
            queue.printAll();
            System.out.println(queue.isFull());
            //queue.enQueue(6);
            System.out.println(queue.isEmpty());
    
    
    
        }
    }
    
    class ArrayQueue{
        private int first,last,size;
        private Object[]  storage;
    
        public ArrayQueue(){
            this(100);
        }
        public ArrayQueue(int n){
            size=n;
            storage=new Object[size];
            first=last=-1;
        }
        public boolean isFull(){
            return first==0 && last==size-1||first==last+1;
        }
        public boolean isEmpty(){
            return first==-1;
        }
        //队列尾部添加元素
        public void enQueue(Object e){
            if(last==size-1||last==-1){
                storage[0]=e;
                last=0;
                if(first==-1){
                    first=0;
                }
            } else{
                storage[++last]=e;
            }
        }
        //从队列中取出元素
        public Object  dequeue(){
            Object tmp=storage[first];
            if(first==last){
                last=first=-1;
            }else if(first==size-1){
                first=0;
            }else {
                first++;
            }
            return tmp;
        }
        public void printAll(){
            for(int i=0;i<size;i++){
                System.out.println(storage[i]+"   ");
            }
        }
    
    
    
    }
    
    class  Queue{
        private LinkedList list=new  LinkedList();
    
        //构造器
        public Queue(){
    
        }
        public boolean isEmpty(){
            return list.isEmpty();
        }
        //第一个元素
        public Object firstEl(){
            return list.getFirst();
        }
    //获取最后一个元素
        public Object  lastEl(){
            return list.getLast();
        }
        public Object dequeue(){
            return list.removeFirst();
        }
        public void enqueue(Object e){
            list.addLast(e);
        }
        public String toString(){
            return list.toString();
        }
    }

运行结果为：

null   
    null   
    null   
    null   
    null   
    false
    true
    
    Process finished with exit code 0

### （四）环形队列的思路分析和代码实现 ###

使用环形队列的原因：

> （1）目前队列使用一次即可，无法达到复用
> 
> （2）设计环形队列，取模%

若队头指针会指向一个较高的下标位置，如下图：

![00193397a3c079eedade883669af1567.png][]

队列中新增数据时，队尾的指针rear 会向上移动，也就是向下标大的方向。移除数据项时，队头指针 front 向上移动。那么这样设计好像和现实情况相反，比如排队买电影票，队头的买完票就离开了，然后队伍整体向前移动。在计算机中也可以在队列中删除一个数之后，队列整体向前移动，但是这样做效率很差。我们选择的做法是移动队头和队尾的指针。

如果这样移动指针，相信队尾指针很快就移动到数据的最末端了，这时候可能移除过数据，那么队头会有空着的位置，然后新来了一个数据项，由于队尾不能再向上移动了，那该怎么办呢？如下图：

![5b0a16a04e4f91a25597942972883d39.png][]

为了避免队列不满却不能插入新的数据，我们可以让队尾指针绕回到数组开始的位置，这也称为“循环队列”。

![e2c093ca7cbc659189877e4ebf11584c.png][]

即如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 1][]

环形队列的实现考虑：

> 1.front变量的含义做调整：front指向队列的第一个元素，即arr\[front\]就是队列的第一个元素
> 
> 2.rear变量的含义做调整：rear指向队列的最后一个元素的后一个元素，**因为希望空出一个空间作为约定（队列实际容量=maxSize-1，理解为防止指向超出数组范围的地方报错）**。
> 
> 3.当队列满时，条件是：**(rear + 1) % maxSize == front \[满\] **
> 
> 4.当队列空时，条件是：**rear == front \[空\]**
> 
> 5.队列中有效数据的个数：**(rear + maxSize - front) % maxSize**
> 
> 6.插入队列时，判断队满，先插入队列arr\[rear\]，然后rear++
> 
> 7.移出队列时，判断队空，先移出队列arr\[front\]，然后front++

综上：环形队列的设计思路为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 2][]

环形队列的代码实现为：

package JAVADATASTRTUCRE;
    
    import java.util.Scanner;
    
    /**
     * Created with IntelliJ IDEA.
     * User:  yongping Li
     * Date: 2020/11/16
     * Time: 21:24
     * Description: No Description
     */
    public class circleArrayQueueDemo {
        public static void main(String[] args) {
            System.out.println("测试数组环形队列");
            circleArrayQueue arrayQueue = new circleArrayQueue(3);
            char key;//接受用户输入
            Scanner scanner =new Scanner(System.in);
            boolean loop=true;
            while(loop){
                System.out.println("s(show):显示队列");
                System.out.println("e(exit):退出程序");
                System.out.println("a(add):添加数据到队列");
                System.out.println("g(get)：从队列中取数据");
                System.out.println("h(head):查看队列头部数据");
                key=scanner.next().charAt(0);
                switch (key){
                    case 's':
                        arrayQueue.showQueue();
                        break;
                    case 'a':
                        System.out.println("请输入一个数");
                        int value=scanner.nextInt();
                        arrayQueue.addQueue(value);
                        break;
                    case 'g':
                        try{
                            int res =arrayQueue.getQueue();
                            System.out.println("去除的数据为"+res);
                        }catch(Exception E){
                            System.out.println(E.getMessage());
                        }
                        break;
                    case 'h':
                        try{
                            int head =arrayQueue.headQueue();
                            System.out.println("头部的数据为"+head);
                        }catch(Exception E){
                            System.out.println(E.getMessage());
                        }
                        break;
                    case 'e':
                        scanner.close();
                        loop=false;
                        break;
                    default:
                        break;
                }
            }
            System.out.println("程序退出！！！！");
        }
    }
    
    class circleArrayQueue{
    
        private int maxSiaze;//队列的最大容量
        private int front;//队列头部,指向队列第一个元素，初始值为0
        private int rear;//队列尾部，指向对列最后一个元素的最后一个位置，初始值为0
        private int []arr;//用于1存放数据，模拟队列
    
        //创建队列的构造器
        public circleArrayQueue(int arrMaxSize){
            maxSiaze=arrMaxSize;
            arr=new int[maxSiaze];
    
        }
    
        //判断队列是否满
        public  boolean isFull(){
            return (rear+1)%maxSiaze==front;
        }
        //判断队列是否为空
        public boolean isEmpty(){
            return rear==front;
        }
        //添加数据到队列
        public void addQueue(int n){
            //判断队列是否满
            if(isFull()){
                System.out.println("队列已满，");
                return;
            }
            arr[rear]=n;
            //将rear后移，取模
            rear=(rear+1) % maxSiaze;
    
        }
        //出队列，取数据
        public  int getQueue(){
            //判断队列是否为空
            if(isEmpty()){
                //抛出异常
                throw new RuntimeException("队列空，不能取数据");
            }
            //分析front指向队列第一个元素
            //1，front保存到一个临时变量 2.临时保存的变量返回
            //3,front后移，考虑取模
            int value=arr[front];
            front=(front+1)%maxSiaze;
            return value;
        }
        //显示队列所有数据
        public void showQueue(){
            if(isEmpty()){
                System.out.println("队列为空，没有数据");
                return;
            }
            //从front开始便利，遍历多少个元素
            for(int i=0;i<front+getQueueSize();i++){
                System.out.printf("arr[%d]=%d\n",i%maxSiaze,arr[i%maxSiaze]);
            }
        }
        //显示队列的头数据，并非取数据
        public int headQueue(){
            if(isEmpty()){
                //System.out.println("队列为空");
                throw new RuntimeException("队列为空");
            }
            return arr[front];
        }
    
        //返回当前队列有效数据的个数
        public int getQueueSize(){
            return (rear+maxSiaze-front)%maxSiaze;
        }
    
    }

运行结果为：

测试数组环形队列
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    队列为空，没有数据
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    12
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    34
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    234
    队列已满，
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    arr[0]=12
    arr[1]=34
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    h
    头部的数据为12
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    g
    去除的数据为12
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    arr[0]=12
    arr[1]=34
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    g
    去除的数据为34
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    g
    队列空，不能取数据
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    a
    请输入一个数
    1
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据
    s
    arr[0]=12
    arr[1]=34
    arr[2]=1
    s(show):显示队列
    e(exit):退出程序
    a(add):添加数据到队列
    g(get)：从队列中取数据
    h(head):查看队列头部数据

### （五）总结 ###

队列是一种线性表，遵行先进先出的原则存储数据。通常是用来简化某些程序操作的数据结构，而不是主要作为存储数据的。对于队列而言，增删改查，可以通过数组来实现。设计环形列表的目的在于数组的重复使用。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70]: /images/20221120/5b6ff904e6bb4d75b5bff732ba757ce9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTM1MDEyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/d9b9568e7dc441d78841e499af932120.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3OTE3OA_size_16_color_FFFFFF_t_70]: /images/20221120/2e60c53a954c4860850ce80942573820.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI3OTE3OA_size_16_color_FFFFFF_t_70 1]: /images/20221120/7627363bd1d446dfbf08e35c70f25e44.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]: /images/20221120/0aaba927ba184287b75a1fade8391198.png
[00193397a3c079eedade883669af1567.png]: /images/20221120/a8efd6aa55f2402f9d844c026b23eb5e.png
[5b0a16a04e4f91a25597942972883d39.png]: https://img-blog.csdnimg.cn/img_convert/5b0a16a04e4f91a25597942972883d39.png
[e2c093ca7cbc659189877e4ebf11584c.png]: https://img-blog.csdnimg.cn/img_convert/e2c093ca7cbc659189877e4ebf11584c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201121210544799.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201121210927185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg==,size_16,color_FFFFFF,t_70