专栏首页星月小站Java实现基本数据结构(三)——队列

Java实现基本数据结构(三)——队列

文章目录

前言

  阅读本文前,最好先学习顺序表和栈的基本操作和实现原理,也就是弄清楚数组和栈的原理,点击Java实现基本数据结构(一)——数组Java实现基本数据结构(二)——栈。先学习前置内容,学习效果更好哦!

队列简介

  在数据结构中,队列和栈(Java实现基本数据结构(二)——栈)类似,也是一种线性表的结构。不同的地方在于栈只允许数据从一端进行插入和删除,而队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。根据这一种操作限制,我们将队列入队(插入操作)的一端称为队尾,出队(删除操作)的一端称为队首。所以队列也被称作为先进先出表(FIFO:First In First Out)。如下面图片所示,展示了一个队列的结构示意,入队和出队的操作示意:

            图1 队列结构示意

            图2 出队操作示意

            图3 入队操作示意图

初识队列的应用

  队列在计算机系统中也是一个应用非常广泛的数据结构。队列在设计程序中用的非常频繁,比如用用户用键盘输入内容后在显示器上显示出来这一过程,其实就是对列的典型应用,比如你输入了一个英文单词god,应用队列可以让显示和你的输入顺序一致,先输入的先输出,否则显示出dog可就真让人恼火了。   还有,我们会在用电脑时,偶尔会出现电脑处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算重启时。突然他像酒醒了一样,把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。   在队列这种数据结构的具体实现上,一般也有两种实现方式:线性存储和链接存储(链表)。也就是使用数组和链表这两种数据结构都可以实现队列。   下面我们分别对这两种方法进行实现。

在Java中使用线性存储实现队列结构

  在Java语言中,使用线性存储实现队列,和栈的实现思路一样,实际上就是使用数组这样一种结构,并对其操作进行限制来实现队列。也就是说实际上,对比数组,线性存储队列对应的操作就是数组的子集。   也就是说,我们实际上可以把队列这种结构看成一个特殊的数组,这个数组只能从一端添加元素,这一端称之为队尾(rear);却只能从另外一端取出元素,这一端称之为队首(front)。   和数组一样,线性存储的队列在使用时是静态分配的,就是使用的时候,内存已经以数组的形式开辟了一段空间,所以在初始化的时候,我们需要给定一个长度。

设计队列的功能

  根据队列这种数据结构的特点,在队列的实现上,我们只需要设计以下几个功能即可:   (1)入队(enqueue)操作:将一个元素插入队列中,实际上就是插入数组的尾部。   (2)出队(dequeue)操作:将队首元素出队,实际上就是将数组头部的元素删除,并返回这个元素。   (3)查看队首元素(getFront)操作:将队首的元素返回给用户,实际上就是返回数组头部元素。   (4)返回栈的元素个数。   (5)判断栈是否为空。   因为我们前面说过,队列这种数据结构可以有两种实现方式,一种是线性存储,即通过数组实现;一种是链接存储,即通过链表实现。为了方便后续的实现,我们首先定义一个Queue接口,后面分别用数组和链表来实现这个接口即可。

实现Queue接口

  按照上一小节的设计,我们直接在接口中约定这些功能即可。

public interface Queue<E> {
	
	int getSize();
	boolean isEmpty();
	void enqueue(E e);
	E dequeue();
	E getFront();
	
}

通过数组实现Queue接口

  为了更好的让本系列文章之间更好的串联知识点,本节实现的线性存储队列,将不使用JDK提供的ArrayList,使用Java实现基本数据结构(一)——数组中已经实现好的ArrayList类作为队列的存储结构。实际上,使用JDK提供的ArrayList类实现队列的方法是一样的,大家可以自行练习。   由于队列的功能比较简单,而且和栈的操作类似,这里直接对队列进行代码实现,相关细节在注释中体现。

public class ArrayQueue<E> implements Queue<E> {  // 泛型
	
	// 定义一个数组用来存储队列中的元素
	private ArrayList<E> array;

	// 无参构造,直接使用ArrayList类中定义的无参默认值
	public ArrayQueue() {
		array = new ArrayList<E>();
	}

	// 有参构造,指定初始队列容量
	public ArrayQueue(int capacity) {
		array = new ArrayList<E>(capacity);
	}
	
	// 返回栈的元素个数,其实就是返回array的元素个数,调用array中的getSize()方法即可
	@Override
	public int getSize() {
		return array.getSize();
	}

