- 一、队列简介：
- 二、队列的存储结构：
- 三、顺序队列的常见实现方式：
- 四、队列的顺序存储实现，底层使用数组来模拟队列类：
- 基础版：不能实现重复使用队列：
- 升级版：循环数组搭建循环队列：
- 五、链表：
- （1）单向链表：
队列在生活中的应用：银行排队办理业务：
总结：即增加数据在队列的尾部增加，和生活中的排队一样，而取出数据是在队列的队首。
二、队列的存储结构：单词说明：
rear:后面，尾部
front:前面，首部
上图中：使用数组模拟队列的存储示意：
假溢出：顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能进行入队列操作的溢出。
真溢出：顺序队列的最大存储空间已经存满,此时进行入队列操作所引起的溢出（即没有多余的物理空间）。
三、顺序队列的常见实现方式：方式一：（不推荐）
队头不动，出队列时队头后的所有元素向前移动。这种方式能克服队列的假溢出。
但是这种队列缺陷：操作是如果出队列比较多，要搬移大量元素。
方式二：
队头移动，出队列时队头向后移动一个位置。
但是这种队列缺陷：如果还有新元素F进行入队列容易造成假溢出。
方式二升级版：（推荐）
将数组存储区看成一个首尾相接的环形，然后形成一个环形队列，避免假溢出。
代码实现：
代码演示：
package com.fan.queue;
import java.util.Scanner;
//测试类
public class ArrayQueueDemo{
public static void main(String[] args) {
//制作用于菜单
ArrayQueue arrayQueue = new ArrayQueue(3);
char key = ' ';//用于接收用户输入的指令
Scanner scanner = new Scanner(System.in);
boolean loop =true;
while(loop){
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头数据");
System.out.println("请输入指令：");
key = scanner.next().charAt(0);//接收编号指令
switch (key){
case 's':arrayQueue.showQueue();break;
case 'a':
System.out.println("请输入一个数字：");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g'://取出数据
try {
Object res = arrayQueue.getQueue();
System.out.printf("取出的数据是%dn",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h'://查看队头数据
try {
Object res = arrayQueue.headQueue();
System.out.printf("队首的数据是%dn",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop = false;
break;
default:break;
}
}
}
}
//数组模拟队列
class ArrayQueue {
private int maxSize;//表示数组的最大容量
private int front;//队列头的 下标
private int rear;//队列尾 的 下标
private Object[] arr;//该数据用于存放数据，模拟队列
//创建队列的构造器
public ArrayQueue(int arrMaxSize){
maxSize = arrMaxSize;
arr = new Object[maxSize];
front = -1;//指向队列头部，分析出front是指向队列头部的一个位置
rear = -1;//指向队列尾部，指向对垒尾部的数据（即就是队列最后一个数据）
}
//判断队列是否满了，方法名可以自定义，但是此方法不能缺少
public boolean isFull(){
return rear == maxSize - 1;//如果数组容量最大值减一等于队尾下标，则满
}
//判断队列是否为空，方法名可以自定义，但是此方法不能缺少
public boolean isEmpty(){
return rear == front;//当队首下标等于队尾下标的时候，队列为空
}
//添加数据到队列，方法名可以自定义，但是此方法不能缺少
public void addQueue(Object o){
//判断队列是否满了
if(isFull()){
System.out.println("队列满了，不能加入数据--");
return;
}
rear++;//让rear指针后移
arr[rear] = o;//将新元素放入后移的空位置
}
//获取队列的数据，出队操作，方法名可以自定义，但是此方法不能缺少
public Object getQueue(){
//判断队列是否为空
if(isEmpty()){
//通过抛出异常
throw new RuntimeException("队列为空，不能取出数据--");
}
front ++ ;//正常取数据，队首指针后移
return arr[front];//将后移后的指向元素取出来
}
//显示队列的所有数据
public void showQueue(){
//遍历
if(isEmpty()){
System.out.println("队列为空，没有数据--");
return;
}
//遍历
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%dn",i,arr[i]);
}
}
//显示队列的头数据，注意不是取出数据
public Object headQueue(){
if(isEmpty()){
throw new RuntimeException("队列为空，没有数据");
}
return arr[front + 1];//开始front为-1，加一才到数组的第一个元素
}
}
测试：发现这个队列只能用一次，存满后取出元素后不能重复使用（假溢出），其他功能正常；
升级版：循环数组搭建循环队列：情况一的思路分析：
代码演示环形数组模拟队列：
package com.fan.queue;
import java.util.Scanner;
//测试类
public class CircleArrayQueueDemo{
public static void main(String[] args) {
//制作用于菜单
CircleArrayQueue circleArrayQueue = new CircleArrayQueue(4);
char key = ' ';//用于接收用户输入的指令
Scanner scanner = new Scanner(System.in);
boolean loop =true;
while(loop){
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头数据");
System.out.println("请输入指令：");
key = scanner.next().charAt(0);//接收编号指令
switch (key){
case 's':circleArrayQueue.showQueue();break;
case 'a':
System.out.println("请输入一个数字：");
int value = scanner.nextInt();
circleArrayQueue.addQueue(value);
break;
case 'g'://取出数据
try {
Object res = circleArrayQueue.getQueue();
System.out.printf("取出的数据是%dn",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h'://查看队头数据
try {
Object res = circleArrayQueue.headQueue();
System.out.printf("队首的数据是%dn",res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop = false;
break;
default:break;
}
}
}
}
//数组模拟队列
class CircleArrayQueue {
private int maxSize;//表示数组的最大容量
private int front;//队列头的 下标,指向下标0
private int rear;//队列尾 的 下标,指向下标0
private Object[] arr;//该数据用于存放数据，模拟队列
//创建队列的构造器
public CircleArrayQueue(int arrMaxSize){
maxSize = arrMaxSize;
arr = new Object[maxSize];
front = 0;//指向队列头部
rear = 0;//指向队列尾部
}
//判断队列是否满了，方法名可以自定义，但是此方法不能缺少
public boolean isFull(){
return (rear + 1) % maxSize == front;//如果数组容量最大值减一等于队尾下标，则满
}
//判断队列是否为空，方法名可以自定义，但是此方法不能缺少
public boolean isEmpty(){
return rear == front;//当队首下标等于队尾下标的时候，队列为空
}
//添加数据到队列，方法名可以自定义，但是此方法不能缺少
public void addQueue(Object o){
//判断队列是否满了
if(isFull()){
System.out.println("队列满了，不能加入数据--");
return;
}
//直接将数据插入
arr[rear] = o;//将新元素放入后移的空位置
//为了让数组的下标在0-3（假设maxSize=4 ）之间循环，我们采用取模的策略来防止数组下标越界
rear = (rear + 1) % maxSize;//让rear指针后移
}
//获取队列的数据，出队操作，方法名可以自定义，但是此方法不能缺少
public Object getQueue(){
//判断队列是否为空
if(isEmpty()){
//通过抛出异常
throw new RuntimeException("队列为空，不能取出数据--");
}
Object v = arr[front];//将队首元素取出备用
front = (front + 1) % maxSize ;//队首指针后移
return v;//返回取出的元素
}
//显示队列的所有数据
public void showQueue(){
//遍历
if(isEmpty()){
System.out.println("队列为空，没有数据--");
return;
}
//遍历,size()为实际元素个数
for (int i = front; i < front + size() ; i++) {
System.out.printf("arr[%d]=%dn",i % maxSize,arr[i % maxSize]);
}
}
//显示队列的头数据，注意不是取出数据
public Object headQueue(){
if(isEmpty()){
throw new RuntimeException("队列为空，没有数据");
}
return arr[front];//
}
//求出当前队列有效元素的个数
public int size(){
return (rear - front + maxSize) % maxSize;
}
}
测试：
总结：禁存区是随着存取元素的环形动态变换的。
方式二代码演示省略；
五、链表：链表介绍：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
（1）单向链表：（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。
这里我们将head节点理解成数据域为null,指针域是next.
代码演示：
package com.fan.linkedlist;
public class SinglelinkedListDemo{
public static void main(String[] args) {
//创建单独的每个节点
Heronode heroNode1 = new Heronode(1, "宋江", "及时雨");
Heronode heroNode2 = new Heronode(2, "卢俊义", "玉麒麟");
Heronode heroNode3 = new Heronode(3, "吴用", "智多星");
Heronode heroNode4 = new Heronode(4, "林冲", "豹子头");
//创建链表,并拼接单独的节点
SinglelinkedList singlelinkedList = new SinglelinkedList();
singlelinkedList.add(heroNode1);
singlelinkedList.add(heroNode2);
singlelinkedList.add(heroNode3);
singlelinkedList.add(heroNode4);
//显示链表
singlelinkedList.list();
}
}
//定义SinglelinkedList,管理我们的英雄，即组合这个链表
class SinglelinkedList {
//一个单链表，至少包含一个头节点
//(1)先初始化一个头节点，头节点不要动，不存放具体的数据
private Heronode head = new Heronode(0,"","");
//(2)添加节点组合到单向链表
//思路：当不考虑编号顺序是
//1.找到当前链表的最后节点
//2.将左后这个节点的next指向新的节点
public void add(Heronode heroNode){
//重点方法：
//因为head节点不能动，因此我们需要一个辅助遍历节点temp
Heronode temp = head;//将head节点赋值给临时节点
//遍历链表，找到最后
while(true){
//找到链表最后,即只有一个头节点，temp此时就是head节点
if(temp.next == null){
break;
}
//如果没有找到最后，就将temp后移,类似于i=i+1,那种i用来遍历数组
temp = temp.next;//将下一个位置的节点赋值给temp临时节点
}
//当退出while循环时，temp就指向了链表的最后
//将最后这个节点的next指向新的节点
temp.next = heroNode;
}
//显示链表【遍历】
public void list(){
//判断链表是否为空，只有一个头节点的话直接结束
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动，因此我们们需要一个临时节点变量temp来遍历
Heronode temp = head.next;//将头节点的下一个节点赋值给临时节点
while(true){
//判断是否到链表最后
if(temp == null){
break;
}
//输出节点信息
System.out.println(temp);
//将temp后移，一定小心
temp = temp.next;
}
}
}
//可以将节点定义成内部类，方便组合使用
//定义HeroNode节点，每个HeroNode对象就是一个节点，属性可以自己定义
class HeroNode{
//no,name,nickname属于数据域，next属于指针域
public Integer no;
public String name;
public String nickname;
//指向下一个节点，下一个节点也是完整的节点对象
public Heronode next;
//构造器，用于构造一个节点对象
public Heronode(Integer no,String name,String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override //为了显示方法，我们重写tosting
public String toString() {
return "HeroNode{" +"no="+no+
",name='" + name + ''' +
", nickname='" + nickname + ''' +
'}';
}
}
测试：发现链表添加节点成功：
需求二：按照编号顺序添加：
增加的代码：
//按照编号顺序添加到链表中，插入顺序乱序
public void addByIdOrder(Heronode newNode){
//因为头节点不能动，我们需要一个辅助节点变量来帮助我们找到添加位置
//因为是单链表，我们找到的temp是位于添加位置前的一个节点，否则插入不了
Heronode temp = head;
boolean flag = false;//flag标志添加的编号是否存在，默认不存在
//while是为了遍历找插入位置
while(true){
//只有一个头节点，则退出后，直接添加
if(temp.next == null){
break;
}
//判断编号定插入位置
if(newNode.no < temp.next.no ){//位置找到，就在temp的后面插入
break;
}else if(temp.next.no == newNode.no){//说明希望添加的新节点的编号已经存在
flag = true;//说明编号存在
break;
}
//指针后移,遍历当前链表
temp = temp.next;
} //end-while
//判断flag的值，进行真正插入
if(flag){//flag为true,不能添加，说明编号存在了
System.out.printf("准备插入的节点的标号是%d," +
"已经存在，不能加入n",newNode.no);
}else{
//插入到链表中，temp的后面
newNode.next = temp.next;//将原来temp的旧的下一级给到新节点的下一级
temp.next = newNode;//将现在的新节点串联到上一级temp的下一级next
}
}
//测试代码：
public class SinglelinkedListDemo{
public static void main(String[] args) {
//创建单独的每个节点
Heronode heroNode1 = new Heronode(1, "宋江", "及时雨");
Heronode heroNode2 = new Heronode(2, "卢俊义", "玉麒麟");
Heronode heroNode3 = new Heronode(3, "吴用", "智多星");
Heronode heroNode4 = new Heronode(4, "林冲", "豹子头");
//创建链表,并拼接单独的节点
SinglelinkedList singlelinkedList = new SinglelinkedList();
singlelinkedList.addByIdOrder(heroNode4);
singlelinkedList.addByIdOrder(heroNode3);
singlelinkedList.addByIdOrder(heroNode2);
singlelinkedList.addByIdOrder(heroNode1);
//显示链表
singlelinkedList.list();
}
}
测试结果：
