上一篇讲了 栈 ,这一篇要讲的是我们常用的队列,我会从以下几个方面进行总结.
1,什么是队列
2,队列的存储结构
3,队列的常用操作及实现代码
1,什么是队列
(1)首先,队列也是一种特殊的 线性表 ,它是一种操作受限的线性表.只允许在表的一端进行元素插入,而在另一端进行元素删除.允许插入的一端称为队尾,允许删除的一端称为队头.
(2)队列与现实生活中的排队类似(如下图),新加入的成员总是在队尾,而排在队列最前面的总是最先离开队列,即先进先出 First In First Out (FIFO),因此队列就是先进先出线性表.
(3)线性表分为顺序表和链表,所以队列也分为顺序队列和链式队列,为了方便演示,下文所使用的队列都是顺序队列.
2,队列的存储结构
用 java 语言自己封装一个顺序队列:
* 封装一个顺序队列
SeqQueue.java
/**
3,队列的常用操作及实现代码
* /
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-1,初始化队列
思路:构造一个空队列,并将头指针 head 和尾指针 rear 都设置为 0.
代码:SeqQueueOperate.java
/**
* 封装队列的常见操作
* 初始化
* /
public class SeqQueueOperate {
/ * *
3-2,入队
*
* @param maxSize
* @return
*/
public SeqQueue init(int maxSize) {
SeqQueue queue = new SeqQueue(maxSize);
queue.head = 0;
queue.rear = 0;
return queue;
}
}
思路:若队列没有满,则将数据插入到尾指针 rear 指向的位置,然后再将 rear 加 1.
代码:在 SeqQueueOperate.java 中添加方法
/**
* 入队
3-3,出队
* /
public void enter(SeqQueue queue, Object obj) {
/ / 判断队列是否已经满了
if (queue.rear >= queue.maxSize) {
return;
}
queue.data[queue.rear] = obj;
queue.rear++;
}
思路:若队列不为空,则将头指针指向的元素删除,然后将头指针加 1.
代码:在 SeqQueueOperate.java 中添加方法
/**
* 出队
3-4,取队头
* /
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;
}
思路:若队列不为空,则返回队头元素.
代码:在 SeqQueueOperate.java 中添加方法
/**
* 取队头
3-5,取队长
* /
public Object getHead(SeqQueue queue) {
/ / 判断队列是否为空
if (queue.head == queue.rear) {
return null;
}
Object obj = queue.data[queue.head];
return obj;
}
思路:即尾指针 - 头指针的值.
代码:在 SeqQueueOperate.java 中添加方法
/**
* 取队长
3-6,判队空
* /
public int getLength(SeqQueue queue) {
return queue.rear - queue.head;
}/
思路:只需要判断头指针和尾指针是否相等即可
代码:在 SeqQueueOperate.java 中添加方法
/**
* 判断队列是否为空
3-7,判队满
* /
public boolean isEmpty(SeqQueue queue) {
return queue.head == queue.rear;
}/
思路:只需判断尾指针与 maxSize 是否相等即可
代码:在 SeqQueueOperate.java 中添加方法
/**
* 判断队列是否已经满了
4,测试
* /
public boolean isFull(SeqQueue queue) {
return queue.rear >= queue.maxSize;
}/
添加一个用来测试的类
* 用来测试
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]);
}
}
注意:在一个非空的队列中,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一个位置.
来源: https://www.cnblogs.com/nnngu/p/8277506.html