数据结构之队列
队列
有序列表
先进先出(FIFO)
单向队列
基于数组实现
- 数组大小
- 数组
- 队头指针(front)：指向队首元素的前一个位置
- 队尾指针(rear)：指向队尾元素位置
判空条件：front == rear （单向队列有可能此情况也是满, 因为前面元素没有办法重复利用）
判满条件：rear == size - 1
代码实现
package org.example.data.structure.queue;/*** 基于数组实现队列** @author xzy* @since 2024/8/25 14:53*/
public class ArrayQueue {/*** 队列头: 头部元素的前一个索引位置*/private Integer front;/*** 队列尾: 与尾部元素的索引位置在同一个*/private Integer rear;/*** 数组容量*/private Integer size;/*** 数组内容*/private Integer[] content;/*** 构造器创建数组*/public ArrayQueue(Integer size) {this.size = size;this.content = new Integer[size];front = -1;rear = -1;}/*** 队列是否为空*/public Boolean isEmpty() {return front == rear;}/*** 队列是否已满*/public Boolean isFull() {return rear == (size - 1);}/*** 添加元素-入队*/public Boolean add(Integer data) {if (isFull()) {System.out.println("队列已满, 无法添加元素");return false;}// 队尾索引+1rear++;content[rear] = data;return true;}/*** 移除元素-出队*/public Integer getData() {if (isEmpty()) {System.out.println("队列为空, 无数据需要出队");return null;}front++;Integer result = content[front];// 原有位置赋空, 可以不赋值, 因为单向队列也不会再取值content[front] = null;return result;}/*** 展示头部元素*/public Integer showHead() {if (isEmpty()) {return null;}return content[front + 1];}/*** 展示尾部元素*/public Integer showRear() {if (isEmpty()) {return null;}return content[rear];}/*** 展示队列中所有的元素*/public String toString() {if (isEmpty()) {return "";}StringBuilder str = new StringBuilder();for (int i = front + 1; i <= rear; i++) {str.append(content[i]).append("\t");}return str.toString();}}循环队列
作用
为了弥补单向队列中只能一次利用的场景而出现。其中，实现循环队列有多种方式：
- 类型中增设表示元素个数的数据成员
- 牺牲一个单元来区分队空和队满，入队时少用一个队列单元
本次以第二种方式进行实现：
- 数组大小
- 数组
- 队首指针(front)：指向队首元素，初始化为0
- 队尾指针(rear)：指向队尾元素的后一个元素，初始化为0
判空条件：front == rear
判满条件：(rear + 1) % size == front
有效数据个数：(rear - front + size) % size
代码实现
package org.example.data.structure.queue;/*** 循环队列: 基于数组实现** @author xzy* @since 2024/8/25 17:12*/
public class CircleArrayQueue {/*** 队首位置, 处于队列中第一个元素*/private int front;/*** 队尾位置, 处于队列中最后元素的后一位*/private int rear;/*** 循环数组*/private Integer[] content;/*** 循环数组大小, 该size会是content的大小, 其中size的大小会是content中真实元素个数 + 1, 即会存在一个空元素*/private int size;public CircleArrayQueue(int size) {// 初始化循环队列, 队首和队尾元素位置均从0位置开始front = 0;rear = 0;this.size = size;content = new Integer[size];}/*** 判断队列是否为空*/public boolean isEmpty() {return front == rear;}/*** 判断队列是否已满*/public boolean isFull() {return (rear + 1) % size == front;}/*** 入队元素*/public boolean add(int data) {if (isFull()) {System.out.println("队列已满, 无法添加元素");return false;}content[rear] = data;// rear后移rear = (rear + 1) % size;return true;}/*** 出队*/public Integer getData() {if (isEmpty()) {System.out.println("队列为空, 返回空数据");return null;}int result = content[front];content[front] = null;front = (front + 1) % size;return result;}/*** 队列中的有效个数*/public int count() {if (isEmpty()) {return 0;}if (isFull()) {return size - 1;}// 可以分两种情况, 其实可以化简为 (rear - front + size) % sizeif (rear > front) {return rear - front;}return rear - front + size;}/*** 显示头元素*/public Integer showHead() {if (isEmpty()) {System.out.println("队列为空, 返回Null");return null;}return content[front];}/*** 显示尾元素*/public Integer showRear() {if (isEmpty()) {System.out.println("队列为空, 返回Null");return null;}return content[(rear - 1 + size) % size];}/*** 打印*/public String toString() {if (isEmpty()) {return "";}StringBuilder str = new StringBuilder();if (rear < front) {for (int i = front; i < size; i++) {str.append(content[i]).append("\t");}for (int i = 0; i < rear; i++) {str.append(content[i]).append("\t");}} else {for (int i = front; i < rear; i++) {str.append(content[i]).append("\t");}}return str.toString();}}