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

链队列

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

链队列代码结构

package list.queue;

　　public interface Queuable<T>;

　　public class QueueNode<T>;

　　public class LinkedQueue<T>;

package list;

　　public class TestLinkedQueue;

链队列公共接口

 1 package list.queue;
 2 
 3 public interface Queuable<T> {
 4 
 5     public int length();
 6 
 7     public boolean destroyQueue();
 8 
 9     public void clear();
10 
11     public boolean isEmpty();
12 
13     public T getHead();
14 
15     public boolean add(T element);
16 
17     public T remove();
18 
19 }

View Code

链队列节点类

 1 package list.queue;
 2 
 3 public class QueueNode<T> {
 4     private T data;
 5     private QueueNode next;
 6 
 7     QueueNode() {
 8         this(null);
 9     }
10     
11     QueueNode(T data) {
12         this(data,null);
13     }
14 
15     QueueNode(T data, QueueNode<T> next) {
16         this.data = data;
17         this.next = next;
18     }
19 
20     public QueueNode<T> getNext() {
21         return this.next;
22     }
23 
24     public T getData() {
25         return this.data;
26     }
27 
28     public void setNext(QueueNode<T> next) {
29         this.next = next;
30     }
31 
32     public void setData(T data) {
33         this.data = data;
34     }
35 
36     public String toString() {
37         return getData().toString();
38     }
39     
40 }

View Code

链队列实现类

 1 //**************************************************************************
 2 //*队列之链式存储结构链队列-JAVA实现
 3 //*@author Nora-Xie
 4 //*@time 2013-10-07PM22:00
 5 //**************************************************************************
 6 
 7 package list.queue;
 8 
 9 import list.queue.QueueNode;
10 import list.queue.Queuable;
11 
12 //链队列实际就是单链表，只不过是限定了其删除在队头，插入在队尾而已
13 public class LinkedQueue<T> implements Queuable<T> {
14     private QueueNode<T> front,rear;
15 
16     public LinkedQueue() {
17         this(null);
18     }
19 
20     public LinkedQueue(T element) {
21         if(element == null) {
22             front = new QueueNode<T>(null);
23             rear = front;
24         }else {
25             rear = new QueueNode<T>(element);
26             front = new QueueNode<T>(null,rear);
27         }
28     }
29 
30     public int length(){
31         if(isEmpty()) return 0;
32         int k = 1;
33         QueueNode<T> temp = front.getNext();
34         while(temp != rear) {
35             k++;
36             temp = temp.getNext();
37         }
38         return k;
39     }
40 
41     public boolean destroyQueue() {
42         return false;
43     }
44 
45     public void clear() {
46         if(isEmpty()) return;
47         while(front.getNext() != rear) {
48             remove();
49         }
50         remove();
51     }
52 
53     public boolean isEmpty() {
54         return front == rear;
55     }
56 
57     public T getHead() {
58         if(isEmpty()) return null;
59         return front.getNext().getData();
60     }
61 
62     public boolean add(T element) {
63         if(element == null) return false;
64         QueueNode<T> temp = front;
65         rear.setNext(new QueueNode<T>(element));
66         rear = rear.getNext();
67         return true;
68     }
69 
70     public T remove() {
71         if(isEmpty()) return null;
72         T element = front.getNext().getData();
73         if(length() == 1) 
74             rear = front;
75         else{
76             front.setNext(front.getNext().getNext());
77         }
78         return element;
79     }
80 
81     public String toString() {
82         if(isEmpty()) return "[ ]";
83         StringBuffer sb = new StringBuffer("[ ");
84         QueueNode<T> temp = front.getNext();
85         while(temp != rear) {
86             sb.append(temp+" ");
87             temp = temp.getNext();
88         }
89         sb.append(temp+" ");
90         sb.append("]");
91         return sb.toString();
92     }
93 
94 }

View Code

链队列测试类

 1 package list;
 2 
 3 import list.queue.LinkedQueue;
 4 import list.queue.Queuable;
 5 import list.queue.QueueNode;
 6 
 7 public class TestLinkedQueue {
 8     public static void main(String[] args) {
 9         Queuable<String> queue = new LinkedQueue<String>("A");
10         System.out.println("queue="+queue+"   queue.length="+queue.length());
11         queue.add("B");
12         System.out.println("queue="+queue+"   queue.length="+queue.length());
13         System.out.println("the removint element="+queue.remove());
14         System.out.println("queue="+queue+"   queue.length="+queue.length());
15         queue.add("C");
16         queue.add("D");
17         System.out.println("queue="+queue+"   queue.length="+queue.length());
18         queue.clear();
19         System.out.println("queue="+queue+"   queue.length="+queue.length());
20         System.out.println("queue is empty?  "+queue.isEmpty());
21         queue = new LinkedQueue<String>("a");
22         System.out.println("queue="+queue+"   queue.length="+queue.length());
23         queue.add("b");
24         queue.add("c");
25         queue.add("d");
26         queue.add("e");
27         queue.add("f");
28         queue.add("g");
29         System.out.println("queue="+queue+"   queue.length="+queue.length());
30         System.out.println("queue's head is ["+queue.getHead()+"]");
31         queue.remove();
32         System.out.println("queue="+queue+"   queue.length="+queue.length());
33         System.out.println("queue's head is ["+queue.getHead()+"]");
34     }
35 }

View Code