	// 返回栈的总体容量大小,同上,就是返回array的容量空间
	public int getCapacity() {
		return array.getCapacity();
	}
	
	// 返回栈是否为空,其实就是返回array是否为空,调用array中的isEmpty()方法即可
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	/* 
	 * 将元素e入队,实际上就是向数组中添加元素。
	 * 由于队列的特性,只能从数组一端添加元素,为了高效,就限定只能从数组尾部添加即可。
	 * 用户调用enqueue函数时,就永远只能从数组尾部插入数据,满足了队列的条件。
	 */
	@Override
	public void enqueue(E e) {
		array.addLast(e);
	}

	/*
	 * 从队列将队首元素出队,其实就是将队首元素删除并返回。
	 * 由于添加的时候是从数组尾部添加的,所以这里只需要从数组头部删除元素即可。
	 * array中的删除函数,我们已经完成了将删除的元素返回,直接使用即可。
	 */
	@Override
	public E dequeue() {
		return array.removeFirst();
	}

	/*
	 * 查看队首元素,就是将数组头部的元素返回即可。
	 * 由于ArrayList中我们没有定义一个直接返回数组头部的函数。
	 * 所以需要使用array.get()函数,再将头部索引0传入即可。
	 */
	@Override
	public E getFront() {
		return array.get(0);
	}
	
	// 覆盖toString函数,便于输出栈的信息
	@Override
	public String toString() {
		
		StringBuilder res = new StringBuilder();
		res.append("Queue: front [");
		for (int i = 0; i < array.getSize(); i++) {
			res.append(array.get(i));
			if (i != array.getSize() -1) {
				res.append(", ");
			}
		}
		res.append("] rear");
		return res.toString();

	}
	
}

  可以看到,栈的代码其实就是对数组的限制应用,下面我们写一个测试,对我们实现的栈进行验证。

public class Main {

	public static void main(String[] args) {
		
		ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
		for (int i = 0; i < 5; i++) {
			queue.enqueue(i);
		}
		System.out.println(queue);
		
		int a = queue.dequeue();
		System.out.println("delect " + a);
		System.out.println(queue);
		
		int b = queue.getFront();
		System.out.println("front is " + b);
		System.out.println(queue);
		
		queue.enqueue(100);
		System.out.println(queue);
		
	}

}

  输出结果如下:

  可以看到,我们成功验证了之前所完成的队列,满足了先进先出原则。

数组实现的一般队列时间复杂度分析

  根据我们刚才的代码和实现思路,可以分析出这个数组队列实现的时间复杂度: (1)在enqueue操作中,其实就是向数组的尾部添加元素,这个时间复杂度为O(1),由于数组类底层的自动扩容触发次数不会太多,所以我们可以将enqueue操作的时间复杂度均摊地看做O(1),效率还是较高的。 (2)在dequeue操作中,其实就是将数组索引为0的位置上元素删除,也就是队首元素出队,此时由于我们设计的ArrayList类底层代码中,一个元素删除后,数组中被删除元素后面的所有元素都要向前移动1位。所以这个操作的时间复杂度和数组删除元素的时间复杂度一样,都为O(n)。这个时间复杂度不是一个高效的操作,所以有必要对其进行优化。

数组队列的优化

  由于之前的实现中,我们为了保证队首元素的索引始终为0,以便于快速找到队首,所以使用的数组类中,在删除操作是会将数组元素前移一位。这就导致了时间复杂度的增高。那么怎么对这个操作进行优化呢?   我们其实可以加入两个指针,一个指针是front,指向目前数组的第一个元素,第二个指针是rear,指向目前数组的最后一个元素后面的一个空间。这样我们就可以根据这两个指针的值进行索引,快速找到队首和队尾元素,进行入队和出队操作,而不需要对数组的元素进行迁移,降低了时间复杂度,实现思路如下图所示:

  由上图,可以看出,我们加入两个指针之后,直接在front位置进行出队操作,出队后将front指针后移,就又指向了数组第一个元素。   在rear处可以直接进行入队操作,这样插入的元素就是数组最后一个元素了,入队后将rear指针后移,就又指向了数组最后一个元素的后一个空间。

  这种方式虽然解决了出队操作时间复杂度高的问题,但是细心的同学可能也发现了,这种方式带来了另外的烦恼。我们先看一张网图,下图展示了该结构下队列的入队和出队操作:

  当我们多次进行入队和出队操作后,会发现由于数组不会自动移动元素,很快,我们的数组就会溢出,而且已经出队的元素所占用的空间,永远不会再次被利用,就都浪费掉了。

  虽然这里我们可以设计一个扩容的函数,在数组满了之后对数组进行扩容,但是还是会有很多空间被浪费掉,这也不算是一个好的队列实现,于是我们就需要引出一个新的概念——循环队列

