数据结构-简单数组模拟队列实现
程序员文章站
2022-07-14 12:30:38
...
列队
- 队列是一个有序的列表,可以用数组或是链表来实现
- 遵循先进先出的原则。
思路
- front 表示列头的前一个位置,初始值为 front = -1
- rear 表示列尾, 初始值为 rear = -1
- 当front == rear 表示队列为空
- 当rear = maxSize - 1 表示队列已满
- maxSize 表示队列的容量,maxSize - 1 表示数组最大的索引
代码实现
import java.util.Scanner;
public class ArrayQueueTest {
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("e(exit): 退出该程序");
System.out.println("a(add): 添加数据到队列");
System.out.println("g(get): 从队列中取出数据");
System.out.println("p(peek): 偷瞄列头数据");
// 接收用户输入的一个字符
key = scanner.next().charAt(0);
// 对应指令具体实现
switch (key) {
case 's':
arrayQueue.showQueue();
break;
case 'e':
scanner.close();
loop = false;
System.out.println("程序退出,exit(0)");
break;
case 'a':
System.out.println("请输入一个数据");
int data = scanner.nextInt();
arrayQueue.addQueue(data);
break;
case 'g':
System.out.printf("取出的数据为%d\n", arrayQueue.getQueue());
break;
case 'p':
System.out.printf("偷瞄的列头数据为%d\n", arrayQueue.peekQueue());
break;
}
}
}
}
/**
* 队列(简单使用数组模拟队列)
* 先进先出
* 有两个指针 一个头指针和一个尾指针(默认指向-1)
* 每次队列添加数据 尾指针会往后移动一位
* 每次队列取出数据 头指针也会往后移动一位
* 当头指针和尾指针相等时,队列为空
* 当尾指针等于队列的容量-1时(因为数组是以0开始),队列满
*/
class ArrayQueue {
// 队列最大的容量
private int MaxSize;
// 列头
private int front;
// 列尾
private int rear;
// 队列
private int[] queue;
// 创建队列
public ArrayQueue(int maxSize) {
this.MaxSize = maxSize;
queue = new int[this.MaxSize];
// 列头,指向队列头的前一个位置 约定
front = -1;
// 列尾,指向队列列尾的数据 约定
rear = -1;
}
// 队列是否满
public boolean isFull() {
return rear == MaxSize - 1;
}
// 队列是否空
public boolean isEmpty() {
return front == rear;
}
// 队列添加数据
public void addQueue(int data) {
if (isFull()) {
System.out.println("队列已满,无法添加数据");
return ;
}
rear++;
queue[rear] = data;
}
// 队列取出数据
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,无法取出数据");
}
front++;
return queue[front];
}
// 显示队列
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空,没有数据");
return ;
}
for (int i = 0; i < queue.length; i++) {
System.out.printf("queue[%d] = %d \n", i, queue[i]);
}
}
// 偷瞄列头
public int peekQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空,列头无数据");
}
return queue[front + 1];
}
}
结论
- 使用简单数组模拟队列实现
- 缺点
- 一次性队列
- 无法复用
- 优化
- 使用环形数组模拟队列
上一篇: 第一个项目开始问题的总结
下一篇: 第十五课:异常