Java实现队列 - 队列内部使用链式存储结构

jopen 10年前

Java实现队列——队列内部使用链式存储结构

 

链队列

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