Java实现队列 - 队列内部使用链式存储结构
jopen
10年前
Java实现队列——队列内部使用链式存储结构
链队列
代码:
package hash; /** * Created with IntelliJ IDEA. * User: ASUS * Date: 14-9-17 * Time: 上午11:58 * To change this template use File | Settings | File Templates. */ public class CustomLinkQueue<E> { //定义一个内部类Node,Node实例代表链栈的节点。 private class Node { //保存节点的数据 private E data; //指向下个节点的引用 private Node next; //无参数的构造器 public Node() { } //初始化节点的数据域 private Node(E data) { this.data = data; } //初始化全部属性的构造器 public Node(E data, Node next) { this.data = data; this.next = next; } } private Node front; //头指针指向头结点 private Node rear; //尾节点 private int count; //该队列元素的数量 /** * 初始化队列 * 此时队列为空 */ public CustomLinkQueue() { Node p = new Node(); p.data = null; p.next = null; front = rear = p; } /** * 在队列的后端插入节点 * * @param item */ public void enqueue(E item) { Node newNode = new Node(); newNode.data = item; newNode.next = null; //入队的节点没有后继节点 this.rear.next = newNode; //让原来的尾节点的后继节点指向新节点 this.rear = newNode; //rear指向最后一个节点 count++; } /** * 出队 * 在队列的前端删除节点 * * @return */ public E dequeue() throws Exception { if (isEmpty()) { throw new Exception("队列为空"); } else { E obj; Node p = this.front.next; //指向队头的第一个节点 obj = p.data; this.front.next = p.next; if (rear == p) { rear = front; } count--; return obj; } } /** * @return */ public int size() { return count; } /** * 遍历算法 * 移动front指针,直到front指针追上rear指针 */ public void traverse() { for (Node current = front.next; current != null; current = current.next) { System.out.println(current.data); } } /** * 判断队列为空的条件是front == rear * * @return */ public boolean isEmpty() { return front == rear; } public static void main(String args[]) throws Exception { CustomLinkQueue linkQueue = new CustomLinkQueue(); for (int i = 0; i < 5; i++) { //添加5个元素 linkQueue.enqueue("lyx" + i); } System.out.println(linkQueue.size()); System.out.println("===========traverse==========="); linkQueue.traverse(); System.out.println("=============================="); linkQueue.dequeue(); linkQueue.dequeue(); System.out.println("===========traverse==========="); linkQueue.traverse(); System.out.println("=============================="); System.out.println(linkQueue.size()); } }来自:http://my.oschina.net/xinxingegeya/blog/314716