您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

队列(图文)

第十三双眼睛2022-05-29【数据结构与算法】人已围观

简介队列

队列介绍
队列是一个有序列表，可以用数组或者链表来实现
遵循先进先出的原则，即先放入队列的数据，要先取出，后放入队列的数据，后取出。

先创建一个队列

package com.xingchen.day002;
public class ArrayQueue {

   // 队列最大容量
   private int maxSize;
   // 队列头
   private int front;
   // 队列尾
   private int rear;
   // 存储数据的数组
   private int[] arr;

   // 创建队列的构造器
   public ArrayQueue(int maxSize) {
       this.maxSize = maxSize;
       this.arr = new int[maxSize];
       this.front = -1;
       this.rear = -1;
   }

   // 判断队列是否满
   public boolean isFull() {
       return this.rear == this.maxSize - 1;
   }

   // 判断队列是否空
   public boolean isEmpty () {
       return this.front == this.rear;
   }

   // 添加数据到队列
   public void addQueue(int n) {
       if (isFull()) {
           System.out.println("队列已满,不能加入数据");
           return;
       }
       this.rear ++ ;
       this.arr[rear] = n;
   }

   // 获取队列的数据
   public int getQueue() {
       if (isEmpty()) {
           throw new RuntimeException("队列为空,无法取出数据");
       }
       this.front ++ ;
       return this.arr[this.front];
   }

   // 显示队列中的所有数据
   public void show () {
       // 遍历
       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()) {
           throw new RuntimeException("队列为空");
       }
       return arr[front+1];
   }
}

测试一下

package com.xingchen.day002;
import java.util.Scanner;
public class ArrayQueueDemo {
   public static void main(String[] args) {
       // 创建一个队列
       ArrayQueue queue = new ArrayQueue(3);
       Scanner scanner = new Scanner(System.in);
       char key = ' ';
       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':
               queue.show();
               break;
           case 'a':
               System.out.println("请输入数据");
               int value = scanner.nextInt();
               queue.addQueue(value);
               break;
           case 'g':
               try{
                   int res = queue.getQueue();
                   System.out.printf("取出的数据是:%d",res);
               }catch(Exception e){
                   System.out.println(e.getMessage());
               }
               break;
           case 'h':
               try{
                   int res = queue.headQueue();
                   System.out.printf("头部数据是:%d",res);
               }catch(Exception e) {
                   System.out.println(e.getMessage());
               }
               break;
           case 'e':
               scanner.close();
               loop = false;
               break;
           default:
               System.out.println("输入不正确,请重新输入");
               break;
           }
       }
       System.out.println("退出");
   }
}

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]=1
arr[1]=0
arr[2]=0
s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据
g
取出的数据是:1s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据
h
队列为空
s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据

目前的队列还有点问题,当队列中的数据长度达到最大值后，就不能再使用了，需要将队列做成可重复使用的
具体实现思路：
front变量的含义做一个调整：front指向队列的第一个元素,初始值为0
rear变量的含义也做一个调整：rear指向队列最后一个元素的后一个位置，希望空出一个空间做一个约定，初始值为0
当队列满时，条件是：(rear + 1)/ maxSize = front
当队列空时，条件是：当rear = front
队列中有效数据的个数是：(rear - front + maxSize ) / maxSize
再之前的代码上略做修改，就能得到环形队列

package com.xingchen.day002;
public class CircleQueue {
   // 队列最大容量
   private int maxSize;
   // 队列头
   private int front;
   // 队列尾
   private int rear;
   // 存储数据的数组
   private int[] arr;

   // 创建队列的构造器
   public CircleQueue(int maxSize) {
       this.maxSize = maxSize;
       this.arr = new int[maxSize];
   }

   // 判断队列是否满
   public boolean isFull() {
       return (this.rear + 1) % this.maxSize == front;
   }

   // 判断队列是否空
   public boolean isEmpty () {
       return this.front == this.rear;
   }

   // 添加数据到队列
   public void addQueue(int n) {
       if (isFull()) {
           System.out.println("队列已满,不能加入数据");
           return;
       }
       this.arr[rear] = n;
       this.rear = (this.rear) + 1 % maxSize;
   }

   // 获取队列的数据
   public int getQueue() {
       if (isEmpty()) {
           throw new RuntimeException("队列为空,无法取出数据");
       }
       // 先将front 保存
       // 将front 后移
       int value = arr[front];
       front = (front + 1) % maxSize;
       return value;
   }

   // 显示队列中的所有数据
   public void show () {
       // 遍历
       if (isEmpty()) {
           System.out.println("队列为空");
           return;
       }
       for (int i = front; i< front + size();i ++ ) {
           System.out.printf("arr[%d]=%d",i,arr[i % maxSize]);
       }
   }

   private int size () {
       return (rear - front + maxSize) % maxSize;
   }

   // 显示队列的头部数据
   public int headQueue() {
       if (isEmpty()) {
           throw new RuntimeException("队列为空");
       }
       return arr[front];
   }
}

测试一下

package com.xingchen.day002;
import java.util.Scanner;
public class CircleQueueDemo {
   public static void main(String[] args) {
       // 测试数组模拟环形队列
       // 创建一个队列
       CircleQueue queue = new CircleQueue(4);
       Scanner scanner = new Scanner(System.in);
       char key = ' ';
       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':
               queue.show();
               break;
           case 'a':
               System.out.println("请输入数据");
               int value = scanner.nextInt();
               queue.addQueue(value);
               break;
           case 'g':
               try{
                   int res = queue.getQueue();
                   System.out.printf("取出的数据是:%d",res);
               }catch(Exception e){
                   System.out.println(e.getMessage());
               }
               break;
           case 'h':
               try{
                   int res = queue.headQueue();
                   System.out.printf("头部数据是:%d",res);
               }catch(Exception e) {
                   System.out.println(e.getMessage());
               }
               break;
           case 'e':
               scanner.close();
               loop = false;
               break;
           default:
               System.out.println("输入不正确,请重新输入");
               break;
           }
       }
       System.out.println("退出");
   }
}

结果如下：

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]=1s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据
g
取出的数据是:1s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据
h
队列为空
s(show):显示队列数据
e(exit):退出
a(add):插入数据
g(get):获取队列数据
h(head):查看头部数据
e
退出

Tags：

很赞哦！ ()

上一篇：稀疏数组(图文)

下一篇：单链表(图文)