欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

数组模拟队列

程序员文章站 2022-07-03 14:57:01
数据结构算法之——数组模拟队列（以实现环形结构）队列的存储结构队列是计算机中常见的数据结构，是一种操作受限的线性表。从尾部（front）进入，头部（rear）弹出，典型的先进后出式存储。队列的分类队列分为两种：单向队列：只能在队列头部删除数据，队列尾部插入数据。双向队列：两端都可以进行插入数据和删除数据操作。我这重点讲单向队列。数组模拟队列（普通版，没有实现环形结构）public class Test01 {public static void main(String[] args)...

数组模拟队列

队列的存储结构

队列是计算机中常见的数据结构，是一种操作受限的线性表。从尾部（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

相关标签： java 队列 数据结构 算法

上一篇： Vue+Cordova移动端Android最全教程

下一篇： Java面试不通过？这篇文章你看了吗？

推荐阅读