`

队列小实现

阅读更多
package cn.smallbug.datastructure.queue;

/**
 * 队列接口
 * 
 * @timestamp Feb 23, 2016 3:28:20 PM
 * @author smallbug
 * @param <T>
 */
public interface Queue<T> {

	/**
	 * 入队列
	 * 
	 * @timestamp Feb 23, 2016 3:28:31 PM
	 * @param obj
	 * @return
	 */
	public boolean enQueue(T obj);

	/**
	 * 出队列
	 * 
	 * @timestamp Feb 23, 2016 3:28:51 PM
	 * @return
	 */
	public T deQueue();

	/**
	 * 队列是否为空
	 * 
	 * @timestamp Feb 23, 2016 3:28:59 PM
	 * @return
	 */
	public boolean isEmpty();

	/**
	 * 队列中元素个数
	 * 
	 * @timestamp Feb 23, 2016 3:29:36 PM
	 * @return
	 */
	public int size();

	/**
	 * 获取对头元素(不删除)
	 * 
	 * @timestamp Feb 23, 2016 3:30:03 PM
	 * @return
	 */
	public T getFirst();
}

 

package cn.smallbug.datastructure.queue;

/**
 * 队列异常
 * 
 * @timestamp Feb 23, 2016 3:50:19 PM
 * @author smallbug
 */
public class QueueException extends RuntimeException {

	/**
	 * 
	 */
	private static final long serialVersionUID = 3156992864706426492L;

	public QueueException() {

		this(null, null);

	}

	public QueueException(String message) {

		this(message, null);

	}

	public QueueException(Throwable throwable) {

		this(null, throwable);

	}

	public QueueException(String message, Throwable throwable) {

		super();
		this.message = message;
		this.throwable = throwable;

	}

	protected String message = null;

	protected Throwable throwable = null;

	public String getMessage() {

		return (message);

	}

	public Throwable getThrowable() {

		return (throwable);

	}

	public String toString() {

		StringBuilder sb = new StringBuilder("QueryException:  ");
		if (message != null) {
			sb.append(message);
			if (throwable != null) {
				sb.append(":  ");
			}
		}
		if (throwable != null) {
			sb.append(throwable.toString());
		}
		return (sb.toString());

	}

}

 

package cn.smallbug.datastructure.queue;

/**
 * 数组结构实现的队列
 * 
 * @timestamp Feb 23, 2016 3:32:44 PM
 * @author smallbug
 */
public class ArrayQueue<T> implements Queue<T> {

	private int defaultSize = 10; // 默认队列的长度
	private int front; // 队头
	private int rear; // 队尾
	private int count; // 统计元素个数的计数器
	private int maxSize; // 队的最大长度
	private T[] queue; // 队列

	/**
	 * 默认大小
	 */
	public ArrayQueue() {
		init(defaultSize);
	}

	/**
	 * 指定大小
	 * 
	 * @param maxSize
	 */
	public ArrayQueue(int maxSize) {
		if (maxSize <= 0)
			throw new IllegalArgumentException("maxSize mast greater than 0!");
		init(maxSize);
	}

	/**
	 * 初始化
	 * 
	 * @timestamp Feb 23, 2016 3:42:20 PM
	 * @param maxSize
	 */
	@SuppressWarnings("unchecked")
	private void init(int maxSize) {
		this.maxSize = maxSize;
		front = rear = 0;
		count = 0;
		queue = (T[]) new Object[maxSize];
	}

	@Override
	public boolean enQueue(T obj) {
		if (obj == null) {
			throw new QueueException("object not null!");
		}
		if (count > 0 && rear == front) {
			return false;
		}
		queue[rear] = obj;
		count++;
		rear = (rear + 1) % maxSize;
		return true;
	}

	@Override
	public T deQueue() {
		if (count == 0 && rear == front) {
			return null;
		}
		T obj = queue[front];
		queue[front] = null;
		count--;
		front = (front + 1) % maxSize;
		return obj;
	}

	@Override
	public boolean isEmpty() {
		return count == 0 ? true : false;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public T getFirst() {
		if (count > 0)
			return queue[front];
		return null;
	}

}

 

package cn.smallbug.datastructure.queue;

/**
 * 链表结构实现的循环队列
 * 
 * @timestamp Feb 23, 2016 3:32:02 PM
 * @author smallbug
 */
public class LinkedQueue<T> implements Queue<T> {

	private Node<T> front; // 队头
	private Node<T> rear; // 队尾
	private int count; // 计数器

	private int maxSize = -1;// 最大元素个数

	public LinkedQueue() {
		init();
	}

	public LinkedQueue(int maxSize) {
		if (maxSize <= 0) {
			throw new IllegalArgumentException("maxSize mast greater than 0!");
		}
		init();
		this.maxSize = maxSize;
	}

	private void init() {
		front = rear = null;
		count = 0;
	}

	@Override
	public boolean enQueue(T obj) {
		if (obj == null) {
			throw new QueueException("object not null!");
		}
		if (maxSize != -1 && maxSize == count)
			return false;
		Node<T> node = new Node<T>(obj, null);
		if (rear != null) {
			rear.next = node;
		}
		rear = node;
		if (front == null) {
			front = node;
		}
		count++;
		return true;
	}

	@Override
	public T deQueue() {
		if (isEmpty())
			return null;
		T t = front.getElement();
		front = front.next;
		count--;
		return t;
	}

	@Override
	public boolean isEmpty() {
		return count == 0;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public T getFirst() {
		if (!isEmpty()) {
			return front.getElement();
		} else {
			return null;
		}
	}

	private class Node<D> {

		private D element; // 数据域
		private Node<D> next; // 指针域

		// 头结点的构造方法
		public Node(Node<D> nextval) {
			this.next = nextval;
		}

		// 非头结点的构造方法
		public Node(D obj, Node<D> nextval) {
			this(nextval);
			this.element = obj;
			this.next = nextval;
		}

		// 获得当前的数据域的值
		public D getElement() {
			return this.element;
		}
	}
}

 

循环队列和链式队列的比较:

     (1)从时间上看,它们的基本操作都是常数时间,即O(1)的。不过循环队列是事先申请好空间,使用期间不释放;而链式队列,每次申请和释放结点也会存在一定的时间开销,如果入栈和出栈比较频繁,则两者还是有细微的差别。

     (2)从空间上看,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链式队列更加灵活。

 

1
3
分享到:
评论

相关推荐

    C#任务队列的实现

    2. **队列实现**: - 可以使用`System.Collections.Concurrent`命名空间中的`ConcurrentQueue&lt;T&gt;`或`BlockingCollection&lt;T&gt;`来实现任务队列。`ConcurrentQueue&lt;T&gt;`是线程安全的队列,而`BlockingCollection&lt;T&gt;`在此...

    java队列模拟实现

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

    循环队列的C++实现

    循环队列是一种线性数据结构,它在物理结构上实现了一个闭合的循环,因此队首和队尾可以在数组的任意位置。这种设计使得在队列满或空时,仍能有效地进行入队和出队操作,避免了普通队列在达到边界条件时的特殊处理。...

    顺序队列的实现

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队...

    顺序队列和链式队列的实现

    顺序队列是一种基于数组的队列实现方式。其主要特点是使用一个数组来存储队列元素,并使用两个指针front和rear来指示队首和队尾的位置。 顺序队列的实现可以使用以下步骤: 1. 定义一个顺序队列类,继承自队列接口...

    栈和队列操作:栈实现、队列实现、双栈实现队列、双队列实现栈、栈实现O(n)求当前栈最大值

    栈实现 队列实现 双栈实现队列 双队列实现栈 栈实现O(n)求当前栈最大值 http://blog.csdn.net/ssuchange/article/details/17398007

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

    在Java中,队列的实现主要有三种:顺序队列、链式队列和循环队列。下面我们将详细探讨这三种队列的实现方式。 1. **顺序队列**: 顺序队列通常是基于数组实现的。在Java中,我们可以使用ArrayList或LinkedList来...

    双端队列C++实现 双端队列C++实现

    然而,如果你想要自定义一个双端队列,我们可以从头开始探讨如何实现。 自定义双端队列的基本思想是使用动态数组或链表作为底层数据结构。这里我们以动态数组为例,因为它提供了更好的空间效率和随机访问性能。一个...

    JAVA 模拟队列的实现

    本课程设计旨在通过模拟队列的实现,帮助学习者深入理解Java编程以及队列数据结构的运作原理。 队列作为一种线性数据结构,遵循“先进先出”(FIFO)原则,即最早插入的元素最先被移除,而最近插入的元素则在队尾等待...

    数据结构队列的实现

    根据给定的信息,本文将详细解释队列这一数据结构,并且着重分析动态链接队列(DynaLnkQueue)的实现方法。 ### 数据结构:队列 队列是一种线性表,只允许在一端进行插入操作,在另一端进行删除操作。这种特性也被...

    C#队列的实现

    在给定的“EX17_04”文件中,可能包含了C#队列实现的源代码实例。通过分析这些源代码,你可以更深入地理解C#中队列的内部工作机制,如元素的添加、删除以及队列的扩容策略等。同时,也可以学习如何在实际项目中灵活...

    数据结构 队列实现 数据结构 队列实现

    ### 数据结构:队列实现详解 #### 一、队列概念与特性 在计算机科学领域,**队列**是一种常见的线性数据结构,遵循先进先出(First In First Out, FIFO)的原则。也就是说,最早添加到队列中的元素将是最先被移除的...

    消息队列的实现

    然而,这里提到的“消息队列实现”可能是指自定义实现的消息队列,而非Windows内建的消息系统。在VC中,可以使用多种数据结构,如链表或队列,来实现一个自定义的消息队列。消息通常包含一个消息类型标识和相关的...

    循环队列的实现源码

    在压缩包文件`reQueue`中,很可能包含了一个实现循环队列的源代码文件,通过阅读和理解这个文件,你可以更深入地了解循环队列的具体实现细节,以及如何在实际项目中应用这种数据结构。学习和掌握循环队列的实现,...

    高效延时队列的设计与实现

    常见的延时队列实现方案包括: 1. 轮询数据库:定期查询数据库中即将到期的延时任务,但这可能导致大量无效查询,效率较低。 2. 使用JDK自带的DelayQueue:这是一个无界阻塞队列,元素需实现Delayed接口,当延迟时间...

    循环队列的实现

    循环队列是一种线性数据结构,它在物理结构上实现了一个首尾相接的闭合环形序列。这种数据结构克服了普通队列在出队和入队操作时可能出现的“满”或“空”问题,提高了空间利用率。在循环队列中,队头和队尾的位置都...

    队列的C语言实现

    在本教程中,我们将深入探讨如何使用C语言来实现队列。 一、队列的基本概念 队列是一种线性数据结构,其中元素按照特定顺序(FIFO)进行操作。在队列中,新元素在队尾(rear)加入,而旧元素在队头(front)移除。...

    一种通用队列的实现

    在这个场景中,我们讨论的是一种特别设计的通用队列实现,由个人编写,适用于8-32位单片机系统,其地址空间为16-32位。这个简洁的队列实现使用了C语言中的指针来高效地处理数据。 首先,C语言是编程的基础,它的...

Global site tag (gtag.js) - Google Analytics