循环队列

  循环队列是为了解决普通数组队列的问题而设计的一种抽象形式,其实现仍然是利用数组这种基础数据结构,但是我们在循环队列中,将队列,也就是数组看成一个首尾相连的环,来循环利用。那么如何看成一个环呢?其实就是使用指针,如下图所示,定义两个指针,一个为front代表队首的位置,一个为tail代表队尾的位置,初始化的时候,定义一个数组data[capacity],容量为capacity,队首与队尾同时指向data[0]。

  当有元素开始入队的时候,tail指针开始后移,始终指向队尾元素的下一个空闲空间;当有元素出队的时候,front指针后移,始终指向第一个元素。front和tail指针追赶的过程,就是数组出队入队的过程。

  当tail指针走到了数组的最后一个位置data[capacity-1]的时候,如果还有元素要入队,这时,tail指针直接指到data[0]位置(如果数组没有满),循环的概念就出来了。如下图所示。

  此时tail后面又有空间可以使元素继续入队,但是如果tail后面没有空间了,此时队列已满,无法继续入队。就需要对队列进行扩容操作,扩容操作和数组的扩容原理是一样的,新建一个更大的数组将元素拷贝过去即可。

  看到这里,可能有的读者会问,我们如何控制指针回到数组头部,使其一直循环运行?其实只需要对tail指针进行一下数学运算即可:

  • (tail + 1) % capacity:入队一个元素时,tail指针应该移动到的索引。
  • (front + 1) % capacity:出队一个元素时,front指针应该移动到的索引。

  为了防止元素覆盖和冲突,我们定义循环队列已满的情况为(tail + 1) % capacity == front,即tail再后移一格就和front重复了,tail后面没有空闲空间了。此时需要扩容。如果出队之后(front + 1) % capacity ==tail,此时我们认为队列是空的。

循环队列的实现

  和普通数组队列一样,这里直接使用前文设计好的Queue接口进行实现,功能一样,只是为了实现循环的概念,在循环队列的实现中,需要使用基础数组,从底层重新实现各种操作。

package Queue;

public class LoopQueue<E> implements Queue<E>{
	
	// 定义一个数组,用来存储元素
	private E[] data;
	// 定义队首和队尾指针
	private int front, tail;
	// 定义一个记录队列中元素数量的变量
	private int size;
	
	// 构造函数,用户可以自定义初始容量
	public LoopQueue(int capacity) {
		data = (E[])new Object[capacity];
		front = 0;
		tail = 0;
		size = 0;
	}
	
	// 无参构造,容量初始默认为10	
	public LoopQueue() {
		this(10);
	}
	
	// 获取当前队列的总容量
	public int getRealCapacity() {
		// 由于循环队列中需要预留一个空间保证入队时tail不和front重合,所以总容量是数组长度-1
		return data.length - 1;
	}

	// 获取当前队列中元素数量
	@Override
	public int getSize() {
		return size;
	}

	// 判断当前队列是否为空
	@Override
	public boolean isEmpty() {
		return front == tail;
	}

	// 入队操作
	@Override
	public void enqueue(E e) {
		
		// 入队之前判断是否队列已满,如果队列已满就先扩容再入队
		if ((tail + 1) % data.length == front)
			resize(data.length * 2);
		data[tail] = e;
		size ++;
		// 更新队尾指针的索引
		tail = (tail + 1) % data.length;
		
	}
	
	// 私有的扩容函数,不对外开放
	private void resize(int newCapacity) {
		
		// 建一个新的数组,空间是newCapacity
		E[] newData = (E[])new Object[newCapacity];
		// 将原本队列中的元素按顺序拷贝进新的数组,由于有指针定义队首和队尾,所以直接从newData[0]开始拷贝即可
		for (int i = 0; i < size; i++) 
			newData[i] = data[(front + i) % data.length];
		// 移动指针将队列的存储数组变更为newData
		data = newData;
		// 归位队首队尾指针
		front = 0;
		tail = size; // tail指向最后一个元素的下一个空间
		
	}

