Java数组实现队列（queue）详解

一、队列简单介绍

队列是只允许在表的一端进行插入, 在另一端删除元素的线性表。
允许插入的一端称为队尾(rear)；
允许删除的一端称为队头(front)；
假设队列为 Q=(a1,a2,…,an),则a1是队头元素，an是队尾元素；
队列中的元素是按照a1,a2,…,an的顺序进入的，退出队列也只能按照这个次序依次退出；
当队列中没有元素时称为空队列；
队列是一种“先进先出”的线性表，简称FIFO表。

在这里插入图片描述

二、队列实现

队列有很多种，这里只是介绍最基本的实现，采用顺序存储结构，称为顺序队列，采用一维数组来存储队列中的每一元素，数组的上界表示队列的最大容量。另设两个指针front 和rear 。
约定：
队头指针front总是指向队头元素在队列中的当前位置；
队尾指针rear总是指示队尾元素的下一个位置。

想学习链表实现队列的看博主的其他文章。

1、创建队列

实现比较简单，先定义好队列的大小maxSize; 再定义好头与尾front, rear；最后定义存储数据的数组arr[]。

class ArrayQueue{
	
	private int maxSize;
	private int front;//头
	private int rear;//尾
	private int[] arr;
	//初始化
	public ArrayQueue(int arrmaxSize) {
		maxSize = arrmaxSize;
		arr = new int[maxSize];
		front = -1;
		rear = -1;
	}
	//判断队列满
	public boolean isFull() {
		return (rear+1) == maxSize;
	}
	//判断队列kong
	public boolean isEmpty() {
		return rear == front;
	}
	//添加数据
	public void addQueue(int n) {
		if(isFull()) {//判满
			System.out.println("队列满");
			return;
		}
		rear++;
		arr[rear] = n;
	}
	//出队列
	public int getQueue() {
		if(isEmpty()) {//判空
			throw new RuntimeException("队列空");
		}
		front++;
		return arr[front];
	}
	public void showQueue() {
		if(isEmpty()) {
			System.out.println("队列空");
			return;
		}
		for(int i = front; i < rear; i++) {
			System.out.printf("arr[%d] = %d\n",i,arr[i]);
		}
	}
	//显示队列头
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列空");
		}
		return arr[front+1];
	}
}

2、测试

使用switch语句分别测试代码的性能。

public static void main(String[] args) {
		// TODO 自动生成的方法存根
		ArrayQueue queue = new ArrayQueue(3);
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		while(loop) {
			System.out.println("s show: 显示队列");
			System.out.println("e exit: 退出程序");
			System.out.println("a add : 添加数据");
			System.out.println("g get : 取出数据");
			System.out.println("h head: 显示队头");
			key = scanner.next().charAt(0);
			switch (key) {
			case 's':
				queue.showQueue();
				break;
			case 'a':
				System.out.println("输入一个数");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case 'g':
				try {
					int res = queue.getQueue();
					System.out.printf("取出的数据：%d\n", res);
				}catch (Exception e) {
					System.out.printf(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = queue.headQueue();
					System.out.printf("队列头的数据：%d\n", res);
				}catch (Exception e) {
					System.out.printf(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;	
			}
		}
		System.out.printf("退出程序");
	}