随笔分类
队列
队列是一个有序列表,可以用数组或链表来实现
基于数组来模拟队列
对头front,随数据输出而改变
对尾rear,随数据的输入而改变
实现思路
存入一个数据
- 将尾指针rear往后移,当front == rear 时,队列为空
- 如果尾部指针rear 小于队列的最大下标 maxSize-1,则将数据存入rear所指的数组元素中,否则将无法存入数据
代码实现
public class ArrayQueueDemo {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(5);
char key = ' '; //接受用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出一个菜单
while (loop){
System.out.println("s:显示队列");
System.out.println("e:退出程序");
System.out.println("a:添加数据");
System.out.println("g:从队列中取数据");
System.out.println("h:查看当前队列头的数据");
key = scanner.next().charAt(0);//每次只接受一个数据
switch (key){
case 's':
arrayQueue.showQueue();
break;
case 'e':
scanner.close();
loop = false;
break;
case 'a':
System.out.println("添加一个数据");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
System.out.println(arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
System.out.println(arrayQueue.getQueueHead());
break;
default:
break;
}
}
}
}
/**
* 数组模拟队列
*/
class ArrayQueue{
private int maxSize;
private int front; //指向队列头的前一个位置
private int rear; //指向队列尾部,即有数据时指向的是队列的最后一个数据
private int[] arr;
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
front = -1;
rear = -1;
arr = new int[maxSize];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
return rear == maxSize-1;
}
// 添加数据
public void addQueue(int ele){
if (isFull())
System.out.println("队列已满,无法添加数据");
arr[++rear] = ele;
}
// 获取数据 对头出列
public int getQueue(){
if (isEmpty())
throw new RuntimeException("队列为空");
return arr[++front];
}
//遍历下队列
public void showQueue(){
if (isEmpty()){
System.out.println("队列为空,没有数据");
return;
}
for (int i = front+1;i<=rear;i++)
System.out.printf(arr[i]+" ");
System.out.println();
}
//显示队列头部数据
public int getQueueHead(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
return arr[front+1];
}
}
运行结果
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
58
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
1
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
68
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
26
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
s
58 1 68 26
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
g
58
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
g
1
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
h
68
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
h
68
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
e
Process finished with exit code 0
问题分析及其优化
- 目前数组使用一次就不能用了,没有达到复用的效果
- 将这个数组使用算法,改进成一个环形的队列 取模:%
数组模拟单向环形队列
一个实现思路如下
- front变量的含义做一个调整:front指向的是队列的第一个元素,也就是说arr[front] 就是第一个元素,默认值为0
- rear变量的含义也做一个调整:rear指向的是最后一个元素的后一个位置.希望留出一个空间作为约定,初始值为0 ;预留着的空间实在不断动态变化着的
- 队列为满条件:rear + 1 % maxSize = front
- 队列为空条件:rear = front
- 队列中有效元素个数:(rear + maxSize - front) % maxSize
- 经过这样改变,便可以得到一个环形队列(注意:因为留出了一个位置作为约定,所以队列的实际有效位置是 maxSize - 1)约定的位置也可以认为是队列第一个元素的前一个元素
代码实现
/**
*
*/
public class ArrayCircleQueueDemo {
public static void main(String[] args) {
ArrayCircleQueue arrayQueue = new ArrayCircleQueue(4); //留出了一个位置作为约定,队列有效数据最大是3
char key = ' '; //接受用户输入
Scanner scanner = new Scanner(System.in);
boolean loop = true;
//输出一个菜单
while (loop){
System.out.println("s:显示队列");
System.out.println("e:退出程序");
System.out.println("a:添加数据");
System.out.println("g:从队列中取数据");
System.out.println("h:查看当前队列头的数据");
key = scanner.next().charAt(0);//每次只接受一个数据
switch (key){
case 's':
arrayQueue.showQueue();
break;
case 'e':
scanner.close();
loop = false;
break;
case 'a':
System.out.println("添加一个数据");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
System.out.println(arrayQueue.getQueue());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
System.out.println(arrayQueue.getQueueHead());
break;
default:
break;
}
}
}
}
/**
* 数组模拟队列
*/
class ArrayCircleQueue{
private int maxSize;
private int front; //指向第一个元素
private int rear; //指向队列最后一个元素的后一个元素
private int[] arr;
public ArrayCircleQueue(int maxSize){
this.maxSize = maxSize;
front = 0;
rear = 0;
arr = new int[maxSize];
}
public boolean isEmpty(){
return front == rear;
}
public boolean isFull(){
return (rear+1) % maxSize == front;
}
// 添加数据
public void addQueue(int ele){
if (isFull()) {
System.out.println("队列已满,无法添加数据");
return;
}
arr[rear] = ele;
rear = (++rear) % maxSize;
}
public int size(){
return (rear + maxSize - front) % maxSize;
}
// 获取数据 对头出列
public int getQueue(){
if (isEmpty())
throw new RuntimeException("队列为空");
int res = arr[front];
front = (++front) % maxSize;
return res;
}
//遍历下队列
public void showQueue(){
if (isEmpty()){
System.out.println("队列为空,没有数据");
return;
}
// 从front开始遍历,有几个元素
for (int i = front;i < front + size();i++)
System.out.printf(arr[i % maxSize]+" ");
System.out.println();
}
//显示队列头部数据
public int getQueueHead(){
if (isEmpty()){
throw new RuntimeException("队列为空");
}
return arr[front % maxSize];
}
}
运行结果
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
11
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
12
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
13
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
14
队列已满,无法添加数据
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
s
11 12 13
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
g
11
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
a
添加一个数据
14
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据
s
12 13 14
s:显示队列
e:退出程序
a:添加数据
g:从队列中取数据
h:查看当前队列头的数据