队列

队列在生活中的应用场景:排队区号,银行柜台服务

队列的特点:

  1. 先进先出,可以理解为从一头进入,从一头出来

使用普通数组方式实现队列步骤

  1. 初始化一个数值
  2. 定义两个指针,分别指向队列的第一个元素和最后一个元素
  3. 两个指针的值都是-1,front,real
  4. 应该编写的方法
    1. 遍历队列(从队列的头部数据一直遍历到队列的尾部,中间可能需要使用中间变量)
    2. 判断队列是否满(如果real == front)
    3. 判断队列是否为空(real == -1)
    4. 向队列里面添加数据
    5. 取出队列中的头部数据(取出front对应的数据)

图示

环形队列

代码(我一开始的思路和这个思路不一样,但是依然可以实现)

package cn.rlfit.queue;

import java.util.Scanner;

public class ArrayQueueDemo {
	static int queueMax;
	static int fast;
	static int end;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		使用数组模拟队列
		/*
		 * 思路分析:
		 * 1. 创建一个数组
		 * 2. 创建两个指针,指向数组的队首和队尾
		 * 3. 创建三个方法
		 * 	1. 向队列里面添加数据
		 * 	2. 取出队列里面的数据
		 * 	3. 遍历整个队列
		 */
		System.out.println("请输入初始化数组的大小");
		Scanner scanner = new Scanner(System.in);
		int orignol = scanner.nextInt();
		int[] queueArray = new int[orignol];
		queueMax = queueArray.length;
		fast = queueArray.length-1;
		end = queueArray.length-1;
		do {
			System.out.println("===============请输入=================\n1. 遍历\t2. 插入\t3. 取出\t4. 退出");
			int key = scanner.nextInt();
			switch (key) {
			case 1: {
				list(queueArray);
				break;
			}
			case 2:{
				addData(queueArray);
				break;
			}
			case 3:{
				removeData(queueArray);
				break;
			}
			case 4:{
				return;
			}
			default:
				System.out.println("请重新输入.......");
			}	
		}while(true);
	}
//	添加数据到队列
	public static void addData(int[] array) {
//		判断队列是否满
		if(fast<0) {
			System.out.println("队列已经满了");
			return;
		}
//		添加数据
		System.out.println("请输入添加的数据");
		Scanner scanner = new Scanner(System.in);
		int data = scanner.nextInt();
		array[fast--] = data;
		System.err.println("添加数据成功");
	}
//	取出数据
	public static void removeData(int[] array) {
//		判断队列中是否存在数据
		if(fast == end) {
			System.out.println("队列为空,不存在数据");
			return;
		}
//		取出数据
		System.out.println("取出的数据为:"+array[end--]);
	}
//	遍历队列
	public static void list(int[] array) {
		if(fast == end) {
			System.out.println("队列为空,不存在数据");
			return;
		}
		int temp = fast;
		for(int i = temp+1;i<=end;i++) {
			System.out.println("队列中总共有"+(end-fast)+"个数据第"+i+"个数据为:"+array[i]);
		}
	}
}

环形队列

从上面的队列中也可以看出,一般的队列存在的问题,队列只能使用一次,无法二次使用,所以我们需要一种方法,让队列可以重复只用,这里就出现了环形队列

数组模拟环形队列的实现方式

//	数组模拟环形队列
	/*
	 * 思路1:
	 * 	1. front变量的含义做一个调整:front变量指向队列的第一个元素,队列的一个元素的初始值为0
	 * 	2. real变量的含义做一个调整:real变量指向队列最后一个位置,但是这个位置不添加元素,预留出一个空间,判断队列满
	 * 	3. 当队列满的时候(real+1)%maxSize == front
	 * 	4. 当队列为空的时候real == front
	 * 	5. 队列中的有效数据为:front+(real + maxSize - front)%maxSize
	 * 添加数据是从第一个位置开始添加数据
	 */

这里有一个不好理解的地方,就是空出来的那个位置,实际上也不能说事空出来的,因为这个空位是随时变化 的,原来空出来的位置也会被添加数据,real指针一直都是指向那个空位的,但是当我们在添加数据的时候判断是否满的时候要先判断才能向里面添加数据,所以如果(real+1)%maxSize == front的时候就不能向real指向的那个空位添加数据,这个时候相当于real指向的位置是空出来的,如果不满足上述的条件,那么将会添加数据到那个空位,而real将会指向下面一个空位,所以就可理解成一直空出来一个位置。

环形队列代码实现

package cn.rlfit.queue;

import java.util.Scanner;

public class CircleArrayQueue {
//	数组模拟环形队列
	/*
	 * 思路1:
	 * 	1. front变量的含义做一个调整:front变量指向队列的第一个元素,队列的一个元素的初始值为0
	 * 	2. real变量的含义做一个调整:real变量指向队列最后一个位置,但是这个位置不添加元素,预留出一个空间,判断队列满
	 * 	3. 当队列满的时候(real+1)%maxSize == front
	 * 	4. 当队列为空的时候real == front
	 * 	5. 队列中的有效数据为:front+(real + maxSize - front)%maxSize
	 * 添加数据是从第一个位置开始添加数据
	 */
	public static void main(String[] args) {
		System.out.println("请输入初始化数组的大小");
		Scanner scanner = new Scanner(System.in);
		int orignol = scanner.nextInt();
		Queue queue = new Queue(orignol);
		do {
			System.out.println("===============请输入=================\n1. 遍历\t2. 插入\t3. 取出\t4. 退出");
			int key = scanner.nextInt();
			switch (key) {
			case 1: {
				queue.list();
				break;
			}
			case 2:{
				System.out.println("请输入添加的数据");
				int value = scanner.nextInt();
				queue.addDta(value);
				break;
			}
			case 3:{
				queue.remove();
				break;
			}
			case 4:{
				return;
			}
			default:
				System.out.println("请重新输入.......");
			}	
		}while(true);
	}
}
class Queue{
	int maxSize;
	int front = 0;
	int real = 0;
	int[] queueArray;
//	初始化数组
	
	public Queue(int maxSize) {
		this.maxSize = maxSize;
		queueArray = new int[maxSize];
	}
//	判断队列是否为空
	public boolean isEmpty() {
		if(real == front) {
			System.out.println("队列为空,不存在数据");
			return true;
		}
		return false;
	}
//	判断队列是否满
	public boolean isFull() {
		if((real+1)%maxSize == front) {
			System.out.println("队列已经满了");
			return true;
		}
		return false;
	}
//	遍历队列中的元素,用一个中间值记录遍历的数据,从头部开始遍历数据,但是real可能会在front的前面,所以遍历队列的时候
//	如果遍历到尾部
	public void list() {
		if(isEmpty()) {
			return;
		}
		for(int i =front;i<front+(real + maxSize - front)%maxSize;i++) {
			System.out.println("第"+i+"个元素的下标为"+i%maxSize+"值为"+queueArray[i%maxSize]);
		}
	}
//	向队列中添加数据
	public void addDta(int data) {
		if(isFull()) {
			return;
		}
		queueArray[real] = data;
		real = (real+1)%maxSize;
	}
//	取出队列中的头部数据
	public void remove() {
		if(isEmpty()) {
			return;
		}
		System.err.println("队列的头部数据为"+queueArray[front]);
		front = (front+1)%maxSize;
	}
}