队列

队列的一个使用场景

银行排队的案例:

银行柜台都有人办理业务时,后面来的人,就要进行抽号排队(先来的人号肯定在前面)。

有人业务办理完后,柜台会进行叫号(从最前面的号开始叫)。

队列介绍

  • 队列是一个有序列表,可以用数组或者链表来实现。
  • 遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的数据要后取出。
  • 示意图:(使用数组模拟队列示意图)

        

 数组模拟队列思路

  • 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如上图,

          其中maxSize是该队列的最大容量。

  • 因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front 及 rear 分别

          记录队列前后端的下标,front 会随着数据输出而改变,而 rear 则是随着数据输入而改变。

 代码实现

  1 package com.jyj.queue;
  2
  3 import java.util.Scanner;
  4
  5 public class ArrayQueueDemo {
  6     public static void main(String[] args) {
  7         //测试
  8         ArrayQueue queue = new ArrayQueue(3);
  9         char key = ' ';//接收用户输入
 10         Scanner scanner = new Scanner(System.in);
 11         boolean loop = true;
 12
 13         //输出一个菜单
 14         while(loop) {
 15             System.out.println("s(show):显示队列");
 16             System.out.println("a(add):添加数据到队列");
 17             System.out.println("g(get):从队列中获取元素");
 18             System.out.println("h(head):查看队列头的数据");
 19             System.out.println("e(exit):退出程序");
 20             //接收键盘输入的字符串,并且取出它的第一个字符
 21             key = scanner.next().charAt(0);
 22             switch(key) {
 23             case 's':
 24                 queue.showQueue();
 25                 break;
 26             case 'a':
 27                 System.out.println("输入一个数:");
 28                 int value = scanner.nextInt();
 29                 queue.addQueue(value);
 30                 break;
 31             case 'g'://抛异常了,要捕获
 32                 try {
 33                     int res = queue.getQueue();
 34                     System.out.printf("取出的数据是%d\n",res);
 35                 } catch (Exception e) {
 36                     //对所捕获异常的处理
 37                     System.out.println(e.getMessage());
 38                 }
 39                 break;
 40             case 'h'://抛异常了,要捕获
 41                 try {
 42                     int head = queue.headQueue();
 43                     System.out.printf("队列头的数据是%d\n",head);
 44                 }catch (Exception e) {
 45                     //对所捕获异常的处理
 46                     System.out.println(e.getMessage());
 47                 }
 48                 break;
 49             case 'e':
 50                 scanner.close();
 51                 loop = false;
 52                 break;
 53             default:
 54                 break;
 55             }
 56         }
 57         System.out.println("程序退出");
 58     }
 59 }
 60
 61 //使用数组模拟队列编写一个ArrayQueue类
 62 class ArrayQueue {
 63     private int maxSize;//数组的最大容量
 64     private int front;//队列头
 65     private int rear;//队列尾
 66     private int[] arr;//用于存放数据
 67
 68     //创建队列的构造器
 69     public ArrayQueue(int arrMaxSize) {
 70         maxSize = arrMaxSize;
 71         arr = new int[maxSize];
 72         front = -1;//指向队列头部,分析出front是指向队列头的前一个位置
 73         rear = -1;//指向队列尾,指向队列尾的数据(即队列最后一个数据)
 74     }
 75
 76     //判断队列是否为空
 77     public boolean isEmpty(){
 78         return front == rear;
 79     }
 80
 81     //判断队列是否满
 82     public boolean isFull(){
 83         return rear == maxSize - 1;
 84     }
 85
 86     //添加数据到队列
 87     public void addQueue(int value) {
 88         //判断是否满
 89         if(isFull()) {
 90             System.out.println("队列满,不能加入数据");
 91             return;
 92         }
 93         rear++;//尾指针后移
 94         arr[rear] = value;
 95     }
 96
 97     //获取队列的数据,出队列
 98     public int getQueue() {
 99         //判空
100         if(isEmpty()) {
101             //抛出异常
102             throw new RuntimeException("队列空,不能取数据");
103         }
104         front++;//front后移
105         return arr[front];
106     }
107     //显示队列所有数据
108     public void showQueue(){
109         //判空
110         if(isEmpty()){
111             System.out.println("队列空,没有可显示的数据");
112             return;
113         }
114         for(int i = 0;i < arr.length;i++) {
115             System.out.printf("arr[%d] = %d\n",i,arr[i]);
116         }
117     }
118
119     //显示队列的头数据,注意不是取出
120     public int headQueue(){
121         //判空
122         if(isEmpty()) {
123             throw new RuntimeException("队列空,没有可取的头数据");
124         }
125         //注意:front指向的是队列头的前一个数据。(更小的一个位置)
126         return arr[front + 1];
127     }
128 }
View Code

问题分析并优化

1)目前数据使用一次就不能使用,没有达到复用的效果。

2)将这个数组使用算法,该进成一个环形的队列   取模 %

环形队列

对前面的数组模拟队列的优化,充分利用数组,因此将数组看做是一个环形的。(通过取模的方式来实现即可)

分析说明

分析示意图:

1)front 变量的含义做一个调整:front 就指向队列的第一个元素,也就是说arr[front] 就是队列的第一个元素,front 的初始值 = 0。

