java队列

Java 实现队列

介绍

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

Java 实现

这次使用顺序队列实现。(使用数组),

why?为什么不直接使用顺序表作为底层容器,因为入队操作执行顺序表尾插入,时间复杂度为O(1)

O(1) 普通语句,相互操作,时间复杂度为O(1)

出对操作执行表头删除操作,时间复杂度为O(n),因为涉及到一个循环遍历,移动,由于时间复杂度高,此时直接想方法将时间复杂度降低为O(1) ,即,用双指针解决。即front和rear两个解决

时间复杂度 O(n) 涉及一层循环,此时时间复杂度为O(n)

又因为直接更改下标,会导致空间的浪费,(出队操作)此时,为了减少空间的浪费,将队列设计为循环队列,目的,避免假满现象的出现。

空队列的时候 front = rear = 0

入队 front = 0 rear = 1

此时继续入队 front = 0 rear = 2

出队 front = rear = 2 两者相等

继续入队,front=2 rear = 3

不断的循环,总有一个为空,即rear

到队满 即 front = 2 rear = 1;

队满的判断 front = (rear + 1)% size

real永远为空

代码

接口

package demo.mingm.struct.queue;

/**
 * 接口 队列
* @author ming
* @date 2018/11/17
*/
public interface Queue<T> {
	// 定义数组长度
	public static final int DEFAULT_SIZE = 10;
	// 返回队列长度
	int size();
	// 判断队列是否为空
	boolean isEmpty();
	// 判断队列是否已满
	boolean isFull();
	// 入队, 成功true 错误false
	boolean add(T data);
	// offer 入队,和add方法不同的是,如果队满,或传入的为空,将会抛出错误,不会自动扩充
	boolean offer(T data);
	// 返回队头元素,不执行删除操作,为空 返回null
	T peek();
	// 返回队头元素,如果为空,将会抛出异常
	T element();
	// 出队,执行删除操作,若为空,返回null
	T poll();
	// 出队,执行删除操作,若为空,抛出异常
	T remove();
	// 清空队列
	void cleameQueue();
	
}

实现接口的类

package demo.mingm.struct.queue;
import java.util.Arrays;
import java.util.Vector;
public class SeqQueue<T> implements Queue<T> {
	private T[] elementData;	// 储存数据的数组
	private int size;	// 储存大小
	private int front, rear;	// 指针指向数组的元素,一个前,一个后
	private int real;
	
	public SeqQueue() {
		elementData= (T[]) new Object[DEFAULT_SIZE];
		// 指针的初始化
		this.front = 0;
		this.rear = 0;
		this.size = 0;
	}
	
	public SeqQueue(int length) {
		elementData = (T[]) new Object[length];
		this.front = 0;
		this.rear = 0;
		this.size = 0;
	}
	
	public int getSize() {
		return this.size;
	}
	
	public int getFront() {
		return this.front;
	}
	
	public int getRear() {
		return this.rear;
	}
	
	public void setSize(int size) {
		this.size = size;
	}
	
	public void setFront(int front) {
		this.front = front;
	}
	
	public void setRear(int rear) {
		this.rear = rear;
	}
	
	// 获取队列长度
	@Override
	public int size() {
		return this.getSize();
	}

	// 判断队列是否为空
	@Override
	public boolean isEmpty() {
		return this.getRear() == this.getFront();
	}
	
	// 判断队列是否已满
	@Override
	public boolean isFull() {
		return this.getFront() == (this.getRear() + 1) % this.elementData.length;
	}
	
	// 入队操作,如果不满,自动扩充数组
	@Override
	public boolean add(T data) {
		if(this.isFull()) {
			Arrays.copyOf(elementData, elementData.length*2);
		}
		// 是否插入空
		if(data == null)
			return false;
		// 添加data
		elementData[this.getRear()] = data;
		// 移动指针
		this.rear++;	// 创造单向队列
		this.size++;
		return true;
	}

	@Override
	public boolean offer(T data) {
		if(this.isFull() || data == null) {
			throw new NullPointerException("error 1");
		}
		// 添加data
		this.elementData[this.getRear()] = data;
		// 移动指针
		this.real = (this.real + 1)%elementData.length;	// 创造循环队列
		this.size++;
		return true;
	}

	// 返回队头元素,不删除
	@Override
	public T peek() {
		if(this.isEmpty())
			return null;
		return this.elementData[this.getFront()];
	}

	// 返回队头元素
	@Override
	public T element() {
		if(this.isEmpty())
			throw  new NullPointerException("error 2");
		return this.elementData[this.getFront()];
	}

	// 出队
	@Override
	public T poll() {
		if (this.isEmpty())
			return null;
		T tmp = this.peek();
		// 循环队列
		this.front = (this.getFront() + 1 ) % this.elementData.length;
		return tmp;
	}

	// 出队
	@Override
	public T remove() {
		if (this.isEmpty())
			throw  new NullPointerException("error 3");
		T tmp = this.peek();
		// 循环队列
		this.front = (this.getFront() + 1 ) % this.elementData.length;
		return tmp;
	}

	// 清空
	@Override
	public void cleameQueue() {
		this.real = 0;
		this.front = 0;
	}
}

www.iming.info

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

47670
来自专栏python读书笔记

《python算法教程》Day8 - 构建二分搜索树二分搜索树介绍二分搜索树创建代码

今天是《python算法教程》的第8篇读书笔记,笔记的主要内容是构建二分搜索树。 二分搜索树介绍 若要对一组有序值中执行操作(如查找),二分搜索法是一个优秀的选...

386130
来自专栏一枝花算不算浪漫

HashMap中的resize以及死链的情况

443120
来自专栏企鹅号快讯

什么是B+Tree

推荐阅读 微服务: springboot系列教程学习 源码:Javaweb练手项目源码下载 调优:十五篇好文回顾 面试笔试:面试笔试整理系列 B+Tree的定义...

23760
来自专栏程序员宝库

JDK 源码中的一些“小技巧”

均摘选自JDK源码 1 i++ vs i-- String源码的第985行,equals方法中: while (n--!= 0) { if...

35550
来自专栏高性能服务器开发

什么是B+Tree

B+Tree的定义 B+Tree是B树的变种,有着比B树更高的查询性能,来看下m阶B+Tree特征: 1、有m个子树的节点包含有m个元素(B-Tree中是m-1...

35580
来自专栏数据结构与算法

cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

10410
来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

18320
来自专栏小樱的经验随笔

【Java数据结构学习笔记之三】Java数据结构与算法之队列(Queue)实现

  本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点: 队列的抽象数据类型 顺序队列的设计与实现 链式队列的设计与实现 队列应用的简单举例 优先队列的设...

41270
来自专栏IMWeb前端团队

JS中的非可变性

非可变性是函数式编程的一个核心规则,对于面向对象编程也有很多用处。本文为参考sitepoint(参考链接1)中的文章后所记录的一些主要内容。 参考链接1:...

19550

扫码关注云+社区

领取腾讯云代金券