【数据结构与算法】（JAVA版）队列，使用普通数组模拟队列（应用场景：银行预约叫号系统），数组模拟环形队列

内容非常详细，不懂请耐性看完，关键步骤都有注释

队列Queue

普通数组模拟队列

/**

• 队列应用场景：银行预约叫号系统
• 队列是一个有序列表，可以用数组或是链表来实现。
• 本代码使用数组模拟队列
• 基本实现思想：
• 当添加数据时，front不动，rear随着数据走
• 当取出数据时，rear不动，front随着数据走
• 出现问题：
• 如：

•  当列表中添加了3个元素之后，再向队列中将全部元素取出（方法是getQueue()）之后。
  

•  再向列表中添加数据就添加不了了
  

• 为了解决这一问题，特此采用环形队列来处理
• */

package dataStructure;
import java.util.Scanner;
public class Queue {
	public static void main(String[] args) {
		ArrayQueue arrayQueue = new ArrayQueue(3);
		char key = ' ';//接收用户输入
		Scanner sc = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("d(display):显示队列");
			System.out.println("a(add):添加数据到队列");
			System.out.println("e(exit):退出程序");
			System.out.println("g(get):从队列中取出数据");
			System.out.println("p(peek):查看队列头数据");
			key = sc.next().charAt(0);
			switch(key) {
				case 'a':
					System.out.println("输入一个数");
					int e = sc.nextInt();
					arrayQueue.addQueue(e);
					break;
				case 'd':
					arrayQueue.display();;
					break;
				case 'g':
					try {//如果方法getQueue没有抛出异常
						int res = arrayQueue.getQueue();
						System.out.printf("取出的数据是%d\n",res);
					}catch(Exception E) {//如果抛出异常
						System.out.println(E.getMessage());
					}
					break;
				case 'p':
					try {
						int res = arrayQueue.peekQueue();
						System.out.printf("队列头的数据是%d\n",res);
					}catch(Exception E) {
						System.out.println(E.getMessage());
					}
					break;
				case 'e':
					sc.close();
					loop = false;
					break;
				default:
					break;
			}	
		}
		System.out.println("程序退出");
	}
}
class ArrayQueue{
	private int maxSize;//表示数组的最大容量
	private int front;//对列头
	private int rear;//对列尾
	private int[] array;//模拟队列的数组
	//初始化构造器
	public ArrayQueue(int arrmaxSize){
		maxSize = arrmaxSize;
		front = -1;//队列头，front指向队列头的前一个位置
		rear = -1;//队列尾，指向队列尾的数据（即就是队列最后一个数据）
		array = new int[arrmaxSize];
	}
	//判空操作
	public boolean isEmpty() {
		return front == rear;
	}
	//判断队列是否已满
	public boolean isFull() {
		return rear == maxSize - 1;
	}
	//向队列添加数据
	public void addQueue(int e) {
		if(isFull()) {
			System.out.println("队列已满~~");
			return;
		}
		rear++;
		array[rear] = e;
	}
	//元素出队
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中没有元素");
			//这里不用写return，因为异常抛出后自动结束本次方法调用
		}
		return array[++front];
	}
	//显示队列中所有元素
	public void display() {
		if(isEmpty()) {
			System.out.println("d队列中没有元素");
			return;
		}
		for(int i = 0;i < array.length;i++) {
			System.out.printf("array[%d]=%d\n",i,array[i]);
		}
	}
	//查看队列第一个元素
	public int peekQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中没有元素");
		}
		return array[front + 1]; 
	}
}

数组模拟环形队列

/**

• 思路如下:
  1. front变量的含义做一个调整: front 就指向队列的第一个元素 也就是说array[front]就是队列的第一个元素front的初始值=0
  2. rear变量的含义做一个调整: rear指向队列的最后一个元素的后一个位置.因为希望空出一个空间做为约定.rear的初始值=0
     3.当队列满时，条件是(rear +1) %maxSize== front [满]
     4.对队列为空的条件，rear= front
     5.当我们这样分析，队列中有效的数据的个数(rear+ maxSize - front)% maxsize
• */

package dataStructure;
import java.util.Scanner;
public class CircularQueue {
	public static void main(String[] args) {
		CircularArray arrayQueue = new CircularArray(3);
		char key = ' ';//接收用户输入
		Scanner sc = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("d(display):显示队列");
			System.out.println("a(add):添加数据到队列");
			System.out.println("e(exit):退出程序");
			System.out.println("g(get):从队列中取出数据");
			System.out.println("p(peek):查看队列头数据");
			System.out.println("请输入对应功能的字符");
			key = sc.next().charAt(0);
			switch(key) {
				case 'a':
					System.out.println("输入一个数");
					int e = sc.nextInt();
					arrayQueue.addQueue(e);
					break;
				case 'd':
					arrayQueue.display();;
					break;
				case 'g':
					try {//如果方法getQueue没有抛出异常
						int res = arrayQueue.getQueue();
						System.out.printf("取出的数据是%d\n",res);
					}catch(Exception E) {//如果抛出异常
						System.out.println(E.getMessage());
					}
					break;
				case 'p':
					try {
						int res = arrayQueue.peekQueue();
						System.out.printf("队列头的数据是%d\n",res);
					}catch(Exception E) {
						System.out.println(E.getMessage());
					}
					break;
				case 'e':
					sc.close();
					loop = false;
					break;
				default:
					break;
			}
				
		}
		System.out.println("程序退出");
	}
}
class CircularArray{
	private int maxSize;//表示数组的最大容量
	private int front;
	private int rear;
	private int[] array;//模拟队列的数组
	//初始化构造器
	public CircularArray(int arrmaxSize){
		maxSize = arrmaxSize;
		array = new int[arrmaxSize];
	}
	//判空操作
	public boolean isEmpty() {
		return front == rear;
	}
	//判断队列是否已满
	public boolean isFull() {
		return (rear+1) % maxSize == front;
	}
	//向队列添加数据
	public void addQueue(int e) {
		if(isFull()) {
			System.out.println("队列已满~~");
			return;
		}
		//直接将数据加入
		array[rear] = e;
		//rear后移一位,这里必须考虑取模
		rear = (rear+1) % maxSize;
	}
	//元素出队
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中没有元素");
			//这里不用写return，因为异常抛出后自动结束本次方法调用
		}
		//这里需要分析front是指向队列的第一个元素
		//1.先把front对应的值保留到一个临时变量
		//2.将front后移，考虑取模
		//3.将临时保存的变量返回
		int value = array[front];
		front = (front+1) % maxSize;
		return value;
	}
	//显示队列中的所有数据
	public void display() {
		if(isEmpty()) {
			System.out.println("d队列中没有元素");
			return;
		}
		//从front开始遍历，再算出有效数据个数
		for(int i = front;i < front + size();i++) {
			System.out.printf("array[%d]=%d\n", i % maxSize,array[i%maxSize]);
		}
	}
	//求出当前队列有效数据个数
	public int size() {
		return (rear + maxSize - front) % maxSize;
	}
	//显示队列的第一个元素，不是取出是查看
	public int peekQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中没有元素");
		}
		return array[front]; 
	}
	
}