数组模拟队列

数组模拟队列

队列的存储结构

队列是计算机中常见的数据结构，是一种操作受限的线性表。从尾部（front）进入，头部（rear）弹出，典型的先进后出式存储。

队列的分类

队列分为两种：
单向队列：只能在队列头部删除数据，队列尾部插入数据。
双向队列：两端都可以进行插入数据和删除数据操作。
我这重点讲单向队列。

数组模拟队列（普通版，没有实现环形结构）

public class Test01 {
	public static void main(String[] args) {
		// 创建一个队列
		ArrayQueue arrayQueue = new ArrayQueue(3);
		char key = ' ';// 接受用户输入
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		// 输出一个菜单
		while (loop) {
			System.out.println("s(show)显示队列");
			System.out.println("a(add)添加数据");
			System.out.println("g(get)取出数据");
			System.out.println("e(exit)退出");
			System.out.println("h(head)查看队列头的数据");
			System.out.println("l(list)遍历数组");
			key = scanner.next().charAt(0);
			switch (key) {
			case 's':
				try {
					arrayQueue.showQueue();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'a':
				try {
					arrayQueue.addQueue(scanner.nextInt());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'g':
				try {
					int queue = arrayQueue.getQueue();
					System.out.println(queue);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				loop = false;
				scanner.close();
				break;
			case 'h':
				try {
					int showHead = arrayQueue.showHead();
					System.out.println(showHead);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'l':
				arrayQueue.arrList();
				break;
			default:
				System.out.println("输入错误");
				break;
			}
		}
	}
}

// 使用数组模拟队列
class ArrayQueue {
	// 表示数组最大容量
	private int maxSize;
	// 队列的头
	private int front;
	// 队列尾
	private int rear;
	// 用于存储数据，模拟队列
	private int[] arr;

	// 创建队列的构造器
	public ArrayQueue(int arrMaxSize) {
		// 最大长度
		maxSize = arrMaxSize;
		// 创建数组
		arr = new int[maxSize];
		// 队列都与队列尾的初始参数
		// 队尾
		rear = -1;
		// 队列头，
		front = -1;
	}

	// 判断是否已满
	public boolean isFull() {
		return rear == maxSize - 1;
	}

	// 判断是否为空
	public boolean isEmpty() {
		return rear == front;
	}

	// 添加数据到队列
	public void addQueue(int a) {
		// 判断数列是否已满
		if (isFull()) {
			throw new RuntimeException("队列已满");
		}
		rear++;
		arr[rear] = a;
		System.out.println(arr[rear]);
	}

	// 取出队列数据
	public int getQueue() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		front++;
		int date = arr[front];
		arr[front] = 0;
		return date;
	}

	// 查看队列所有数据
	public void showQueue() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		// 遍历数组
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// 查看队列头
	public int showHead() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		return arr[front + 1];
	}

	// 查询数组
	public void arrList() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}

数组模拟队列（实现环形结构）

//约定空一个空位空出来，总是在front前面一个位置是空的，因为：
//return (rear+1) % maxSize == front;这个非空判断语句
//如果不将rear加一的话，rear从一开始就和front相等了
//参考的是韩老师的教程
public class Test02 {
	public static void main(String[] args) {
		// 创建一个队列
		CircularArrayQueue circularArrayQueue = new CircularArrayQueue(4);
		char key = ' ';// 接受用户输入
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		// 输出一个菜单
		while (loop) {
			System.out.println("s(show)显示队列");
			System.out.println("a(add)添加数据");
			System.out.println("g(get)取出数据");
			System.out.println("e(exit)退出");
			System.out.println("h(head)查看队列头的数据");
			System.out.println("l(list)遍历数组");
			key = scanner.next().charAt(0);
			switch (key) {
			case 's':
				try {
					circularArrayQueue.showQueue();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'a':
				try {
					circularArrayQueue.addQueue(scanner.nextInt());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'g':
				try {
					int queue = circularArrayQueue.getQueue();
					System.out.println(queue);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				loop = false;
				scanner.close();
				break;
			case 'h':
				try {
					int showHead = circularArrayQueue.showHead();
					System.out.println(showHead);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'l':
				circularArrayQueue.arrList();
				break;
			default:
				System.out.println("输入错误");
				break;
			}
		}
	}
}

// 使用数组模拟队列
class CircularArrayQueue {
	// 表示数组最大容量
	private int maxSize;
	// 队列的头,初始化为0
	private int front;
	// 队列尾，初始化为0
	private int rear;
	// 用于存储数据，模拟队列
	private int[] arr;

	// 创建队列的构造器
	public CircularArrayQueue(int arrMaxSize) {
		// 最大长度
		maxSize = arrMaxSize;
		// 创建数组
		arr = new int[maxSize];
	}

	// 判断是否已满,要考虑到环形队列
	public boolean isFull() {
		// 将队列头下标加1取模，判断是否和队列尾下标相等
		return (rear + 1) % maxSize == front;
	}

	// 判断是否为空
	public boolean isEmpty() {
		return rear == front;
	}

	// 添加数据到队列
	public void addQueue(int a) {
		// 判断数列是否已满
		if (isFull()) {
			throw new RuntimeException("队列已满");
		}
		arr[rear] = a;
		System.out.println(arr[rear]);
		// 要考虑到环形，不能直接进行rear++
		// 因为队列头有数据被取出的话，
		// 数组前面就会有空余的位置
		// rear必须要由最后一位指向数组的第一位下标为0的位置去。
		rear = (rear + 1) % maxSize;
	}

	// 取出队列数据
	public int getQueue() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		int date = arr[front];
		arr[front] = 0;
		// 同上以免数组下标界和能循环取值
		front = (front + 1) % maxSize;
		return date;
	}

	// 查看队列所有数据
	public void showQueue() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		// 遍历数组，从front开始遍历
		//(i)%maxSize,避免下标越界，与取值不正确
		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 showHead() {
		// 判断队列是否为空
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		return arr[front];
	}

	// 查询数组
	public void arrList() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}

输出结果

s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
s
队列为空
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
a
1
1
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
a
2
2
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
a
3
3
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
a
4
队列已满
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
s
1 2 3 
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
l
1 2 3 0 
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
g
1
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
s
2 3 
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
a
6
6
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
s
2 3 6 
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组
l
0 2 3 6 
s(show)显示队列
a(add)添加数据
g(get)取出数据
e(exit)退出
h(head)查看队列头的数据
l(list)遍历数组

本文地址：https://blog.csdn.net/qq_49249150/article/details/107900005