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()+"]");
}
}
上一篇:Git for Windows之团队合作


下一篇:PHP实例学习之————MVC架构模式分析与设计