java与数据结构(8)---java实现链队列

链队列

实际上就是单链表，只是规定了删除在队头进行，添加在队尾进行。

链队列代码结构

package list.queue;

　　public interface Queuable<T>;

　　public class QueueNode<T>;

　　public class LinkedQueue<T>;

package list;

　　public class TestLinkedQueue;

链队列公共接口

 package list.queue;

 public interface Queuable<T> {

     public int length();

     public boolean destroyQueue();

     public void clear();

     public boolean isEmpty();

     public T getHead();

     public boolean add(T element);

     public T remove();

 }

链队列节点类

 package list.queue;

 public class QueueNode<T> {

     private T data;

     private QueueNode next;

     QueueNode() {

         this(null);

     }

     QueueNode(T data) {

         this(data,null);

     }

     QueueNode(T data, QueueNode<T> next) {

         this.data = data;

         this.next = next;

     }

     public QueueNode<T> getNext() {

         return this.next;

     }

     public T getData() {

         return this.data;

     }

     public void setNext(QueueNode<T> next) {

         this.next = next;

     }

     public void setData(T data) {

         this.data = data;

     }

     public String toString() {

         return getData().toString();

     }

 }

链队列实现类

 //**************************************************************************

 //*队列之链式存储结构链队列-JAVA实现

 //*@author Nora-Xie

 //*@time 2013-10-07PM22:00

 //**************************************************************************

 package list.queue;

 import list.queue.QueueNode;

 import list.queue.Queuable;

 //链队列实际就是单链表，只不过是限定了其删除在队头，插入在队尾而已

 public class LinkedQueue<T> implements Queuable<T> {

     private QueueNode<T> front,rear;

     public LinkedQueue() {

         this(null);

     }

     public LinkedQueue(T element) {

         if(element == null) {

             front = new QueueNode<T>(null);

             rear = front;

         }else {

             rear = new QueueNode<T>(element);

             front = new QueueNode<T>(null,rear);

         }

     }

     public int length(){

         if(isEmpty()) return 0;

         int k = 1;

         QueueNode<T> temp = front.getNext();

         while(temp != rear) {

             k++;

             temp = temp.getNext();

         }

         return k;

     }

     public boolean destroyQueue() {

         return false;

     }

     public void clear() {

         if(isEmpty()) return;

         while(front.getNext() != rear) {

             remove();

         }

         remove();

     }

     public boolean isEmpty() {

         return front == rear;

     }

     public T getHead() {

         if(isEmpty()) return null;

         return front.getNext().getData();

     }

     public boolean add(T element) {

         if(element == null) return false;

         QueueNode<T> temp = front;

         rear.setNext(new QueueNode<T>(element));

         rear = rear.getNext();

         return true;

     }

     public T remove() {

         if(isEmpty()) return null;

         T element = front.getNext().getData();

         if(length() == 1)

             rear = front;

         else{

             front.setNext(front.getNext().getNext());

         }

         return element;

     }

     public String toString() {

         if(isEmpty()) return "[ ]";

         StringBuffer sb = new StringBuffer("[ ");

         QueueNode<T> temp = front.getNext();

         while(temp != rear) {

             sb.append(temp+" ");

             temp = temp.getNext();

         }

         sb.append(temp+" ");

         sb.append("]");

         return sb.toString();

     }

 }

链队列测试类

 package list;

 import list.queue.LinkedQueue;

 import list.queue.Queuable;

 import list.queue.QueueNode;

 public class TestLinkedQueue {

     public static void main(String[] args) {

         Queuable<String> queue = new LinkedQueue<String>("A");

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         queue.add("B");

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         System.out.println("the removint element="+queue.remove());

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         queue.add("C");

         queue.add("D");

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         queue.clear();

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         System.out.println("queue is empty?  "+queue.isEmpty());

         queue = new LinkedQueue<String>("a");

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         queue.add("b");

         queue.add("c");

         queue.add("d");

         queue.add("e");

         queue.add("f");

         queue.add("g");

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         System.out.println("queue's head is ["+queue.getHead()+"]");

         queue.remove();

         System.out.println("queue="+queue+"   queue.length="+queue.length());

         System.out.println("queue's head is ["+queue.getHead()+"]");

     }

 }