`
suhuanzheng7784877
  • 浏览: 702334 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Ff8d036b-05a9-33b5-828a-2633bb68b7e6
读金庸故事,品程序人生
浏览量:47699
社区版块
存档分类
最新评论

Java基础复习笔记06数据结构-队列

阅读更多

1.       队列

队列又是一种比较特殊的线性表,和栈一样在线性表的基础上进行了一些限制操作。就是队列了。顾名思义,队列就是咱们排队买火车票一样,排在最前面的先买到,排到后面的后买到。先进先出、后进后出。

 

2.       队列的操作

队列的操作一般包括:进队列、出队列,访问队列头元素、删除队列头元素、判断队列是否为空、获得队列大小这些核心操作。SunJava的队列规定了一个规范、反映出来的的就是java.util.Queue,实现了此接口的所有方法,相当于“你按照SunJava规范为自己写了一个符合规范的队列实现类”。

3.       队列的使用场景

队列的使用场景其实个人感觉比栈要广泛一些,比如开发网络服务中间件,处理并发消息的时候就需要将这些消息组成队列的方式一个一个处理,再比如对象池的应用,底层完全可以做成一个对象队列,将一个用完的对象放回池中后,就是放到等待队列中,先归还的对象,下次再使用的时候就比后放入的对象优先调用,因为先归还的对象肯定是休息了很久了,该对象应当回收的资源也都回收了。

4.       队列的顺序实现

和栈结构一样队列也有两种实现方式,先来看顺序的实现方式,顺序实现方式就是利用数组,记录当前队列头标记nowTopIndex以及下一个、新的队列结尾元素的标记newTailIndex

程序如下:

package dateStructer.queue;

/**
 * 顺序队列
 * 
 * @author liuyan
 * @param <E>
 */
public class MyArrayQueue<E> implements Queue<E> {

	// 默认大小
	private final static int DefSize = 32;

	// 临时数组
	private Object[] objects;

	// 当前队列头元素索引
	private int nowTopIndex;

	// 下一个队列新元素的索引
	private int newTailIndex;

	public MyArrayQueue() {
		objects = new Object[DefSize];
	}

	/**
	 * 添加元素
	 */
	@Override
	public boolean add(E e) {

		int elementSize = newTailIndex - nowTopIndex;

		if (elementSize == 0 && newTailIndex == 0) {
			objects[0] = e;
			nowTopIndex = 0;
			newTailIndex = 1;
			return true;
		}

		objects[newTailIndex++] = e;

		return true;
	}

	/**
	 * 获取队头元素
	 */
	@Override
	public E element() {
		return (E) objects[nowTopIndex];
	}

	/**
	 * 返回头元素,不删除头元素
	 */
	@Override
	public E peek() {
		return (E) objects[nowTopIndex];
	}

	/**
	 * 返回头元素,删除头元素
	 */
	@Override
	public E poll() {

		if (objects[nowTopIndex] == null) {
			return null;
		}

		E date = (E) objects[nowTopIndex];
		objects[nowTopIndex++] = null;
		return date;
	}

	@Override
	public E remove() {
		if (nowTopIndex == 0) {
			return null;
		}
		E date = (E) objects[nowTopIndex];
		objects[nowTopIndex--] = null;
		return date;
	}

	@Override
	public void clear() {
		Arrays.fill(objects, null);
		nowTopIndex = 0;
		newTailIndex = 0;
	}

	@Override
	public boolean contains(Object object) {
		for (int i = 0; i < objects.length; i++) {
			if (object == objects[i]) {
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean isEmpty() {
		int elementSize = newTailIndex - nowTopIndex;
		return elementSize == 0;
	}

	@Override
	public int size() {
		return newTailIndex - nowTopIndex;
	}

	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");

		int elementSize = newTailIndex - nowTopIndex;

		for (int i = nowTopIndex; i < newTailIndex; i++) {

			str.append("[" + objects[i].toString() + "],");

		}

		if (elementSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
}

 测试代码如下

	public static void main(String[] args) {
		MyArrayQueue<String> myQueue = new MyArrayQueue<String>();
		myQueue.add("1");
		myQueue.add("2");
		myQueue.add("3");
		System.out.println(myQueue.toString());
		String e = myQueue.poll();
		System.out.println(e);
		System.out.println(myQueue.toString());
		myQueue.add("4");
		e = myQueue.peek();
		System.out.println("是否为空队列" + myQueue.isEmpty());
		System.out.println("队列大小" + myQueue.size());
		System.out.println(e);
		System.out.println(myQueue.toString());
		System.out.println("是否包含相关元素" + myQueue.contains("1"));
		System.out.println("是否包含相关元素" + myQueue.contains("2"));
		myQueue.clear();
		System.out.println("是否为空队列" + myQueue.isEmpty());
	}

 运行后效果如下

[[1],[2],[3]]
1
[[2],[3]]
是否为空队列false
队列大小3
2
[[2],[3],[4]]
是否包含相关元素false
是否包含相关元素true
是否为空队列true

5.       队列的链表实现

相对于顺序实现方式,链式实现相对比较简单,只需要利用Node结构,记录下队列的头Node和尾巴Node,在记录下元素个数就可以了。算法如下

package dateStructer.queue;

/**
 * 实现自己的队列
 * @author liuyan
 * @param <E>
 */
public class MyQueue<E> implements Queue<E> {
	
	/**
	 * 双向链表结构
	 */
	public class LinkNode {

		// 真正的数据域
		private E date;

		// 记录上一个节点
		private LinkNode prevLinkNode;

		// 记录下一个节点
		private LinkNode nextLinkNode;

		public LinkNode() {

		}

		public LinkNode(E date, LinkNode prevLinkNode, LinkNode nextLinkNode) {
			this.date = date;
			this.prevLinkNode = prevLinkNode;
			this.nextLinkNode = nextLinkNode;
		}
	}
	
	// 结点个数
	private int nodeSize;

	// 头结点
	private LinkNode headNode;

	// 尾巴节点
	private LinkNode tailNode;
	
	public MyQueue(){
		headNode = null;
		tailNode = null;
	}
	
	/**
	 * 添加元素
	 */
	@Override
	public boolean add(E element) {
		if (nodeSize == 0) {
			headNode = new LinkNode(element, null, tailNode);
		}else {

			if (tailNode == null) {
				tailNode = new LinkNode(element, headNode, null);
				headNode.nextLinkNode = tailNode;
				nodeSize++;
				return true;
			}

			LinkNode linkNode = tailNode;
			tailNode = new LinkNode(element, linkNode, null);
			linkNode.nextLinkNode = tailNode;

		}
		nodeSize++;
		return true;
	}
	
	/**
	 * 访问队列头元素
	 */
	@Override
	public E element() {
		return headNode.date;
	}
	
	/**
	 * 返回头元素,不删除头元素
	 */
	@Override
	public E peek() {
		return headNode.date;
	}

	/**
	 * 返回头元素,删除头元素
	 */
	@Override
	public E poll() {
		
		LinkNode headNodeTemp = headNode;
		E date = headNodeTemp.date;
		if(headNode.nextLinkNode == null){
			headNode.date = null;
			headNode = null;
			nodeSize--;
			return date;
		}else{
			headNode = headNode.nextLinkNode;
			if(headNode == tailNode){
				tailNode = null;
			}
		}
		
		nodeSize--;
		
		return headNodeTemp.date;
	}
	
	/**
	 * 清除所有元素
	 */
	@Override
	public void clear() {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (linkNodeNowTemp != tailNode && linkNodeNowTemp != headNode) {
				linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
				linkNodeNowTemp.prevLinkNode.nextLinkNode = null;
				linkNodeNowTemp.prevLinkNode.prevLinkNode = null;
				linkNodeNowTemp.prevLinkNode.date = null;
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == tailNode) {
				linkNodeNowTemp.prevLinkNode = null;
			} else if (linkNodeNowTemp == headNode) {
				linkNodeNowTemp.nextLinkNode = null;
			}

		}
		headNode = null;
		tailNode = null;
		nodeSize = 0;

	}
	
	/**
	 * 判断是否存在
	 */
	@Override
	public boolean contains(Object object) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (object == linkNodeNowTemp.date) {
				return true;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}

		return false;
	}
	
	/**
	 * 队列是否为空
	 */
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return nodeSize == 0;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return nodeSize;
	}
	
	/**
	 * 根据索引号查找节点
	 * 
	 * @param index
	 * @return
	 */
	public LinkNode findLinkNodeByIndex(int index) {

		LinkNode linkNodeNowTemp = headNode;

		for (int i = 0; i < nodeSize; i++) {

			if (i == index) {
				return linkNodeNowTemp;
			}

			linkNodeNowTemp = linkNodeNowTemp.nextLinkNode;
		}
		return null;
	}
	
	@Override
	public String toString() {

		StringBuffer str = new StringBuffer("[");
		LinkNode linkNode = null;
		for (int i = 0; i < nodeSize; i++) {

			linkNode = findLinkNodeByIndex(i);

			str.append("[" + linkNode.date + "],");

		}

		if (nodeSize > 0) {
			return str.substring(0, str.lastIndexOf(",")) + "]";
		}

		return str.append("]").toString();
	}
	
}

 测试代码和顺序实现的测试代码相同,在此不再赘述。

6.       总结

队列是一种比较简单线性表,使用场景很多,尤其是开发自己的类库层次。使用队列这种结构存储临时数据的情况比较多。顺序实现与链表实现各有利弊。一般元素个数比较固定用顺序实现方式,如果使用元素个数变化十分频繁,还是使用链表效率好一些。顺序实现方式存在一种隐患就是“假满现象”,所以顺序实现还可以采用循环队列,循环队列的原理就是如果头索引=尾索引,并且头索引不等于0,并且此时数组大小已经都用完了,那么将头、尾索引都置为0即可,这里就不给出代码了。当然以上2种方式的实现都是没有做安全检查的,而且顺序实现元素最大个数也只能拥有和数组一样的元素个数。Java有个常用的队列java.util.concurrent.ConcurrentLinkedQueue

  • 大小: 22.3 KB
分享到:
评论

相关推荐

    Java基础复习笔记09数据结构-哈夫曼树

    ### Java基础复习笔记09数据结构-哈夫曼树 #### 1. 哈夫曼树概述 哈夫曼树是一种特殊的二叉树,它在计算机科学领域有着广泛的应用,尤其是在数据压缩方面。哈夫曼树也被称为最优二叉树,其构建原则是使得带权路径...

    Java基础复习笔记04数据结构-线性表

    ### Java基础复习笔记04数据结构-线性表:深入解析与应用 #### 线性表的概念 线性表是计算机科学中最基础的数据结构之一,它由一系列相同类型的元素组成,这些元素按照一定的顺序排列,形成一个有序的序列。在逻辑...

    数据结构高分笔记part1

    2. **线性数据结构**:线性数据结构如数组、链表、栈和队列是学习的基础。笔记可能详细讲解了数组的连续存储和随机访问特性,链表的动态内存分配和指针操作,栈的“后进先出”(LIFO)原则,以及队列的“先进先出”...

    JavaSE基础复习笔记

    - **队列**:队列是一种先进先出(FIFO)的数据结构。Java中提供了多种队列实现,如 `Queue` 接口及其子类。 - **树**:树是一种非线性的数据结构,广泛应用于各种场景。二叉树是最常见的树形结构之一,包括二叉...

    JAVA试题 JAVA复习题 JAVA复习笔记

    本压缩包集合了多种JAVA试题与复习笔记,涵盖了基础理论、编程实践以及解题技巧等多个方面,旨在帮助Java学习者巩固知识,提升编程能力。 1. **Java基础** - **数据类型**:包括基本数据类型(如int、char、...

    大学笔试专用,计算机数据结构超快星人复习笔记

    这份“大学笔试专用,计算机数据结构超快星人复习笔记”旨在帮助学生在短时间内掌握数据结构的基本概念和重要算法,特别适合应对笔试考试。 首先,笔记强调了对编程思想的理解,这是学习数据结构的基础。编程思想...

    Java学习笔记&工作经验总结.rar

    这份压缩包文件"Java学习笔记&工作经验总结.rar"包含了多个PDF文档,分别涵盖了Java的基础知识、高级特性、数据结构以及学员的学习总结,是深入理解Java编程的宝贵资料。 1. **Java SE基础全程学习笔记.pdf**: 这...

    408考试数据结构高分笔记2019版(天勤论坛)

    此外,笔记还会强调实际编程实现,包括C++或Java等语言的数据结构实现,如链表的插入、删除、遍历,树的构建与遍历,图的邻接矩阵和邻接表表示,以及各种排序和查找算法的代码实现。这部分内容有助于考生提升编程...

    哈工大数据结构考验笔记

    哈工大的数据结构考验笔记涵盖了这门课程的关键概念,是准备相关考试的重要参考资料。 首先,让我们深入探讨标题和描述中提及的知识点: 1. **第一章 绪论**: - **黑体字概念**:通常在教材或笔记中,黑体字用于...

    数据结构与算法分析-JAVA实现-带书签目录超清文字版

    常见的数据结构包括数组、链表、栈、队列、树(如二叉树、平衡树如AVL树和红黑树)、图以及哈希表等。每种数据结构都有其独特的特性和应用场景,例如,数组适合随机访问,链表适合动态插入和删除,而哈希表则提供...

    数据结构算法Java实现。关于Java《数据结构算法》核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。.zip

    数据结构是计算机科学中...这个压缩包“my_resource”可能包含了上述所有知识点的相关文件,如笔记、代码示例、练习题解答等,是学习和复习数据结构算法的理想资源。记得深入学习和动手实践,以真正掌握这些重要概念。

    Java数据结构与算法15天笔记.zip

    通过阅读这些笔记,你可以系统地学习Java中的数据结构和算法,掌握它们的基本概念、操作和应用场景,为提升编程技能和解决复杂问题打下坚实基础。记得结合博客文章深入学习,理论与实践相结合,才能更好地理解和运用...

    2018软创 数据结构实验报告.zip

    本资源包"2018软创 数据结构实验报告.zip"包含了针对C/C++/JAVA/Python编程语言的数据结构学习笔记和资料,适合大学生或编程初学者深入理解和掌握这一关键概念。 1. 数据结构基础 - 数据结构的基本概念:数组、...

    《数据结构与算法分析(Java语言描述版本)》中介绍的算法与数据结构.zip

    这些笔记有助于你系统地复习和学习数据结构。 相关书籍推荐:为了更深入地理解数据结构,我们推荐了几本经典的教材和参考书籍。这些书籍将帮助你建立完整的数据结构知识体系。 适用人群: 这份学习资料适用于所有...

    newreview_die4ix_Java数据结构_

    "newreview_die4ix_Java数据结构_"这个标题暗示了这是一个关于Java编程和数据结构复习的资源,可能包含了作者die4ix在学习或教学过程中整理的笔记、示例代码或测试题目。 描述中提到的“java基本编程的复习”涵盖了...

    java-senior-development-engineer-interview-notes-master.zip

    8. **数据结构与算法**:对常见数据结构(链表、队列、栈、树、图)和算法(排序、搜索)的掌握,直接影响到问题解决能力和代码效率。 9. **微服务**:了解微服务架构,包括服务发现、API Gateway、服务治理、熔断...

    基于java语言的数据结构及算法实现,LeetCode算法示例.zip

    这些笔记有助于你系统地复习和学习数据结构。 相关书籍推荐:为了更深入地理解数据结构,我们推荐了几本经典的教材和参考书籍。这些书籍将帮助你建立完整的数据结构知识体系。 适用人群: 这份学习资料适用于所有...

Global site tag (gtag.js) - Google Analytics