	// 出队队首元素并返回改元素
	@Override
	public E dequeue() {
		
		// 首先判断队列是否为空
		if (isEmpty()) 
			throw new IllegalArgumentException("Queue is empty!");
		// 记录队首元素,以便后续返回
		E ret = data[front];
		// 移除队首元素,指针后移,维护size
		data[front] = null;
		front = (front + 1) % data.length;
		size --;
		
		// 为了更好地利用内存空间,如果出队后,队列中的元素数量只占用了数组总容量的1/4,进行缩容操作
		// 这里需要注意的是,缩容后的容量不能为0
		if (size == getRealCapacity() / 4 && getRealCapacity() / 2 != 0)
			resize(getRealCapacity() / 2);
		
		return ret;
		
	}
	
	// 看一下队首元素
	@Override
	public E getFront() {
		
		// 首先判断队列是否为空
		if (isEmpty()) 
			throw new IllegalArgumentException("Queue is empty!");
		
		return data[front];
	}
	
	// 为了方便打印队列信息,重写toString函数
	@Override
	public String toString() {
		
		StringBuilder res = new StringBuilder();
		res.append("LoopQueue: front[");
		for (int i = front; i != tail; i = (i + 1) % data.length) {
			res.append(data[i]);
			if ((i + 1) % data.length != tail) {
				res.append(", ");
			}
		}
		res.append("] tail");
		return res.toString();
		
	}
	
}

  对循环队列进行测试:

public class Main {

	public static void main(String[] args) {
		
		LoopQueue<Integer> queue = new LoopQueue<Integer>();
		for (int i = 0; i < 5; i++) {
			queue.enqueue(i);
		}
		System.out.println(queue);
		
		int a = queue.dequeue();
		System.out.println("delect " + a);
		System.out.println(queue);
		
		int b = queue.getFront();
		System.out.println("front is " + b);
		System.out.println(queue);
		
		queue.enqueue(100);
		System.out.println(queue);
		
	}

}

  测试结果为:

  可以看出,我们设计的循环队列已经可以正常工作了!   最后,我们再对循环队列的各操作时间复杂度进行一下展示。

  至此,基于数组实现的队列我们就已经全部讲解完毕了!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java实现基本数据结构(二)——栈

    阅读本文前,最好先学习顺序表的基本操作和实现原理,也就是弄清楚数组的原理,点击Java实现基本数据结构(一)——数组学习前置内容。学习效果更好哦!

    星如月勿忘初心
  • spring框架通过xml以及注解方式注册BeanDefinition的流程全链路分析

    在上一章节中,主要介绍了SpringIoC、依赖注入和Spring中的Bean与BeanDefinition。可能部分读者还是比较迷茫,BeanDefiniti...

    星如月勿忘初心
  • Java后端面试学习知识总结

    本系列文章是在学习Java后端知识中进行总结与考证的结晶,梳理了Java后端面试与学习的核心知识体系,并对核心知识进行了讲解,属于BFS型知识讲解,在总结的过程...

    星如月勿忘初心
  • 剑指 offer代码解析——面试题29数组中出线次数超过一半的数字

    题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 分析:本题最直观的思路就是分别统计数组中每个数出现的次数,然后求出最大值,判断是否超过...

    大闲人柴毛毛
  • Java漫谈6

    今天这篇想聊聊数组。 在聊数组之前先聊个别的,如果想在Java中实现一个 数字-月份 转换,那我该怎么做呢?就比如数字1代表了一月份,数字2代表了二月份…数字1...

    用户1335799
  • Java中的数组(基础篇六)

    在学习数组之前我们先来了解一下容器,生活中的容器比如水杯是用来装水的,衣柜是装衣服的,Java中的容器是用来存储数据的,将多个数据存储到一起,每个数据称为该容器...

    故里
  • 数组

    1、 一维数组的定义和使用 通过对前面知识的学习,我们已经知道如何定义和使用一个一个的各种变量,但总有不够用的时候。举个例子,我要记录一个班32个同学C语...

    编程范 源代码公司
  • Java SE | 基础语法day04

    剑走天涯
  • Excel VBA解读(153): 数据结构——基本的数组操作

    创建了一个可以容纳6个Long型数据的数组,第一个元素的索引值为0,最后一个元素的索引值为5,如下图1所示。

    fanjy
  • [Linux]shell基础教程3-数组

    在之前的 shell基础教程1-变量、字符串、数组、注释 已经写过了,现在这个增加一些例子。

    祥知道

扫码关注云+社区

领取腾讯云代金券