2)rear 变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间作为约定,rear 的初始值 = 0。

3)当队列满时,条件是 (rear + 1) % maxSize == front【满】

4)当队列为空的条件是 rear == front 【空】

5)当我们这样分析时,队列中有效的数据的个数 (rear + maxSize - front) % maxSize

6)修改原来的队列,做成一个环形队列。

代码实现

  1 package com.jyj.queue;
  2
  3 import java.util.Scanner;
  4
  5 public class CircleArrayQueueDemo {
  6     public static void main(String[] args) {
  7         //测试
  8         System.out.println("数组模拟环形队列测试~");
  9         //注意:有一个空的位置,实际最长为3
 10         CircleArrayQueue queue = new CircleArrayQueue(4);
 11         char key = ' ';//接收用户输入
 12         Scanner scanner = new Scanner(System.in);
 13         boolean loop = true;
 14
 15         //输出一个菜单
 16         while(loop) {
 17             System.out.println("s(show):显示队列");
 18             System.out.println("a(add):添加数据到队列");
 19             System.out.println("g(get):从队列中获取元素");
 20             System.out.println("h(head):查看队列头的数据");
 21             System.out.println("e(exit):退出程序");
 22             //接收键盘输入的字符串,并且取出它的第一个字符
 23             key = scanner.next().charAt(0);
 24             switch(key) {
 25             case 's':
 26                 queue.showQueue();
 27                 break;
 28             case 'a':
 29                 System.out.println("输入一个数:");
 30                 int value = scanner.nextInt();
 31                 queue.addQueue(value);
 32                 break;
 33             case 'g'://抛异常了,要捕获
 34                 try {
 35                     int res = queue.getQueue();
 36                     System.out.printf("取出的数据是%d\n",res);
 37                 } catch (Exception e) {
 38                     //对所捕获异常的处理
 39                     System.out.println(e.getMessage());
 40                 }
 41                 break;
 42             case 'h'://抛异常了,要捕获
 43                 try {
 44                     int head = queue.headQueue();
 45                     System.out.printf("队列头的数据是%d\n",head);
 46                 }catch (Exception e) {
 47                     //对所捕获异常的处理
 48                     System.out.println(e.getMessage());
 49                 }
 50                 break;
 51             case 'e':
 52                 scanner.close();
 53                 loop = false;
 54                 break;
 55             default:
 56                 break;
 57             }
 58         }
 59         System.out.println("程序退出");
 60     }
 61 }
 62
 63 //使用数组模拟环形队列编写一个CircleArrayQueue类
 64 class CircleArrayQueue {
 65     private int maxSize;//数组的最大容量
 66     //队列头:调整为指向队列的第一个元素,即arr[front],初始值设为0
 67     private int front;
 68     //队列尾:调整为指向队列的最后一个元素的后一个位置,并空出一个空间作为约定,初始值为设为0
 69     private int rear;
 70     private int[] arr;//用于存放数据
 71
 72     //创建队列的构造器
 73     public CircleArrayQueue(int arrMaxSize) {
 74         maxSize = arrMaxSize;
 75         arr = new int[maxSize];
 76     }
 77
 78     //判断队列是否为空
 79     public boolean isEmpty(){
 80         return front == rear;
 81     }
 82
 83     //判断队列是否满
 84     public boolean isFull(){
 85         return (rear + 1) % maxSize == front;
 86     }
 87
 88     //添加数据到队列
 89     public void addQueue(int value) {
 90         //判断是否满
 91         if(isFull()) {
 92             System.out.println("队列满,不能加入数据");
 93             return;
 94         }
 95         arr[rear] = value; //rear指向最后一个元素的后一个位置,所以直接添加
 96         rear = (rear + 1) % maxSize; //考虑环形,取模
 97     }
 98
 99     //获取队列的数据,出队列
100     public int getQueue() {
101         //判空
102         if(isEmpty()) {
103             //抛出异常
104             throw new RuntimeException("队列空,不能取数据");
105         }
106         /**
107          * front 指向队列的第一个元素
108          * 1、先把front对应的值保留到一个临时变量
109          * 2、将front后移,考虑取模
110          * 3、将临时保存的变量返回
111          */
112         int value = arr[front];
113         front = (front + 1) % maxSize;
114         return value;
115     }
116     //显示队列所有数据
117     public void showQueue(){
118         //判空
119         if(isEmpty()){
120             System.out.println("队列空,没有可显示的数据");
121             return;
122         }
123         //注意:从front开始遍历,遍历多少个元素:元素个数怎么求?
124         for(int i = front;i < front + size();i++) {
125             System.out.printf("arr[%d] = %d\n",i % maxSize,arr[i % maxSize]);
126         }
127     }
128
129     //求当前队列有效数据的个数
130     public int size(){
131         return (rear + maxSize - front) % maxSize;
132     }
133
134     //显示队列的头数据,注意不是取出
135     public int headQueue(){
136         //判空
137         if(isEmpty()) {
138             throw new RuntimeException("队列空,没有可取的头数据");
139         }
140         //注意:front指向的是队列头的数据,计算front时已经做了取模的动作,front即为正确的位置。
141         return arr[front];
142     }
143 }
View Code

以上

12-21 01:31