数据结构 - 队列(Queue)原理和 Java 实现案例
「这是我参与11月更文挑战的第15天,活动详情查看:2021最后一次更文挑战」。
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。本文详细介绍了队列的特性,并且使用Java语言分别实现了基于顺序结构和链式结构的队列。
1 队列的概述
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队,如果你排在他前面,你将先上车,而后来的人将会排在你朋友后面。队列的工作原理与此相同。
队列是一种先进先出(First In First Out)的线性表,简称FIFO。 允许插入的一端称为队尾,允许删除的一端称为队头。假设队列是q=(a1,a2,......,an),那么a1就是队头元素,而an是队尾元素。这样我们就可以删除时,总是从a1开始,而插入时,列在最后。
因为队列属于线性表,因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现,比如JUC中的各种阻塞、非阻塞队列。在生产环境中,各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。
关于Java 栈的数据结构,可以看这篇文章:数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。
2 队列的顺序存储结构实现
2.1 队列的顺序存储结构概述
和栈不同的是,队列的入队和出队操作在不同端。采用数组来实现时,如果和实现栈的思想一样,如果队头在数组元素最大索引处,那么入队列就是将元素添加到最大索引后的索引处,不需要移动元素,此时时间复杂度为O(1);但是出队列就要在数组头部了,此时将会移动全部元素,时间复杂度为O(n)。如果队头在数组元素的起始索引处,那么出队列到时变快了,但是入队列的时间复杂度却又变成O(n)了。
因此,这里要灵活处理对头或者队尾,不再是固定在数组起始索引或者最大索引处,应该是可变的,此时需要添加外部指针用来保存“队头”和“队尾”。操作数据的时候只需要操作队头和队尾就行了,这样入队和出队的时间复杂度都是O(1)。
按照上面的做法,队头和队尾是不用固定了,入队和出队操作确实很方便。但是可能造成索引溢出以及内存浪费,如下图:
可能会出现图上的情况,队头被移动到数组的中间,而队尾由于添加元素,移动到数组尾部,此时如果再次入队,由于数组索引溢出将会抛出ArrayIndexOutOfBoundsException,但是数组的前半部分空间却还没有使用,此时又造成了空间浪费。
上面这种溢出,称为“假溢出”。假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
循环队列解决了假溢出的问题,同时入队和出队时间都是O(1)。此时需要考虑的就只是数组的容量有限的问题了。
2.2 数组循环队列的简单实现
/**
* 数组实现的循环队列,为了方便,这里底层数组设计为不可扩展
*/
public class MyArrayLoopQueue<E> {
/**
* 采用数组实现链式存储
*/
private final Object[] elements;
/**
* 容量
*/
private final int capacity;
/**
* 队头元素索引
*/
private int first;
/**
* 队尾元素索引
*/
private int end;
/**
* 元素个数
*/
private int size;
/**
* 构造器初始化数组
*
* @param capacity 容量
*/
public MyArrayLoopQueue(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
/**
* 入队,元素添加在队尾
*
* @param element 添加的元素
* @return 添加成功返回true,添加失败返回false
*/
public boolean add(E element) {
//如果队列容量已满.添加失败返回false
if (size == capacity) {
return false;
}
if (size == 0) {
/*如果是第一次放元素,则队头和队尾都指向索引0处的元素*/
elements[end] = element;
} else if (end + 1 == capacity) {
/*如果end + 1等于capacity说明队尾空间满了,转向队头,队尾队尾索引置0,循环*/
end = 0;
elements[end] = element;
} else {
/*否则,队尾索引正常自增*/
elements[++end] = element;
}
//size自增1
size++;
return true;
}
/**
* 出队,删除队头元素
*
* @return 被移除的元素, 或者null
*/
public E remove() {
//队列是否已空
if (size == 0) {
// 返回null
return null;
}
Object o = elements[first];
//移除队头元素
elements[first] = null;
//如果队头索引+1之后等于capacity,重置队头索引,循环
if (++first == capacity) {
first = 0;
}
//如果出队列后队列为空,那么重置队头和队尾索引
if (--size == 0) {
first = 0;
end = 0;
}
return (E) o;
}
/**
* 返回队列元素数量
*
* @return
*/
public int size() {
return size;
}
/**
* 清空队列
*/
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
first = 0;
end = 0;
}
/**
* 重写了toString方法
*
* @return
*/
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
if (size == 0) {
stringBuilder.append("[ ]");
return stringBuilder.toString();
}
stringBuilder.append("[ ");
if (first < end) {
for (int i = first; i <= end; i++) {
stringBuilder.append(elements[i]);
if (i != end) {
stringBuilder.append(", ");
}
}
} else if (size == 1) {
stringBuilder.append(elements[first]);
} else {
for (int i = first; i < capacity; i++) {
stringBuilder.append(elements[i]);
stringBuilder.append(", ");
}
for (int i = 0; i <= end; i++) {
stringBuilder.append(elements[i]);
if (i != end) {
stringBuilder.append(", ");
}
}
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
/**
* 增强toString方法,用于测试
*
* @return
*/
public String toStringPlus() {
StringBuilder stringBuilder = new StringBuilder();
if (size == 0) {
stringBuilder.append("[ ]");
stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
return stringBuilder.toString();
}
stringBuilder.append("[ ");
if (first < end) {
for (int i = first; i <= end; i++) {
stringBuilder.append(elements[i]);
if (i != end) {
stringBuilder.append(", ");
}
}
} else if (size == 1) {
stringBuilder.append(elements[first]);
} else {
for (int i = first; i < capacity; i++) {
stringBuilder.append(elements[i]);
stringBuilder.append(", ");
}
for (int i = 0; i <= end; i++) {
stringBuilder.append(elements[i]);
if (i != end) {
stringBuilder.append(", ");
}
}
}
stringBuilder.append(" ]");
stringBuilder.append(" ; first:").append(first).append(" ; end:").append(end).append(" ; size:").append(size);
return stringBuilder.toString();
}
}
2.2.1 测试
MyArrayLoopQueue<Object> objectMyArrayLoopQueue = new
MyArrayLoopQueue<>(4);
System.out.println("入队========>");
objectMyArrayLoopQueue.add(11);
objectMyArrayLoopQueue.add(22);
objectMyArrayLoopQueue.add(33);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
objectMyArrayLoopQueue.remove();
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("入队========>");
objectMyArrayLoopQueue.add(44);
objectMyArrayLoopQueue.add(55);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("入队========>");
objectMyArrayLoopQueue.add(null);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("入队失败========>");
boolean add = objectMyArrayLoopQueue.add(77);
System.out.println(add);
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
System.out.println("出队========>");
System.out.println(objectMyArrayLoopQueue.remove());
System.out.println(objectMyArrayLoopQueue.toStringPlus());
3 队列的链式存储结构及实现
3.1 队列的链式存储结构概述
队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。为了操作上的方便,我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。
可以看出来,使用链式结构实现队列相比顺序结构的实现更加简单。
3.2 队列的链式存储结构简单实现
/**
* 队列的链式储存结构的简单单链表实现
*/
public class MySingleLinkedQueue<E> {
/**
* 空构造器,内部的节点均没有初始化,在第一次添加时才会初始化。
*/
public MySingleLinkedQueue() {
}
/**
* 元素个数
*/
private int size;
/**
* 指向队头结点的引用
*/
private Node<E> first;
/**
* 指向队尾结点的引用
*/
private Node<E> end;
/**
* 单链表内部的节点
*/
private static class Node<E> {
//下一个结点的引用
Node<E> next;
//结点数据
E data;
//节点构造器
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
/**
* 入队,添加元素到单链表尾部
*
* @param e 要添加的元素
*/
public void add(E e) {
//创建新节点
Node<E> newNode = new Node<>(e, null);
if (end != null) {
/*如果尾结点不为空*/
end.next = newNode;
//改变队尾节点引用
end = newNode;
} else {
end = newNode;
first = newNode;
}
++size;
}
/**
* 出队,删除单链表头部元素
*
* @return 被删除的元素
*/
public E remove() {
//如果头结点为空,抛出异常
if (first == null) {
throw new NoSuchElementException("队列已经为空");
}
E e = first.data;
//改变队头节点引用
first = first.next;
//如果元素为0,则将队尾节点引用置空
if (--size == 0) {
end = null;
}
return e;
}
/**
* 获取元素数量
*/
public int size() {
return size;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
if (size > 0) {
Node<E> f = first;
stringBuilder.append("[ ");
for (int i = 0; i < size; i++) {
stringBuilder.append(f.data);
if (i != size - 1) {
stringBuilder.append(" , ");
}
f = f.next;
}
stringBuilder.append(" ]");
return stringBuilder.toString();
}
return "[]";
}
}
3.2.1 测试
MySingleLinkedQueue<Object> objectMySingleLinkedQueue = new
MySingleLinkedQueue<>();
System.out.println("入队========>");
objectMySingleLinkedQueue.add(11);
objectMySingleLinkedQueue.add(22);
objectMySingleLinkedQueue.add(33);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
objectMySingleLinkedQueue.remove();
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("入队========>");
objectMySingleLinkedQueue.add(44);
objectMySingleLinkedQueue.add(55);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("入队========>");
objectMySingleLinkedQueue.add(null);
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
System.out.println("出队异常========>");
System.out.println(objectMySingleLinkedQueue.remove());
System.out.println(objectMySingleLinkedQueue.toString());
4 总结
本文介绍了队列的基本概念,并且提供了简单的实现,队列属于一种特殊的线性表。“先来的数据先处理”是一种很常见的思路,所以队列的应用范围非常广泛,实际上我们能够直接接触到的队列的应用是要高于栈的应用的,比如各种并发队列,消息队列。另外在广度优先搜索算法中,通常就会从搜索候补中选择最早的数据作为下一个顶点。此时,在候补顶点的管理上就可以使用队列。
另外,关于Java 栈的数据结构,可以看这篇文章:数据结构—栈(Stack)的原理以及Java实现以及后缀表达式的运算。
上一篇: Java 中的数据结构:队列(顶部)
推荐阅读
-
数据结构 - 队列(Queue)原理和 Java 实现案例
-
Java 数据结构和算法 - 队列(详细实现)
-
windows下进程间通信的(13种方法)-摘 要 本文讨论了进程间通信与应用程序间通信的含义及相应的实现技术,并对这些技术的原理、特性等进行了深入的分析和比较。 ---- 关键词 信号 管道 消息队列 共享存储段 信号灯 远程过程调用 Socket套接字 MQSeries 1 引言 ---- 进程间通信的主要目的是实现同一计算机系统内部的相互协作的进程之间的数据共享与信息交换,由于这些进程处于同一软件和硬件环境下,利用操作系统提供的的编程接口,用户可以方便地在程序中实现这种通信;应用程序间通信的主要目的是实现不同计算机系统中的相互协作的应用程序之间的数据共享与信息交换,由于应用程序分别运行在不同计算机系统中,它们之间要通过网络之间的协议才能实现数据共享与信息交换。进程间通信和应用程序间通信及相应的实现技术有许多相同之处,也各有自己的特色。即使是同一类型的通信也有多种的实现方法,以适应不同情况的需要。 ---- 为了充分认识和掌握这两种通信及相应的实现技术,本文将就以下几个方面对这两种通信进行深入的讨论:问题的由来、解决问题的策略和方法、每种方法的工作原理和实现、每种实现方法的特点和适用的范围等。 2 进程间的通信及其实现技术 ---- 用户提交给计算机的任务最终都是通过一个个的进程来完成的。在一组并发进程中的任何两个进程之间,如果都不存在公共变量,则称该组进程为不相交的。在不相交的进程组中,每个进程都独立于其它进程,它的运行环境与顺序程序一样,而且它的运行环境也不为别的进程所改变。运行的结果是确定的,不会发生与时间相关的错误。 ---- 但是,在实际中,并发进程的各个进程之间并不是完全互相独立的,它们之间往往存在着相互制约的关系。进程之间的相互制约关系表现为两种方式: ---- (1) 间接相互制约:共享CPU ---- (2) 直接相互制约:竞争和协作 ---- 竞争——进程对共享资源的竞争。为保证进程互斥地访问共享资源,各进程必须互斥地进入各自的临界段。 ---- 协作——进程之间交换数据。为完成一个共同任务而同时运行的一组进程称为同组进程,它们之间必须交换数据,以达到协作完成任务的目的,交换数据可以通知对方可以做某事或者委托对方做某事。 ---- 共享CPU问题由操作系统的进程调度来实现,进程间的竞争和协作由进程间的通信来完成。进程间的通信一般由操作系统提供编程接口,由程序员在程序中实现。UNIX在这个方面可以说最具特色,它提供了一整套进程间的数据共享与信息交换的处理方法——进程通信机制(IPC)。因此,我们就以UNIX为例来分析进程间通信的各种实现技术。 ---- 在UNIX中,文件(File)、信号(Signal)、无名管道(Unnamed Pipes)、有名管道(FIFOs)是传统IPC功能;新的IPC功能包括消息队列(Message queues)、共享存储段(Shared memory segment)和信号灯(Semapores)。 ---- (1) 信号 ---- 信号机制是UNIX为进程中断处理而设置的。它只是一组预定义的值,因此不能用于信息交换,仅用于进程中断控制。例如在发生浮点错、非法内存访问、执行无效指令、某些按键(如ctrl-c、del等)等都会产生一个信号,操作系统就会调用有关的系统调用或用户定义的处理过程来处理。 ---- 信号处理的系统调用是signal,调用形式是: ---- signal(signalno,action) ---- 其中,signalno是规定信号编号的值,action指明当特定的信号发生时所执行的动作。 ---- (2) 无名管道和有名管道 ---- 无名管道实际上是内存中的一个临时存储区,它由系统安全控制,并且独立于创建它的进程的内存区。管道对数据采用先进先出方式管理,并严格按顺序操作,例如不能对管道进行搜索,管道中的信息只能读一次。 ---- 无名管道只能用于两个相互协作的进程之间的通信,并且访问无名管道的进程必须有共同的祖先。 ---- 系统提供了许多标准管道库函数,如: pipe——打开一个可以读写的管道; close——关闭相应的管道; read——从管道中读取字符; write——向管道中写入字符; ---- 有名管道的操作和无名管道类似,不同的地方在于使用有名管道的进程不需要具有共同的祖先,其它进程,只要知道该管道的名字,就可以访问它。管道非常适合进程之间快速交换信息。 ---- (3) 消息队列(MQ) ---- 消息队列是内存中独立于生成它的进程的一段存储区,一旦创建消息队列,任何进程,只要具有正确的的访问权限,都可以访问消息队列,消息队列非常适合于在进程间交换短信息。 ---- 消息队列的每条消息由类型编号来分类,这样接收进程可以选择读取特定的消息类型——这一点与管道不同。消息队列在创建后将一直存在,直到使用msgctl系统调用或iqcrm -q命令删除它为止。 ---- 系统提供了许多有关创建、使用和管理消息队列的系统调用,如: ---- int msgget(key,flag)——创建一个具有flag权限的MQ及其相应的结构,并返回一个唯一的正整数msqid(MQ的标识符); ---- int msgsnd(msqid,msgp,msgsz,msgtyp,flag)——向队列中发送信息; ---- int msgrcv(msqid,cmd,buf)——从队列中接收信息; ---- int msgctl(msqid,cmd,buf)——对MQ的控制操作; ---- (4) 共享存储段(SM) ---- 共享存储段是主存的一部分,它由一个或多个独立的进程共享。各进程的数据段与共享存储段相关联,对每个进程来说,共享存储段有不同的虚拟地址。系统提供的有关SM的系统调用有: ---- int shmget(key,size,flag)——创建大小为size的SM段,其相应的数据结构名为key,并返回共享内存区的标识符shmid; ---- char shmat(shmid,address,flag)——将当前进程数据段的地址赋给shmget所返回的名为shmid的SM段; ---- int shmdr(address)——从进程地址空间删除SM段; ---- int shmctl (shmid,cmd,buf)——对SM的控制操作; ---- SM的大小只受主存限制,SM段的访问及进程间的信息交换可以通过同步读写来完成。同步通常由信号灯来实现。SM非常适合进程之间大量数据的共享。 ---- (5) 信号灯 ---- 在UNIX中,信号灯是一组进程共享的数据结构,当几个进程竞争同一资源时(文件、共享内存或消息队列等),它们的操作便由信号灯来同步,以防止互相干扰。 ---- 信号灯保证了某一时刻只有一个进程访问某一临界资源,所有请求该资源的其它进程都将被挂起,一旦该资源得到释放,系统才允许其它进程访问该资源。信号灯通常配对使用,以便实现资源的加锁和解锁。 ---- 进程间通信的实现技术的特点是:操作系统提供实现机制和编程接口,由用户在程序中实现,保证进程间可以进行快速的信息交换和大量数据的共享。但是,上述方式主要适合在同一台计算机系统内部的进程之间的通信。 3 应用程序间的通信及其实现技术 ---- 同进程之间的相互制约一样,不同的应用程序之间也存在竞争和协作的关系。UNIX操作系统也提供一些可用于应用程序之间实现数据共享与信息交换的编程接口,程序员可以通过自己编程来实现。如远程过程调用和基于TCP/IP协议的套接字(Socket)编程。但是,相对普通程序员来说,它们涉及的技术比较深,编程也比较复杂,实现起来困难较大。 ---- 于是,一种新的技术应运而生——通过将有关通信的细节完全掩盖在某个独立软件内部,即底层的通讯工作和相应的维护管理工作由该软件内部来实现,用户只需要将通信任务提交给该软件去完成,而不必理会它的具体工作过程——这就是所谓的中间件技术。 ---- 我们在这里分别讨论这三种常用的应用程序间通信的实现技术——远程过程调用、会话编程技术和MQSeries消息队列技术。其中远程过程调用和会话编程属于比较低级的方式,程序员参与的程度较深,而MQSeries消息队列则属于比较高级的方式,即中间件方式,程序员参与的程度较浅。 ---- 4.1 远程过程调用(RPC)
-
标题:一文搞定Redis面试,附Redis面试大纲+常见Redis面试题-一、基础篇 快速上手 ①. 什么是redis ②. 为什么使用redis ③. 安装 ④. 基本使用(常见数据结构的命令) Java操作redis ①. Jedis ②. SpringBoot 启动redis的方式 ①. 配置文件 ②. 生产环境启动方案 二、进阶篇 redis实现session共享 redis缓存的使用 ①. 注解式 ②. Spring Cache 数据库和缓存双写一致性问题——穿透 redis实现附近的人 redis实现计数器 redis事务 redis分布式锁的使用 redis集群 redis实现延时队列 redis实现限流 redis实现布隆过滤器 发布订阅 redis优化 三、原理篇 redis单线程为什么性能好 数据类型的底层实现 持久化机制 过期策略 内存淘汰 redis优化 哨兵模