队列的介绍和使用（用数组实现队列操作实例）

队列简介

        队列宛如一条不允许逆行的单行隧道，车辆(数据)只允许从隧道(队列)的入口(队尾)进入，从隧道(队列)的出口(队头)出来。
        那么可以看出：队列是有个有序列表，并且队列中的数据只能先入先出。队列这种线性数据结构，可以使用数组实现，也可以使用链表来实现。

队列的基本操作

1.入队
  入队就是把新元素添加到队尾的操作，放入一个元素，队尾也相应的向后会移动一个位置。
2.出队
  出队就是把元素从队头移出队列的操作，移出一个元素，队头也相应的向后会移动一个位置。 

使用数组实现队列

分析

1.通过数组实现队列，创建队列时候需要知道数组大小，来确定该队列的最大容量。
2.需要通过一个变量来记录队尾，确定每次插入数据(入队)的位置。
3.需要通过一个变量来记录对头，确定每次取出数据(出队)的位置。
4.当队列是空队列的时候，不能出队。空队列条件：队头标记变量 = 队尾标记变量。
5.当队列是满队列的时候，不能入队，满队列条件：队尾标记变量 = 实现队列的数组长度。 

代码实现

/**
 * 数组模拟简单队列
 */ class ArrayQueue{ int queueSize = 0;//队列的大小 int front = 0;//记录队头 int rear = 0;//记录队尾 int[] queue;//模拟队列的数组 /**
     * 构造方法 初始化队列
     *      
     * @param queueSize 队列大小
     */ public ArrayQueue(int queueSize){ this.queueSize = queueSize; queue = new int[queueSize]; front = 0; rear = 0; } /**
     * 判断队列是否已满
     * @return  true 表示已满
     */ public boolean isFull(){ return rear == queueSize; } /**
     * 判断队列是否为空
     * @return  true : 表示为空
     */ public boolean isEmpty(){ return rear == front; } /**
     * 给队列添加数据
     * @param num
     */ public void addQueue(int num){ //判断队列是否已满，如果已满 则无法添加数据 if(isFull()){ System.out.println("队列已满，无法添加数据"); return; } queue[rear] = num; rear++; } /**
     * 从队列中取值
     * @return
     */ public int getQueue(){ //判断队列是否为空 为空不能取值 if(isEmpty()){ throw new RuntimeException("队列空，不能取数据"); } int value = queue[front]; front++; return value; } /**
     * 显示队列中的数据
     */ public void showQueue(){ //判断队列是否为空 为空不能取值 if(isEmpty()){ System.out.println("队列为空，没有数据"); return; } for (int i = front; i < rear; i++){ System.out.println(queue[i]); } } /**
     * 显示队列的头数据
     * @return
     */ public int headQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空，没有数据..."); } return queue[front]; } } 

import java.util.Scanner; /**
 * 操作数组模拟的简单队列
 */ public class ArrayQueueDemo { public static void main(String[] args) { //创建队列 ArrayQueue arrayQueue = new ArrayQueue(10); //创建Scanner对象 用以获取用户输入 Scanner scanner = new Scanner(System.in); //标志位： 标记程序是否退出 boolean loop = true; char key; while (loop){ /*
             * 队列菜单
             */ System.out.println("s(show):显示队列"); System.out.println("a(add):添加数据"); System.out.println("g(get):获取数据"); System.out.println("h(head):查看队列头数据"); System.out.println("e(exit):退出程序"); //获取用户输入的第一个字符 key = scanner.next().charAt(0); switch (key){//根据字符做出相应操作 case 's': arrayQueue.showQueue();//显示队列数据 break; case 'a': System.out.println("请输入需要添加的数："); int num = scanner.nextInt();//获取键盘输入数据 arrayQueue.addQueue(num);//入队 break; case 'g': try { num = arrayQueue.getQueue();//出队 System.out.println("从队列中取出： " + num); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'h': try { num = arrayQueue.headQueue();//获取队头数据 System.out.println("队列头的数据："+num); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': loop = false; scanner.close(); System.out.println("退出程序~"); break; } } } } 

存在问题：当不断出队时，队头左边的空间得不到充分利用，导致队列容量越来越小。
问题解决：通过数组实现循环队列来充分利用空间，当记录队尾的变量到达数组长度时，查看记录队头的变量是不是在数组起始位置。若不是，则队尾从数组的起始位置开始存值，并且后移。

循环队列的实现

如上图，就可以实现队列的循环，从而达到队列空间的充分利用。

循环队列分析

1.通过数组实现队列，创建队列时候需要知道数组大小，来确定该队列的最大容量。
2.需要通过一个变量来记录队尾，确定每次插入数据(入队)的位置。
3.需要通过一个变量来记录对头，确定每次取出数据(出队)的位置。
4.当队列是空队列的时候，不能出队。空队列条件：队头标记变量 = 队尾标记变量。
5.当队列是满队列的时候，不能入队，满队列条件：(记录队尾的变量 + 1) % 数组长度 = 记录队头的变量。
6.队列中存在的有效数据个数为： (记录队尾的变量 + 数组长度 – 记录队头的变量) % 数组长度
7.记录队尾的变量的位置永远是空位，所以队列最大容量比数组长度小1. 

代码实现

/**
 *数组模拟循环队列
 */ class CircleArrayQueue{ int querySize = 0; int front = 0; int rear = 0; int[] query; /**
     * 构造方法 初始化循环队列
     * @param querySize
     */ public CircleArrayQueue(int querySize){ this.querySize = querySize; query = new int[querySize]; front = 0; rear = 0; } /**
     * 判断是否为空队列
     * @return ture :空
     */ public boolean isEmpty(){ return rear == front;//当队尾和队头相等时，表明为空队列 } /**
     * 判断是否为满队列
     * @return  true：满
     */ public boolean isFull(){ return (rear + 1) % querySize == front;//表明队尾和队头相邻 且队尾在左，队头在右 } public void addQueue(int num){ if (isFull()){//满队列 System.out.println("队列已满 无法加入数据"); return; } query[rear] = num; rear = (rear + 1) % querySize; } public int getQueue(){ if (isEmpty()){ throw new RuntimeException("为空，不能取值"); } int value = query[front]; front = (front + 1) % querySize; return value; } public void showQueue(){ if (isEmpty()){ System.out.println("为空，不能遍历"); } for (int i = front; i < front + (rear + querySize - front) %querySize; i++){ System.out.println(query[i]); } } } 

 import java.util.Scanner; /**
 *  操作数组模拟的循环队列
 */ public class CircleArrayQueueDemo { public static void main(String[] args) { CircleArrayQueue arrayQueue = new CircleArrayQueue(3); Scanner scanner = new Scanner(System.in); boolean loop = true; char key; while (loop){ System.out.println("s(show):显示队列"); System.out.println("a(add):添加数据"); System.out.println("g(get):获取数据"); System.out.println("e(exit):退出程序"); key = scanner.next().charAt(0); switch (key){ case 's': arrayQueue.showQueue(); break; case 'a': System.out.println("请输入需要添加的数："); int num = scanner.nextInt(); arrayQueue.addQueue(num); break; case 'g': try { num = arrayQueue.getQueue(); System.out.println("从队列中取出： " + num); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e': loop = false; scanner.close(); break; } } } } 

本文地址：https://blog.csdn.net/Rong_zhe/article/details/108022519