`

java 实现数据结构之队列

阅读更多
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作。
1.队列的顺序存储结构及实现
public class SequenceQueue<T>
{
	private int DEFAULT_SIZE = 10;
	//保存数组的长度。
	private int capacity;
	//定义一个数组用于保存顺序队列的元素
	private Object[] elementData;
	//保存顺序队列中元素的当前个数
	private int front = 0;
	private int rear = 0;
	//以默认数组长度创建空顺序队列
	public SequenceQueue()
	{
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	//以一个初始化元素来创建顺序队列
	public SequenceQueue(T element)
	{
		this();
		elementData[0] = element;
		rear++;
	}
	/**
	 * 以指定长度的数组来创建顺序队列
	 * @param element 指定顺序队列中第一个元素
	 * @param initSize 指定顺序队列底层数组的长度
	 */
	public SequenceQueue(T element , int initSize)
	{
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		rear++;
	}
	//获取顺序队列的大小
	public int length()
	{
		return rear - front;
	}
	//插入队列
	public void add(T element)
	{
		if (rear > capacity - 1)
		{
			throw new IndexOutOfBoundsException("队列已满的异常");
		}
		elementData[rear++] = element;
	}
	//移除队列
    public T remove()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		//保留队列的rear端的元素的值
		T oldValue = (T)elementData[front];
		//释放队列的rear端的元素
		elementData[front++] = null; 
		return oldValue;
	}
	//返回队列顶元素,但不删除队列顶元素
    public T element()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		return (T)elementData[front];
	}
	//判断顺序队列是否为空队列
	public boolean empty()
	{
		return rear == front;
	}
	//清空顺序队列
	public void clear()
	{
		//将底层数组所有元素赋为null
		Arrays.fill(elementData , null);
		front = 0;
		rear = 0;
	}
	public String toString()
	{
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (int i = front  ; i < rear ; i++ )
			{
				sb.append(elementData[i].toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
}

2.循环队列(顺序结构存储实现)

import java.util.Arrays;
public class LoopQueue<T>
{
	private int DEFAULT_SIZE = 10;
	//保存数组的长度。
	private int capacity;
	//定义一个数组用于保存循环队列的元素
	private Object[] elementData;
	//保存循环队列中元素的当前个数
	private int front = 0;
	private int rear = 0;
	//以默认数组长度创建空循环队列
	public LoopQueue()
	{
		capacity = DEFAULT_SIZE;
		elementData = new Object[capacity];
	}
	//以一个初始化元素来创建循环队列
	public LoopQueue(T element)
	{
		this();
		elementData[0] = element;
		rear++;
	}
	/**
	 * 以指定长度的数组来创建循环队列
	 * @param element 指定循环队列中第一个元素
	 * @param initSize 指定循环队列底层数组的长度
	 */
	public LoopQueue(T element , int initSize)
	{
		this.capacity = initSize;
		elementData = new Object[capacity];
		elementData[0] = element;
		rear++;
	}
	//获取循环队列的大小
	public int length()
	{
		if (empty())
		{
			return 0;
		}
		return rear > front ? rear - front 
			: capacity - (front - rear);
	}
	//插入队列
	public void add(T element)
	{
		if (rear == front 
			&& elementData[front] != null)
		{
			throw new IndexOutOfBoundsException("队列已满的异常");
		}
		elementData[rear++] = element;
		//如果rear已经到头,那就转头
		rear = rear == capacity ? 0 : rear;
	}
	//移除队列
	public T remove()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		//保留队列的rear端的元素的值
		T oldValue = (T)elementData[front];
		//释放队列的rear端的元素
		elementData[front++] = null; 
		//如果front已经到头,那就转头
		front = front == capacity ? 0 : front;
		return oldValue;
	}
	//返回队列顶元素,但不删除队列顶元素
	public T element()
	{
		if (empty())
		{
			throw new IndexOutOfBoundsException("空队列异常");
		}
		return (T)elementData[front];
	}
	//判断循环队列是否为空队列
	public boolean empty()
	{
		//rear==front且rear处的元素为null
		return rear == front 
			&& elementData[rear] == null;
	}
	//清空循环队列
	public void clear()
	{
		//将底层数组所有元素赋为null
		Arrays.fill(elementData , null);
		front = 0;
		rear = 0;
	}
	public String toString()
	{
		if (empty())
		{
			return "[]";
		}
		else
		{
			//如果front < rear,有效元素就是front到rear之间的元素
			if (front < rear)
			{
				StringBuilder sb = new StringBuilder("[");
				for (int i = front  ; i < rear ; i++ )
				{
					sb.append(elementData[i].toString() + ", ");
				}
				int len = sb.length();
				return sb.delete(len - 2 , len).append("]").toString();
			}
			//如果front >= rear,有效元素为front->capacity之间、0->front之间的
			else
			{
				StringBuilder sb = new StringBuilder("[");
				for (int i = front  ; i < capacity ; i++ )
				{
					sb.append(elementData[i].toString() + ", ");
				}
				for (int i = 0 ; i < rear ; i++)
				{
					sb.append(elementData[i].toString() + ", ");
				}
				int len = sb.length();
				return sb.delete(len - 2 , len).append("]").toString();
			}
		}
	}
}

3.队列的链式存储结构及实现
public class LinkQueue<T>
{
	//定义一个内部类Node,Node实例代表链队列的节点。
	private class Node
	{
		//保存节点的数据
		private T data;
		//指向下个节点的引用
		private Node next;
		//无参数的构造器
		public Node()
		{
		}
		//初始化全部属性的构造器
		public Node(T data ,  Node next)
		{
			this.data = data;
			this.next = next;
		}
	}
	//保存该链队列的头节点
	private Node front;
	//保存该链队列的尾节点
	private Node rear;
	//保存该链队列中已包含的节点数
	private int size;
	//创建空链队列
	public LinkQueue()
	{
		//空链队列,front和rear都是null
		front = null;
		rear = null;
	}
	//以指定数据元素来创建链队列,该链队列只有一个元素
	public LinkQueue(T element)
	{
		front = new Node(element , null);
		//只有一个节点,front、rear都指向该节点
		rear = front;
		size++;
	}
	//返回链队列的长度	
	public int length()
	{
		return size;
	}
	//将新元素加入队列
	public void add(T element)
	{
		//如果该链队列还是空链队列
		if (front == null)
		{
			front = new Node(element , null);
			//只有一个节点,front、rear都指向该节点
			rear = front;
		}
		else
		{
			//创建新节点
			Node newNode = new Node(element , null);
			//让尾节点的next指向新增的节点
			rear.next = newNode;
			//以新节点作为新的尾节点
			rear = newNode;
		}
		size++;
	}
	//删除队列front端的元素
	public T remove()
	{
		Node oldFront = front;
		front = front.next;
		oldFront.next = null;
		size--;
		return oldFront.data;
	}
	//访问链式队列中最后一个元素
	public T element()
	{
		return rear.data;
	}
	//判断链式队列是否为空队列
	public boolean empty()
	{
		return size == 0;
	}
	//清空链队列
	public void clear()
	{
		//将front、rear两个节点赋为null
		front = null;
		rear = null;
		size = 0;
	}
	public String toString()
	{
		//链队列为空链队列时
		if (empty())
		{
			return "[]";
		}
		else
		{
			StringBuilder sb = new StringBuilder("[");
			for (Node current = front ; current != null
				; current = current.next )
			{
				sb.append(current.data.toString() + ", ");
			}
			int len = sb.length();
			return sb.delete(len - 2 , len).append("]").toString();
		}
	}
}
分享到:
评论
3 楼 andylauzhl 2014-04-22  
mark 
2 楼 啦登2010 2014-04-04  
1 楼 ssssd1000 2012-10-18  
代码写的规范,注释写的很详细。一看就懂。好文章。

相关推荐

    Java队列实现,数据结构

    在这个Java队列实现的数据结构作业练习中,我们将会探讨如何使用Java来创建一个简单的队列,并分析`Queue.java`和`Node.java`这两个文件可能包含的内容。 首先,`Queue.java`很可能是实现队列接口或类的文件。在...

    用Java实现数据结构中的队列

    在计算机科学中,数据结构是组织、存储和处理数据的方式,...通过理解这些基本概念和代码示例,你可以轻松地在Java项目中实现和使用队列数据结构。记住,选择哪种实现取决于具体的需求,如性能、内存使用和功能需求。

    java实现数据结构

    下面将详细介绍Java中实现链表、栈、队列、优先级队列以及哈希表这些基本数据结构的方法。 首先,我们来看链表。链表是一种线性数据结构,其中的元素不连续存储,而是通过指针连接。Java中的`LinkedList`类实现了`...

    Java语言编写的数据结构-队列实现

    Java作为一种广泛使用的编程语言,提供了丰富的库支持来实现各种数据结构。在这个主题中,我们将深入探讨Java中队列的实现,包括顺序队列(SqQueueCycle)和链队列(LinkQueue)。 1. **队列的基本概念** 队列是一...

    数据结构:链队列

    链队列,顾名思义,是基于链表实现的队列数据结构。队列是一种遵循“先进先出”(FIFO,First In First Out)原则的数据结构,类似于现实生活中的排队等待。在链队列中,元素按照加入的顺序排列,第一个加入的元素被...

    java队列实现(顺序队列、链式队列、循环队列)

    Java中的队列是一种数据结构,它遵循先进先出(FIFO)原则,即最先插入的元素将是最先被删除的。在Java中,队列的实现主要有三种:顺序队列、链式队列和循环队列。下面我们将详细探讨这三种队列的实现方式。 1. **...

    常用数据结构(堆栈,队列,列表)JAVA代码

    在这个主题中,我们将深入探讨Java实现的三种基本数据结构:堆栈(Stack)、队列(Queue)和列表(List)。这些概念是计算机科学的核心部分,对理解和解决复杂问题至关重要。 1. **堆栈(Stack)**: - 堆栈是一种...

    数据结构JAVA实现

    在这个名为“数据结构JAVA实现”的压缩包中,我们可以看到作者提供了三种重要的数据结构——链表、有序二叉树和队列的Java代码实现。 首先,让我们详细探讨链表。链表是一种线性数据结构,与数组不同,它不连续存储...

    Java常见数据结构面试题(带答案)

    "Java常见数据结构面试题(带答案)" 以下是对Java常见数据结构面试题的...本篇文章主要介绍了Java常见数据结构面试题,涵盖了栈、队列、链表、线性表、树、算法、数据结构等知识点,希望对广大的程序爱好者有所帮助。

    用数组实现的优先队列(JAVA)

    总之,`PriorityQ.java`文件可能是一个简单的数组实现优先队列的示例,通过分析这个文件,我们可以学习到如何利用数组数据结构实现优先队列,以及理解其核心的插入、删除和查找操作。同时,这也能帮助我们更好地掌握...

    java队列模拟实现

    Java队列模拟实现是一个典型的计算机科学中的数据结构应用,它主要涉及了Java编程语言和队列数据结构。在这个工程中,开发者已经创建了一个基于图形用户界面(GUI)的应用程序,用于演示和操作队列的各种功能。以下...

    java基础数据结构-队列

    ### Java基础数据结构—队列 #### 一、队列的概念与特性 队列是一种特殊类型的线性表,它的特点是先进先出(FIFO,First In First Out)。我们可以将其想象成现实生活中的排队情景,比如排队购买火车票时,最早...

    java-数据结构代码实现

    本资料包“java-数据结构代码实现”提供了使用Java语言实现数据结构的实例,旨在帮助开发者加深对数据结构的理解并提升编程技能。 1. **链表**:链表是一种动态数据结构,其元素在内存中不是顺序排列的。Java中的...

    数据结构——队列的实现

    3. 高级数据结构实现:如Java的`java.util.Queue`接口,提供了多种队列实现,如`ArrayDeque`(基于数组的双端队列)、`LinkedList`(链表实现)等。 队列的应用场景: 1. 打印机任务调度:新任务入队,完成的任务出...

    java多线程模拟队列实现排队叫号

    总的来说,通过Java多线程和队列数据结构,我们可以有效地模拟排队叫号系统。这种模拟有助于理解和实践并发编程,同时也为我们解决实际问题提供了思路。在这个过程中,我们学习了线程同步、队列操作以及如何在Java中...

    JAVA基本5种数据结构的实现。

    队列是一种先进先出(FIFO)的数据结构,`Queue.java`和`QueueApp.java`可能实现了这一概念。在Java中,可以使用`java.util.Queue`接口及其实现如`LinkedList`来创建队列。队列的主要操作包括添加元素(enqueue)、...

    Java数据结构之队列的简单定义与使用方法

    Java中实现队列的方法有多种,本文将详细介绍Java数据结构之队列的简单定义与使用方法。 一、队列的定义 队列是一种特殊的线性表,元素的添加和删除只能在队列的两端进行,即队头和队尾。队列的原则是先进先出,就...

    Java版本数据结构实验报告

    总的来说,"Java版本数据结构实验报告"是一个全面的学习资源,它涵盖了数据结构的基本理论和Java实现,旨在提升学生的算法思维能力和编程技巧。通过这一系列的实验,学生不仅能熟练掌握各种数据结构,还能学会如何...

    java数据结构实例

    "Java数据结构实例"这个主题,旨在通过具体的代码实例帮助初学者掌握数据结构的基本概念和使用方式,以此来提升编程思维和问题解决能力。在这个压缩包文件中,我们可以预期找到一些用Java实现的数据结构的源代码。 ...

    数据结构队列总结

    总之,队列作为一种基本的数据结构,其在Java编程语言中的实现和应用非常广泛。无论是通过数组还是链表实现,队列都能有效地帮助我们管理和控制数据的流动,特别是在需要遵循特定顺序或限制并发访问的场景下。深入...

Global site tag (gtag.js) - Google Analytics