数据结构-简单队列

1.简介

队列为一个有序列表，可以用数组或链表来实现。

先进先出原则。先存入队列的数据先取出，后存进队列的数据后取出。

这里对比一下，栈是后来者居上

下面使用数组来模拟队列，用数组的结构来存储队列的数据：

Queue中两个指针，front为队首，rear为队尾。maxSize是该队列的最大容量。当有数据加进来时，加到队尾，front没有变化，而rear在增加。当数据被取出，从对头取出，rear没有变化，而front在增加。front随数据输出而改变，rear随数据输入而改变。

怎么记呢？就是，现在你在军训排队，然后你来晚了迟到了，你这时候偷偷排到队尾去，队尾就后移了。然后教官是站在队伍前方的，他对着队伍说：出列！然后队头这个人就站出来了，队头这个位置就空出来了。

还可以就按超市排队结账，肯定是排在前面的人先结账，后面来的就在队尾排队，你排到了队尾，队就变长了，队尾就后移了。前面的队头的人结完账走了，队伍就变短了，队头也后移到了下一个人。

2.将数据加入队列思路：

数据加入队列，addQueue。入队处理有两个步骤：

将尾指针后移，rear+1。若队满了则不能加入数据。
若尾指针rear小于队列最大下标maxSize-1，则将数据存入rear指的这个数组元素中。否则就无法存入数据。

注：因为数组下标从0开始，队列容量maxSize，所以最大下标是maxSize-1。

3.从队列取出数据思路：

若数组为将头指针后移，front+1。若队为空则不能取出数据。

4.判断队列满和空：

当front==rear则队列为空

当rear==maxSize-1则队列满

5.将数据加入队列代码：

package com.xjj.queue;import java.nio.Buffer;
import java.util.Scanner;public class ArrayQueue {public static void main(String[] args) {//创建一个队列MyArrayQueue arrayQueue = new MyArrayQueue(3);//测试从控制台输入数据到队列char key = ' ';//接收用户输入Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {System.out.print("s(show)展示队列\t");System.out.print("e(exit)退出\t");System.out.print("a(add)添加数据\t");System.out.print("g(get)取出数据\t");System.out.print("h(head)查看队头数据\t\n");key = scanner.next().charAt(0);//接收一个字符switch (key) {case 's':arrayQueue.showQueue();break;case 'a':System.out.println("添加一个数据");try{int value = scanner.nextInt();//假如需要输入一个整数arrayQueue.addQueue(value);}catch (Exception e){System.out.println(e.getMessage());}break;case 'g':try {//这里用try catch是因为可能有异常抛出int res = arrayQueue.getQueue();System.out.printf("取出的数据为：%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());//这里的e.getMessage()就是方法里的异常消息}break;case 'h':try {int res = arrayQueue.headQueue();System.out.printf("队头数据为：%d\n",res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':scanner.close();//关闭输入loop=false;break;default:break;}}System.out.println("程序退出");}
}//用数组模拟队列
class MyArrayQueue {private int maxSize;//队列的最大容量private int front;//队列头private int rear;//队列尾private int[] QueueArr;//用于存放数据的数组，模拟队列//先创建队列的构造器public MyArrayQueue(int arrMaxSize) {maxSize = arrMaxSize;QueueArr = new int[maxSize];front = -1;//指向队列头部前一个位置。当还没有在队列中添加数据时指向队列头的前一个位置rear = -1;//指向队列尾部。指向队列尾部的数据（就是直接是队列最后一个数据）}//判断队列是否满public boolean isFull() {return rear == maxSize - 1;//如果尾指针直接在最大下标，不就是满了吗}//判断队列是否空public boolean isEmpty() {return rear == front;}//添加数据到队列public void addQueue(int n) {//先判断队列满没满，满了就加不了数据if (isFull()) {//抛出异常throw new RuntimeException("队满，无法加数据");}rear++;//rear后移一位就是加进去了QueueArr[rear] = n;//这个队尾位置就放这个数据}//从队列中取数据，出队列public int getQueue() {if (isEmpty()) {//抛出异常throw new RuntimeException("队空，无法取数据");}front++;//front后移一位就是队头，因为front本来是指向队头前一个位置，后移一位就正好指向队头了return QueueArr[front];//返回队头这个数据}//显示队列所有数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空，没有数据");return;}//遍历for (int i = 0; i < QueueArr.length; i++) {System.out.printf("QueueArr[%d]=%d\n", i, QueueArr[i]);}}//显示队列的队头数据public int headQueue() {//判断是否为空if (isEmpty()) {throw new RuntimeException("队列为空，没有数据");}//从队列头前一位指向队列头return QueueArr[front+1];}
}