JAVA数据结构与算法之数组模拟队列
程序员文章站
2022-05-04 12:37:38
...
-
前言:
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。
队列
队列简介:
- 队列属于一种线性存储结构,是一个特殊的线性表
- 队列是一种先入先出 FIFO的线性表
队列的存储结构:
-
顺序存储:
利用一组连续的地质单元存放队列元素(通常使用数组)
(注:因数组模拟队列,为了方便起见出入队只将两个指针进行移动)
- 链式存储:
后续更新
队列基本操作:
- 入队(增): 将数据放入队尾(rear),并将队尾指针后移一位
- 出队(删): 将队首(front) 数据取出,并将队首指针后移一位
- 查询队首元素(查): 返回队首元素的值,并不移动指针
- 判断队列是否为空: 判断队列中是否含有数据
- 判断队列是否已满: 判断队列是否满或者 假溢出1
代码实现以及思路:
- 准备工作:
- 对程序中用到的变量做出如下约定:
front:指向队列头前一个元素
rear:指向队尾
private int maxSize; // 最大容量
private int front; // 指向队列头前一个元素
private int rear; // 指向队列尾
private int[] data; // 核心数组
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.data = new int[maxSize];
this.front = -1;
this.rear = -1;
}
- 判空:
- 本身未插入数据,即 rear=front=-1
- 插入数据后又将数据全部取出,已经取走队尾的数据,即 rear=front
/**
* <pre>
* 队列是否为空
* </pre>
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
- 判满:
判断队尾指针是否已经到达顺序表最后一位
/**
* <pre>
* 队列是否为空
* </pre>
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
- 入队(增):
- 先判断队列是否已满
- 将数据写在当前队尾的后一个位置
(1)先将队尾指针后移
(2)将数据写入队尾指针所在位置
/**
* <pre>
* 向队列中增加数据
*
* <pre>
*
* @param n 插入数据
* @see ArrayQueue#isFull()
*/
public void add(int n) {
// 判断队列是否已满
if (isFull())
throw new ArrayIndexOutOfBoundsException("队列已满");
/**
* 等同于<code>rear++; data[rear]=n;</code>
*/
data[++rear] = n;
}
- 出队:
- 先判断队列是否为空
- 取出队首位置元素,并将队首指针后移
(1)因我们约定front指向队首前一个元素,先将front后移
(2)再取出front位置的元素
/**
* <pre>
* 取数据
* </pre>
*
* @return
* @see ArrayQueue#isEmpty()
*/
public int get() {
if (isEmpty())
throw new RuntimeException("队列空");
/**
* 等同于<code>front++; return data[front];</code>
*/
return data[++front];
}
- 查询队首元素:
思路与出队基本相同,但是不讲队首指针后移
因此只需取出front+1位置上的元素
/**
* <pre>
* 读取队首数据
* </pre>
*
* @return
* @see ArrayQueue#isEmpty()
*/
public int read() {
if (isEmpty())
throw new RuntimeException("队列空");
/**
* 等同于<code>front=front+1; return data[front];</code>
*/
return data[front + 1];
}
- 打印队列:
- 首先判断队列是否为空
- 遍历核心数组
但是因为在做出队时只是将front后移,并没有真正的删除
因此在遍历时,应从front+1的位置开始,到rear的位置结束
/**
* 打印数据
*
* @see ArrayQueue#isEmpty()
*/
public void display() {
if (isEmpty())
throw new RuntimeException("队列空");
for (int i = front + 1; i <= rear; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
完整代码:
package DataStructures.linear.queue;
/**
*
* <pre>
* 数组实现队列
* </pre>
*
* @param <code>int maxSize</code>->最大容量
* @param <code>int front</code>->指向队列头前一个元素
* @param <code>int rear</code>->指向队列尾
* @param <code>int[] data</code>->核心数组
*
* @author Lansion
* @version 1.0
* @since 1.0
*/
public class ArrayQueue {
private int maxSize; // 最大容量
private int front; // 头
private int rear; // 尾
private int[] data; // 核心数组
public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.data = new int[maxSize];
this.front = -1;
this.rear = -1;
}
/**
* <pre>
* 队列是否已满
* </pre>
*
* @return
*/
public boolean isFull() {
return rear == maxSize - 1;
}
/**
* <pre>
* 队列是否为空
* </pre>
*
* @return
*/
public boolean isEmpty() {
return rear == front;
}
/**
* <pre>
* 向队列中增加数据
*
* <pre>
*
* @param n 插入数据
* @see ArrayQueue#isFull()
*/
public void add(int n) {
// 判断队列是否已满
if (isFull())
throw new ArrayIndexOutOfBoundsException("队列已满");
/**
* 等同于<code>rear++; data[rear]=n;</code>
*/
data[++rear] = n;
}
/**
* <pre>
* 取数据
* </pre>
*
* @return
* @see ArrayQueue#isEmpty()
*/
public int get() {
if (isEmpty())
throw new RuntimeException("队列空");
/**
* 等同于<code>front++; return data[front];</code>
*/
return data[++front];
}
/**
* <pre>
* 读取队首数据
* </pre>
*
* @return
* @see ArrayQueue#isEmpty()
*/
public int read() {
if (isEmpty())
throw new RuntimeException("队列空");
/**
* 等同于<code>front=front+1; return data[front];</code>
*/
return data[front + 1];
}
/**
* 打印数据
*
* @see ArrayQueue#isEmpty()
*/
public void display() {
if (isEmpty())
throw new RuntimeException("队列空");
for (int i = front + 1; i <= rear; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
-
是指队尾指针已经指向最后一个存储位置,但前面仍有空闲位置,这时程序已经认为队列已满,其实还有空间,防止假溢出最简单的方式就是环形队列。 ↩︎
上一篇: 皇帝招才女入宫,她作词一首就失宠了
下一篇: JavaScript基础内容中的函数详解