1.什么是队列?
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
2. 队列的特点:
队列是一种先进先出(First In First out)的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。
3. 队列顺序存储有什么不足?
使用数组实现的顺序存储,当做出队列操作时,所有的元素都需要向前移动一位,性能很低。
4. 什么是循环队列?
队列头尾相接的顺序存储结构称为循环队列。
如图所示:front记住队头元素下标,rear记住队尾元素的下一个元素。
注意:
1. 只凭等式front=rear是无法判断队空还是队满,所以我们约定当队列头指针front在队尾指针rear的下一个位置上时,作为队列"已满"的标志,当队列满时,数组中还会有一个空闲位置。
2. 我们也可以设置一个标志变量flag,当(front == rear && flag == 0) 队列为空, 当(front == rear && flag == 1)队列为满。
5. Java使用数组实现循环队列:
//循环队列的顺序存储结构(数组实现)
public class LoopQueue<T> {
private Object[] arr; // 对象数组,队列最多存储
private int front; // 记住队首下标位置
private int rear; // 记住队尾下标的下一个位置
private static final int DEFAULT_SIZE = 3; // 定义数组默认长度
public LoopQueue() {
this(DEFAULT_SIZE);
}
public LoopQueue(int size) {
arr = new Object[size];
front = 0;
rear = 0;
}
// 将元素追加到队列尾部
public boolean enqueue(T data) {
if ((rear + 1) % arr.length == front) { // 判断队列是否已满
System.out.println("队列已满,无法入队..");
return false;
}
arr[rear] = data; // 将元素data赋值到队尾
System.out.println(data + "入队..");
rear = (rear + 1) % arr.length; // real下标向后移一位,若到最后则转到数组头部
return true;
}
// 队列头部的第一个元素出队
@SuppressWarnings("unchecked")
public T dequeue() {
if (rear == front) { // 判断队列是否为空
System.out.println("队列已空,无法出队..");
return null;
}
Object data = arr[front];
System.out.println(data + "出队..");
front = (front + 1) % arr.length; // front下标向后移一位,若到最后则转到数组头部
return (T) data;
}
// 获取队列中元素个数
public int size() {
return (rear - front + arr.length) % arr.length;
}
public static void main(String[] args) {
LoopQueue<String> queue = new LoopQueue<String>();
queue.enqueue("张三");
queue.dequeue();
queue.enqueue("李四");
queue.enqueue("王五");
queue.enqueue("赵六");
queue.dequeue();
queue.enqueue("田七");
queue.dequeue();
queue.enqueue("周八");
System.out.println("队列中元素个数为: " + queue.size());
}
}
6. 循环队列的不足:
如果只是顺序存储,算法的性能不咋的,但是循环队列却不得不面临数组可能溢出的问题,有什么好的解决办法吗?
请见下节 --
链队列,未完待续 . . .
分享到:
相关推荐
大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
一个无比严谨的技术痴迷者创作的一本饱含诚意与想象力的经典存储著作。
特别提醒:本文件为《大话数据分析:Tableau数据可视化实战》的数据集,并不是PDF书籍。
大话存储:存储系统底层架构原理极限剖析(终极版)第3部分 大话存储:存储系统底层架构原理极限剖析(终极版)第3部分大话存储:存储系统底层架构原理极限剖析(终极版)第3部分
大话存储2:存储系统架构与底层原理极限剖析.docx
大话数据结构 .pptx
Android之大话设计模式——:抽象工厂模式借鉴.pdf
基于《大话数据结构》进行数据结构的学习
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)
大话存储:存储系统底层架构原理极限剖析(终极版)_张冬2015.01_P989
Android之大话设计模式——:抽象工厂模式参考.pdf
数据结构与算法问题 讲解生动 数据结构不在
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。
大话存储:存储系统底层架构原理极限剖析(终极版)第5部分 大话存储:存储系统底层架构原理极限剖析(终极版)第5部分
数据结构 线性表 栈和队列 串 数和二叉树 图 查找 内部排序
[大话存储:网[大话存储:网络存储系统原理精解与最佳实践].张冬.扫描版络存储系统原理精解与最佳实践].张冬.扫描版
大话存储:存储系统底层架构原理极限剖析(终极版)第4部分 大话存储:存储系统底层架构原理极限剖析(终极版)第4部分
《大话存储:存储系统底层架构原理极限剖析(终极版)》内容涉及:计算机IO基本概念,硬盘物理结构、盘片数据结构和工作原理,七种常见RAID原理详析以及性能细节对比,虚拟磁盘、卷和文件系统原理,磁盘阵列系统,...