链队列
实际上就是单链表，只是规定了删除在队头进行，添加在队尾进行。
链队列代码结构
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{ 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 }
链队列节点类
1 package list.queue; 2 3 public class QueueNode{ 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 next) {16 this.data = data;17 this.next = next;18 }19 20 public QueueNode getNext() {21 return this.next;22 }23 24 public T getData() {25 return this.data;26 }27 28 public void setNext(QueueNode 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 }
链队列实现类
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 LinkedQueueimplements Queuable {14 private QueueNode front,rear;15 16 public LinkedQueue() {17 this(null);18 }19 20 public LinkedQueue(T element) {21 if(element == null) {22 front = new QueueNode (null);23 rear = front;24 }else {25 rear = new QueueNode (element);26 front = new QueueNode (null,rear);27 }28 }29 30 public int length(){31 if(isEmpty()) return 0;32 int k = 1;33 QueueNode 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 temp = front;65 rear.setNext(new QueueNode (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 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 }
链队列测试类
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 queue = new LinkedQueue ("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 ("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 }