博客

1.1应用场景

银行排队：

1.2基本介绍

特点:

1. 队列是一个有序列表，可以用数组或是链表来实现。
2. 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
   
   示意图:
   
   
   
   解释:MaxSize-1：数组中下标从范围0~MaxSize-1
   
   front：指向队列中的首元素的前一个位置
   
   rear：指向队列中的尾元素
   
   最开始的时候没有存入元素就让front与rear都指向-1 表示不存储任何元素，因为数组的下标从0开始。当添加一个元素的时候（所谓的入队）就让rear先加1后存储，当删除一个元素的时候（所谓的出队）就让front移动一个位置(front始终指向头元素的前一个位置)

代码如下:

package com.atguigu.queue;

import java.util.Scanner;

public class aaa {

	public static void main(String[] args) {
		
		ArrayQueue1 queue = new ArrayQueue1(3);
		int key=0;//接收用户输入
		Scanner scanner = new Scanner(System.in);
		boolean flag=true;
		while(flag) {
			System.out.println("1.显示队列 , 2.退出程序 , 3.添加数据到队列(入队) ,4.从队列中取出数据(出队), 5.取对头元素");
			key = scanner.nextInt();
			switch (key) {
			case 1:
				queue.showQueue();
				break;
			case 2:
				scanner.close();
				flag=false;
				break;
			case 3:
				System.out.println("请输入一个数据，进行入队操作");
				int val = scanner.nextInt();
				queue.addQueue(val);
				break;
			case 4:
				try {
					int data = queue.getQueue();
					System.out.println("出队的数据是:"+data);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			
				break;
			case 5:
				try {
					int data1 = queue.headQueue();
					System.out.println("头数据是:"+data1);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			}
			
		}

	}

}

class ArrayQueue1{
	private int maxSize;//表示数组的最大容量
	private int front;//队列头
	private int rear;//队列尾
	private int[] arr;//存放数据的数组，用于模拟队列
	int count=0;
	
	public ArrayQueue1(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = -1;//指向队列头部 分析出front是指向队列头的前一个位置
		rear  = -1;//指向队列队尾,指向队列尾的数据(就是队列的最后一个数据)
		
	}
	
	//判断队列是否满
	public boolean isFull() {
		//队列满的情况是:rear==maxSize-1
		return rear == maxSize-1;
	}
	
	//判断队列是否为空
	public boolean isEmpty() {
		//队列为空的条件是 front==rear
		return front == rear ;
	}
	
	//入队
	public void addQueue(int data) {
		if(isFull()) {
			throw new RuntimeException("队列已经满，不能添加数据");
		}
		rear++;//让rear后移,后一个位置存储当前元素的值
		arr[rear] = data;
	}
	//出队
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中无数据");
		}
		front++;//front后移 返回出队的元素
		return arr[front];
	}
	//显示队列所有的数据
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("队列为空,无法显示数据");
			return;
		}
		//元素中的值是从front+1 dao rear (front+1是因为front指向的是队列首元素的前一个位置)
		for (int i=front+1; i <= rear; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	//显示队头数据
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，无法取出头部数据");
		}
		return arr[++front];
	}
}

	问题分析并优化
	 1) 目前数组使用一次就不能用， 没有达到复用的效果
	 2) 将这个数组使用算法，改进成一个环形的队列 取模：%

1.3环形队列

对前面的数组模拟队列的优化，充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可）		

分析说明：

1. 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize ==front
2. rear == front [空]
3. 分析示意图:
   
   
   
   可根据这个图进行模拟正常的数组不会有环形的 只是这样画图模拟更直观
   
   

package com.atguigu.queue;
import java.util.Scanner;

public class ArrCircleQueue {

	public static void main(String[] args) {
		
		CircleQueue queue = new CircleQueue(3);
		int key=0;//接收用户输入
		Scanner scanner = new Scanner(System.in);
		boolean flag=true;
		while(flag) {
			System.out.println("1.显示队列 , 2.退出程序 , 3.添加数据到队列(入队) ,4.从队列中取出数据(出队), 5.取对头元素");
			key = scanner.nextInt();
			switch (key) {
			case 1:
				queue.showQueue();
				break;
			case 2:
				scanner.close();
				flag=false;
				break;
			case 3:
				System.out.println("请输入一个数据，进行入队操作");
				int val = scanner.nextInt();
				queue.addQueue(val);
				break;
			case 4:
				try {
					int data = queue.getQueue();
					System.out.println("出队的数据是:"+data);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				
				break;
			case 5:
				try {
					int data1 = queue.headQueue();
					System.out.println("头数据是:"+data1);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			}
			
		}

	}
}

class CircleQueue{
	private int maxSize;//表示数组的最大容量
	private int front;//队列头
	private int rear;//队列尾
	private int[] arr;//存放数据的数组，用于模拟队列
	
	public CircleQueue(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = 0;//指向队列头部元素
		rear  = 0;//指向队列队尾后一个元素,
	}
	
	//判断队列是否满
	public boolean isFull() {
		return (rear+1)%maxSize==front;
	}
	
	//判断队列是否为空
	public boolean isEmpty() {
		return front == rear ;
	}
	
	//入队
	public void addQueue(int data) {
		if(isFull()) {
			System.out.println("队列已经满，不能添加数据");
			return ;
		}
		arr[rear] = data;
		//将 rear 后移, 这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}
	//出队
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列中无数据");
		}
		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;
	}
	//显示队列所有的数据
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("队列为空,无法显示数据");
			return;
		}
		
		for (int i=front; i < front+size(); i++) {
			System.out.print(arr[i%maxSize]+" ");
		}
		System.out.println();
	}
	// 求出当前队列有效数据的个数
		public int size() {
			return (rear + maxSize - front) % maxSize;   
		}
	//显示队头数据
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，无取出头部数据");
		}
		return arr[front];
	}
}