什么是队列?
队列是一个有序列表,可以用数组或链表实现
遵循先入先出的(First in First Out)原则。即:先存入队列的数据，要先取出。后存入的要后取出
当队列中插入元素后,此元素可以被读取
当队列中元素被取出后,此元素就会从队列中移出
队列初始状态图解
image.png
从上图可以看出数组队列中包含元素:
1. 队列头指针,用来记录当前队列可读取的元素位置
2. 队列尾指针,用来记录当前队列可以写入的元素位置
3. 队列的容量大小(数组容量)
4. 队列中的数组
5. 队列中可读取的元素数量
队列应该有那些方法?
一个队列应该需要那些操作?
1. 将元素插入队列方法 enQueue(item) 操作tail尾指针写入元素数据
2. 获取队列元素方法 E deQeueu() 操作front头指针从队列中获取元素数据
3. 查看队列当前头指针的元素 E showFront()
4. 获取队列中的元素数量 int getSize()
5. 判断队列是否为空 boolean isEmpty()
队列实战案例一:数组实现队列
数组实现队列思路分析:
- 定义队列数组,定义头指针与尾指针和size
- 初始化队列数组,头指针,尾指针,通过构造函数完成
- 编写enQueue(item)添加元素操作
添加元素需要判断队列是否已经满,没有满才可以插入元素
如何判断队列满了?
如果tail==capacity表示队列满了
如何队列满了应该怎么办?
扩容,第一个案例我们先不使用扩容来操作,后面再进行扩容操作 - 编写deQueue()取出元素操作
取出元素操作需要判断列表是否为空,为空表示没有数据 - 编写getSize()获取元素数量操作
- 编写判断队列是否为空的操作
如何判断队列中没有元素?
如果头指针与尾指针相等,则表示没有元素,所以tail==front就表示队列为空
- 编写队列接口
/**
* @author 凡人静水
* 注释: 此接口定义队列的接口方法
*/
public interface Queue {
//添加元素到队列
int enQueue(int e);
//从队列中取出元素
int deQeueu();
//查看队列头元素
int showFront();
//查看有多少元素可读
int getSize();
//判断队列是否为空
boolean isEmpty();
}
- 编写队列实现
/**
* @author 凡人静水
* 注释: 数组实现队列
*/
public class IntArrayQueue implements Queue {
//1.定义队列数组,定义头指针与尾指针和size
private int[] arr;
private int capacity;
private int front;
private int tail;
private int size;
//2.初始化队列数组,头指针,尾指针,通过构造函数完成
public IntArrayQueue(int capacity) {
this.arr = new int[capacity];
this.capacity = capacity;
this.front = 0;
this.tail = 0;
this.size = 0;
}
public IntArrayQueue() {
//默认创建大小为5的数组
this(5);
}
//3.编写enQueue(item)添加元素操作
public void enQueue(int e) {
//添加元素需要判断队列是否已经满,没有满才可以插入元素
if (tail == capacity) {
throw new RuntimeException("队列满了...请扩容");
}
//添加元素,只需要改变尾指针即可
arr[tail] = e;
//插入元素后,尾指针需要向前移动一位,准备好下次元素插入的位置
tail++;
//插入元素时需要给size++,表示队列中元素个数
size++;
}
//4.编写deQueue()取出元素操作
public int deQeueu() {
//取出元素操作需要判断列表是否为空,为空表示没有数据
if (isEmpty()) {
throw new RuntimeException("队列中没有元素...");
}
int result = arr[front];
//取出数据通过头指针,取出后移动到下一个读取的位置
front++;
//取出元素时需要给size--,表示队列中元素个数
size--;
return result;
}
//7.查看队列的头部
public int showFront() {
if (isEmpty())
System.out.println("队列中没有元素....");
return arr[front];
}
//5.编写getSize()获取元素数量操作
public int getSize() {
return size;
}
//6.编写判断队列是否为空的操作
public boolean isEmpty() {
return tail == front;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d ,capacity=%d , front=%d , tail=%d\n", size, capacity, front, tail));
res.append("[");
for (int i = front; i < tail; i++) {
res.append(arr[i]);
if (i != (tail - 1) ){
res.append(",");
}
}
res.append("]");
return res.toString();
}
}
- 编写测试
public static void main(String[] args) {
IntArrayQueue queue = new IntArrayQueue(10);
System.out.println("添加数据:");
for (int i = 0; i < 3; i++) {
try {
queue.enQueue(i);
} catch (Exception e) {
break;
}
System.out.println(queue);
System.out.println("----------------------------------");
}
int result = queue.deQeueu();
System.err.println("取出数据:" + result);
System.err.println(queue);
result = queue.deQeueu();
System.err.println("取出数据:" + result);
System.err.println(queue);
}
- 测试结果
添加数据:
Array: size = 1 ,capacity=10 , front=0 , tail=1
[0]
----------------------------------
Array: size = 2 ,capacity=10 , front=0 , tail=2
[0,1]
----------------------------------
Array: size = 3 ,capacity=10 , front=0 , tail=3
[0,1,2]
----------------------------------
取出数据:0
Array: size = 2 ,capacity=10 , front=1 , tail=3
[1,2]
取出数据:1
Array: size = 1 ,capacity=10 , front=2 , tail=3
[2]
图解队列执行流程
第一次添加元素
image.png
第二次添加元素
image.png
第三次添加元素
image.png
第一次取出元素
image.png
第二次取出元素
image.png
数组队列的问题
通过上面的测试结果,发现以下问题:
当取出数据后,发现front的值为2,此时,队列的前两个空间没有被使用,而之后插入也都不会插入到这两个空间中,所以被浪费掉了!
结论:只要取出数据后,空间就没办法再用了,只能通过扩容来维护新的数组,这肯定不是好的解决方案
解决方案:通过环形(循环)队列来解决上面的问题,下一章我们看看环形队列如何实现,及其实现原理
搜索公众号,查看更多专题文章:javastu
网友评论