作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
简书：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
上一篇讲了栈，这一篇要讲的是我们常用的队列，我会从以下几个方面进行总结。
1、什么是队列
2、队列的存储结构
3、队列的常用操作及实现代码
1、什么是队列
（1）首先，队列也是一种特殊的线性表，它是一种操作受限的线性表。只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾，允许删除的一端称为队头。
（2）队列与现实生活中的排队类似（如下图），新加入的成员总是在队尾，而排在队列最前面的总是最先离开队列，即先进先出 First In First Out (FIFO)，因此队列就是先进先出线性表。
（3）线性表分为顺序表和链表，所以队列也分为顺序队列和链式队列，为了方便演示，下文所使用的队列都是顺序队列。
2、队列的存储结构
用java语言自己封装一个顺序队列：
SeqQueue.java
/**
* 封装一个顺序队列
*/
public class SeqQueue {
// 保存数据
public Object[] data;
// 头指针
public int head;
// 尾指针
public int rear;
// 队列的最大容量
public int maxSize;
public SeqQueue(int maxSize) {
this.maxSize = maxSize;
data = new Object[maxSize];
}
}
3、队列的常用操作及实现代码
3-1、初始化队列
思路：构造一个空队列，并将头指针head和尾指针rear都设置为0。
代码：SeqQueueOperate.java
/**
* 封装队列的常见操作
*/
public class SeqQueueOperate {
/**
* 初始化
*
* @param maxSize
* @return
*/
public SeqQueue init(int maxSize) {
SeqQueue queue = new SeqQueue(maxSize);
queue.head = 0;
queue.rear = 0;
return queue;
}
}
3-2、入队
思路：若队列没有满，则将数据插入到尾指针rear指向的位置，然后再将rear加1。
代码：在 SeqQueueOperate.java 中添加方法
/**
* 入队
*/
public void enter(SeqQueue queue, Object obj) {
// 判断队列是否已经满了
if (queue.rear >= queue.maxSize) {
return;
}
queue.data[queue.rear] = obj;
queue.rear++;
}
3-3、出队
思路：若队列不为空，则将头指针指向的元素删除，然后将头指针加1。
代码：在 SeqQueueOperate.java 中添加方法
/**
* 出队
*/
public Object dequeue(SeqQueue queue) {
// 判断队列是否为空
if (queue.head == queue.rear) {
return null;
}
Object obj = queue.data[queue.head];
queue.data[queue.head] = null;
queue.head++;
return obj;
}
3-4、取队头
思路：若队列不为空，则返回队头元素。
代码：在 SeqQueueOperate.java 中添加方法
/**
* 取队头
*/
public Object getHead(SeqQueue queue) {
// 判断队列是否为空
if (queue.head == queue.rear) {
return null;
}
Object obj = queue.data[queue.head];
return obj;
}
3-5、取队长
思路：即尾指针 - 头指针的值。
代码：在 SeqQueueOperate.java 中添加方法
/**
* 取队长
*/
public int getLength(SeqQueue queue) {
return queue.rear - queue.head;
}
3-6、判队空
思路：只需要判断头指针和尾指针是否相等即可
代码：在 SeqQueueOperate.java 中添加方法
/**
* 判断队列是否为空
*/
public boolean isEmpty(SeqQueue queue) {
return queue.head == queue.rear;
}
3-7、判队满
思路：只需判断尾指针与maxSize是否相等即可
代码：在 SeqQueueOperate.java 中添加方法
/**
* 判断队列是否已经满了
*/
public boolean isFull(SeqQueue queue) {
return queue.rear >= queue.maxSize;
}
4、测试
添加一个用来测试的类
QueueTest.java
/**
* 用来测试
*/
public class QueueTest {
public static void main(String[] args) {
SeqQueueOperate seqQueueOperate = new SeqQueueOperate();
// 最大容量设置为5
int maxSize = 5;
SeqQueue queue = seqQueueOperate.init(maxSize);
System.out.println("队列的最大容量是：" + maxSize);
// 当前队列的长度
System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
System.out.println("");
System.out.println("===========入队start ===========");
System.out.println("插入6个元素试试");
seqQueueOperate.enter(queue, 1);
seqQueueOperate.enter(queue, 2);
seqQueueOperate.enter(queue, 3);
seqQueueOperate.enter(queue, 4);
seqQueueOperate.enter(queue, 5);
seqQueueOperate.enter(queue, 6);
System.out.println("===========入队end =============");
// 当前队列的长度
System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
System.out.println("");
// 出队
System.out.println("===========出队start ===========");
Object obj = seqQueueOperate.dequeue(queue);
System.out.println("出队的元素是：" + obj);
System.out.println("===========出队end =============");
// 当前队列的长度
System.out.println("当前队列的长度是：" + seqQueueOperate.getLength(queue));
System.out.println("");
System.out.println("------------------------------------");
System.out.println("队头元素是：" + queue.data[queue.head]);
System.out.println("队尾元素是：" + queue.data[queue.rear-1]);
}
}
测试结果：
注意：在一个非空的队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。
网友评论