本文共 5460 字，大约阅读时间需要 18 分钟。

什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

那么我们如何实现队列呢？

数组：

具体实现：

（1）首先这个队列一定得有队头（front）和队尾（rear）、maxSize（队列大小）

（2）front初始值为-1，指向队列头部，分析出front是指向队列头的前一个位置

（3）rear初始值为-1，指向队列尾部，指向队列尾部的数据（就是队列最后一个数据）

（4）队列满的条件是：rear = maxSize - 1

（5）队列为空的条件是：rear = front

代码实现：

package com.zcx;import java.util.Scanner;/** * @author Kesrn *	用数组实现队列 */public class ArrayQueueDemo {	public static void main(String[] args) {		ArrayQueue arrayQueue =new ArrayQueue(3);		char key = ' ';		Scanner s = new Scanner(System.in);		boolean flag=true;				while(flag) {			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 = s.next().charAt(0);//接收一个字符						switch (key) {			case 's':				arrayQueue.showQueue();				break;			case 'e':				s.close();				flag = false;				break;			case 'a':				System.out.println("输入一个数");				int value = s.nextInt();				arrayQueue.addQueue(value);				break;			case 'g':				try {					int res = arrayQueue.getQueue();					System.out.printf("取出来的数据是%d\n",res);				} catch (Exception e) {					System.out.println(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;			default:				break;			}		}		System.out.println("退出程序");	}}class ArrayQueue{	private int maxSize;//队列大小	private int front;//队列头	private int rear;//队列尾	private int[] arr;//模拟队列			//构造器	public ArrayQueue(int maxSize) {		this.maxSize = maxSize;		this.front = -1;//指向队列头部，分析出front是指向队列头的前一个位置		this.rear = -1;//指向队列尾部，指向队列尾部的数据（就是队列最后一个数据）		this.arr = new int[maxSize];	}		//判断队列是否满	public boolean isFull() {		return rear == maxSize - 1;	}		//判断队列是否为空	public boolean isEmpty() {		return rear == front;	}		//添加数据到队列	public void addQueue(int n) {		//判断队列是否满		if(isFull()) {			System.out.println("队列已满，不能加入数据~");			return;		}		rear++;//让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 = 0; i < arr.length; i++) {			System.out.printf("arr[%d]=%d\n",i,arr[i]);		}	}	//显示队列头部数据	public int headQueue() {		//判断队列是否为空		if(isEmpty()) {			throw new RuntimeException("当前队列为空");		}		return arr[front+1];			}}

实现之后我们发现，这个队列是一次性产品，也就是说在你插入数据到队列中后，无法让这两个指向位置的变量被复用，这时候就需要引入一种叫做环形队列的数据结构：

图片借鉴自下面的文章

具体实现：

（1）对上面提到的front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值为0

（2）对上面提到的rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear = 0

（3）当队列满的条件为（rear+1）%maxSize = front[满]

（4）当队列为空的条件 rear == front

（5）队列中的有效数据的个数：（rear+maxSize-front）%maxSize

代码实现：

package com.zcx;import java.util.Scanner;public class CircleArrayQueue {	public static void main(String[] args) {		CircleArray arrayQueue =new CircleArray(3);		char key = ' ';		Scanner s = new Scanner(System.in);		boolean flag=true;				while(flag) {			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 = s.next().charAt(0);//接收一个字符						switch (key) {			case 's':				arrayQueue.showQueue();				break;			case 'e':				s.close();				flag = false;				break;			case 'a':				System.out.println("输入一个数");				int value = s.nextInt();				arrayQueue.addQueue(value);				break;			case 'g':				try {					int res = arrayQueue.getQueue();					System.out.printf("取出来的数据是%d\n",res);				} catch (Exception e) {					System.out.println(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;			default:				break;			}		}		System.out.println("退出程序");	}}class CircleArray{	private int maxSize;//队列大小	private int front;//队列头	private int rear;//队列尾	private int[] arr;//模拟队列		//构造器		public CircleArray(int maxSize) {			this.maxSize = maxSize;			this.front = 0;//指向队列头部，分析出front是指向队列头的前一个位置			this.rear = 0;//指向队列尾部，指向队列尾部的数据（就是队列最后一个数据）			this.arr = new int[maxSize];		}				//判断队列是否满		public boolean isFull() {			return (rear+1)%maxSize == front;		}				//判断队列是否为空		public boolean isEmpty() {			return rear == front;		}				//添加数据到队列		public void addQueue(int n) {			//判断队列是否满			if(isFull()) {				System.out.println("队列已满，不能加入数据~");				return;			}			arr[rear]=n;			rear = (rear+1) % maxSize;		}				//获取队列中的数据		public int getQueue() {			//判断队列是否为空			if(isEmpty()) {				throw new RuntimeException("当前队列为空");			}			//front是指向队列的第一个元素			// 1.先把front对应的值保留到一个临时变量 2.将front后移 3.将临时保存的变量返回			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.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);			}		}		//显示队列头部数据		public int headQueue() {			//判断队列是否为空			if(isEmpty()) {				throw new RuntimeException("当前队列为空");			}			return arr[front];				}				//求出当前队列的有效数据的个数		public int size() {			return (rear+maxSize-front)%maxSize;		}}

转载地址：http://exewi.baihongyu.com/