Java数据结构与算法-1.2队列
队列
1.队列的一个使用场景
银行排队的案例:
2.队列介绍
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出
示意图：(使用数组模拟队列示意图)
3.数组模拟队列思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
思路分析：
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析
- 将尾指针往后移：rear+1 , 当front == rear 【空】
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1【队列满】
4.数组模拟队列实现
1.新增元素addQueue
2.出队列操作getQueue
3.显示队列的情况showQueue
4.查看队列头元素headQueue
5.退出系统exit
代码实现
/**
* 功能描述: 队列 - 数组模拟队列练习
*
* @author lunaw-
* @version 1.0
* @date 2023/12/7 22:37
*/
public class QueueDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入队列容量:");
char c = ' ';
int num = scanner.nextInt();
MyQueue myQueue = new MyQueue(num);
boolean flag = true;
while (flag) {
System.out.println("请输入要进行的操作:p(查看队列头部元素),a(添加元素到队列),g(取出元素出队列),s(展示队列),e(退出程序)");
c = scanner.next().charAt(0);
switch (c) {
case 'p':
System.out.println(myQueue.peak());
break;
case 'a':
System.out.print("请输入要添加的元素:");
myQueue.addQueue(scanner.nextInt());
break;
case 'g':
System.out.println(myQueue.getQueue());
break;
case 's':
myQueue.showQueue();
break;
case 'e':
flag = false;
break;
}
}
}
}
/**
* 队列
*/
class MyQueue {
private int[] array;
//队列数据容量
private int size;
//指向头元素的前一个位置
private int front;
//指向尾元素
private int rear;
public MyQueue(int size) {
this.size = size;
array = new int[size];
front = -1;
rear = -1;
}
/**
* 添加元素
*
* @param num 元素
*/
public void addQueue(int num) {
if (isFull()) {
System.out.println("队列已满！");
return;
}
rear++;
array[rear] = num;
}
/**
* 取出元素
*
* @return 取出的元素
*/
public int getQueue() {
if (isEmpty()) {
System.out.println("队列为空！");
return -999;
}
front++;
return array[front];
}
/**
* 显示队列
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空!");
return;
}
for (int i = front + 1; i < rear + 1; i++) {
System.out.print(array[i] + "\t");
}
System.out.println();
}
/**
* 查看队列头元素
*
* @return 头元素
*/
public int peak() {
if (isEmpty()) {
System.out.println("队列为空！");
return -999999;
}
return array[front + 1];
}
/**
* 队列是否已满
*
* @return true/false
*/
private boolean isFull() {
return rear == size - 1;
}
/**
* 队列是否为空
*
* @return true/false
*/
private boolean isEmpty() {
return front == rear;
}
}
5.数组模拟环形队列
针对前面的练习，我们实现了队列的功能，但是我们发现队列的利用率很低，数组的每个位置只能用一次，针对这种问题，我们提出了环形队列的思路：将数组看做是一个环形的。(通过取模的方式来实现即可)
分析说明：
尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意
(rear + 1) % maxSize == front 【满】
rear == front【空】
代码实现:
public class CircleQueueDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入队列容量:");
char c = ' ';
int num = scanner.nextInt();
CircleQueue myQueue = new CircleQueue(num);
boolean flag = true;
while (flag) {
System.out.println("请输入要进行的操作:p(查看队列头部元素),a(添加元素到队列),g(取出元素出队列),s(展示队列),e(退出程序)");
c = scanner.next().charAt(0);
switch (c) {
case 'p':
System.out.println(myQueue.peak());
break;
case 'a':
System.out.print("请输入要添加的元素:");
myQueue.addQueue(scanner.nextInt());
break;
case 'g':
System.out.println(myQueue.getQueue());
break;
case 's':
myQueue.showQueue();
break;
case 'e':
flag = false;
break;
}
}
}
}
/**
* 环形队列
*/
class CircleQueue {
private int[] array;
//队列数据容量
private int size;
//指向头元素的位置
private int front;
//指向尾元素的后一个位置
private int rear;
public CircleQueue(int size) {
this.size = size;
array = new int[size];
front = 0;
rear = 0;
}
/**
* 添加元素
*
* @param num 元素
*/
public void addQueue(int num) {
if (isFull()) {
System.out.println("队列已满！");
return;
}
array[rear] = num;
rear = (rear + 1)%size;
}
/**
* 取出元素
*
* @return 取出的元素
*/
public int getQueue() {
if (isEmpty()) {
System.out.println("队列为空！");
return -999;
}
int num = array[front];
front = (front+1)%size;
return num;
}
/**
* 显示队列
*/
public void showQueue() {
if (isEmpty()) {
System.out.println("队列为空!");
return;
}
for (int i = front; i < (rear - front + size) % size; i++) {
System.out.print(array[i] + "\t");
}
System.out.println();
}
/**
* 查看队列头元素
*
* @return 头元素
*/
public int peak() {
if (isEmpty()) {
System.out.println("队列为空！");
return -999999;
}
return array[front];
}
/**
* 队列是否已满
*
* @return true/false
*/
private boolean isFull() {
return (rear +1 - front + size)%size == 0;
}
/**
* 队列是否为空
*
* @return true/false
*/
private boolean isEmpty() {
return (rear - front + size)%size == 0;
}
}