package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: ArrayQueue * @Description: 順序隊列 * @date 2014年1月20日 下午3:46:19 * @param <T> */public class ArrayQueue<T> implements Serializable{ /**  * @Fields serialVersionUID : TODO  */ private static final long serialVersionUID = 7333344126529379197L; private int DEFAULT_SIZE = 10; private int capacity;//保存數組的長度 private Object[] elementData;//定義一個數組用于保存順序隊列的元素 private int front = 0;//隊頭 private int rear = 0;//隊尾 //以默認數組長度創建空順序隊列 public ArrayQueue() {  capacity = DEFAULT_SIZE;  elementData = new Object[capacity]; } //以一個初始化元素來創建順序隊列 public ArrayQueue(T element) {  this();  elementData[0] = element;  rear++; }  public ArrayQueue(int initSize) {  elementData = new Object[initSize]; } /**  * 以指定長度的數組來創建順序隊列  * @param element 指定順序隊列中第一個元素  * @param initSize 指定順序隊列底層數組的長度  */ public ArrayQueue(T element, int initSize) {  this.capacity = initSize;  elementData = new Object[capacity];  elementData[0] = element;  rear++; } /**  * @Title: size     * @Description: 獲取順序隊列的大小    * @return  */ public int size() {  return rear - front; } /**  * @Title: offer     * @Description: 入隊    * @param element  */ public void offer(T element) {  ensureCapacity(rear + 1);  elementData[rear++] = element; }  private void ensureCapacity(int minCapacity) {  //如果數組的原有長度小于目前所需的長度  int oldCapacity = elementData.length;  if (minCapacity > oldCapacity) {   int newCapacity = (oldCapacity * 3) / 2 + 1;   if (newCapacity < minCapacity)    newCapacity = minCapacity;   // minCapacity is usually close to size, so this is a win:   elementData = Arrays.copyOf(elementData, newCapacity);  } } /**  * @Title: poll     * @Description: 出隊    * @return  */ public T poll() {  if (isEmpty()) {   throw new IndexOutOfBoundsException("空隊列異常");  }  //保留隊列的front端的元素的值  T oldValue = (T) elementData[front];  //釋放隊列的front端的元素  elementData[front++] = null;  return oldValue; } /**  * @Title: peek     * @Description: 返回隊列頂元素，但不刪除隊列頂元素    * @return  */ public T peek() {  if (isEmpty()) {   throw new IndexOutOfBoundsException("空隊列異常");  }  return (T) elementData[front]; } /**  * @Title: isEmpty     * @Description: 判斷順序隊列是否為空隊列    * @return  */ public boolean isEmpty() {  return rear == front; } /**  * @Title: clear     * @Description: 清空順序隊列  */ public void clear() {  //將底層數組所有元素賦為null  Arrays.fill(elementData, null);  front = 0;  rear = 0; } public String toString() {  if (isEmpty()) {   return "[]";  } else {   StringBuilder sb = new StringBuilder("[");   for (int i = front; i < rear; i++) {    sb.append(elementData[i].toString() + ", ");   }   int len = sb.length();   return sb.delete(len - 2, len).append("]").toString();  } }}

package lang;import java.io.Serializable;/** * @ClassName: LinkQueue * @Description: 鏈式隊列 * @date 2014年1月21日 下午3:24:38 * @param <T> */public class LinkQueue<T> implements Serializable{ /**  * @Fields serialVersionUID : TODO  */ private static final long serialVersionUID = -6726728595616312615L; //定義一個內部類Node，Node實例代表鏈隊列的節點。 private class Node {    private T data;//保存節點的數據    private Node next;//指向下個節點的引用  //無參數的構造器  public Node() {  }  //初始化全部屬性的構造器  public Node(T data, Node next) {   this.data = data;   this.next = next;  } }  private Node front;//保存該鏈隊列的頭節點  private Node rear;//保存該鏈隊列的尾節點 private int size;//保存該鏈隊列中已包含的節點數 /**  * <p>Title: LinkQueue </p>     * <p>Description: 創建空鏈隊列 </p>   */ public LinkQueue() {  //空鏈隊列，front和rear都是null  front = null;  rear = null; } /**  * <p>Title: LinkQueue </p>    * <p>Description: 以指定數據元素來創建鏈隊列，該鏈隊列只有一個元素</p>   */ public LinkQueue(T element) {  front = new Node(element, null);  //只有一個節點，front、rear都指向該節點  rear = front;  size++; } /**  * @Title: size     * @Description: 獲取順序隊列的大小    * @return  */ public int size() {  return size; } /**  * @Title: offer     * @Description: 入隊    * @param element  */ public void offer(T element) {  //如果該鏈隊列還是空鏈隊列  if (front == null) {   front = new Node(element, null);      rear = front;//只有一個節點，front、rear都指向該節點  } else {      Node newNode = new Node(element, null);//創建新節點      rear.next = newNode;//讓尾節點的next指向新增的節點      rear = newNode;//以新節點作為新的尾節點  }  size++; } /**  * @Title: poll     * @Description: 出隊    * @return  */ public T poll() {  Node oldFront = front;  front = front.next;  oldFront.next = null;  size--;  return oldFront.data; } /**  * @Title: peek     * @Description: 返回隊列頂元素，但不刪除隊列頂元素    * @return  */ public T peek() {  return rear.data; } /**  * @Title: isEmpty     * @Description: 判斷順序隊列是否為空隊列    * @return  */ public boolean isEmpty() {  return size == 0; } /**  * @Title: clear     * @Description: 清空順序隊列  */ public void clear() {  //將front、rear兩個節點賦為null  front = null;  rear = null;  size = 0; } public String toString() {  //鏈隊列為空鏈隊列時  if (isEmpty()) {   return "[]";  } else {   StringBuilder sb = new StringBuilder("[");   for (Node current = front; current != null; current = current.next) {    sb.append(current.data.toString() + ", ");   }   int len = sb.length();   return sb.delete(len - 2, len).append("]").toString();  } } public static void main(String[] args) {  LinkQueue<String> queue = new LinkQueue<String>("aaaa");  //添加兩個元素  queue.offer("bbbb");  queue.offer("cccc");  System.out.println(queue);  //刪除一個元素后  queue.poll();  System.out.println("刪除一個元素后的隊列：" + queue);  //再次添加一個元素  queue.offer("dddd");  System.out.println("再次添加元素后的隊列：" + queue);  //刪除一個元素后，隊列可以再多加一個元素  queue.poll();  //再次加入一個元素  queue.offer("eeee");  System.out.println(queue); }}

package lang;import java.io.Serializable;import java.util.Arrays;/** * @ClassName: LoopQueue * @Description: 循環隊列 * @date 2014年1月20日 下午3:47:14 */public class LoopQueue<T> implements Serializable{ /**  * @Fields serialVersionUID : TODO  */ private static final long serialVersionUID = -3670496550272478781L; private int DEFAULT_SIZE = 10; private int capacity;//保存數組的長度 private Object[] elementData;//定義一個數組用于保存循環隊列的元素 private int front = 0;//隊頭 private int rear = 0;//隊尾 //以默認數組長度創建空循環隊列 public LoopQueue() {  capacity = DEFAULT_SIZE;  elementData = new Object[capacity]; } //以一個初始化元素來創建循環隊列 public LoopQueue(T element) {  this();  elementData[0] = element;  rear++; } /**  * 以指定長度的數組來創建循環隊列  * @param element 指定循環隊列中第一個元素  * @param initSize 指定循環隊列底層數組的長度  */ public LoopQueue(T element, int initSize) {  this.capacity = initSize;  elementData = new Object[capacity];  elementData[0] = element;  rear++; } //獲取循環隊列的大小 public int size() {  if (isEmpty()) {   return 0;  }  return rear > front ? rear - front : capacity - (front - rear); } //插入隊列 public void add(T element) {  if (rear == front && elementData[front] != null) {   throw new IndexOutOfBoundsException("隊列已滿的異常");  }  elementData[rear++] = element;  //如果rear已經到頭，那就轉頭  rear = rear == capacity ? 0 : rear; } //移除隊列 public T remove() {  if (isEmpty()) {   throw new IndexOutOfBoundsException("空隊列異常");  }  //保留隊列的rear端的元素的值  T oldValue = (T) elementData[front];  //釋放隊列的rear端的元素  elementData[front++] = null;  //如果front已經到頭，那就轉頭  front = front == capacity ? 0 : front;  return oldValue; } //返回隊列頂元素，但不刪除隊列頂元素 public T element() {  if (isEmpty()) {   throw new IndexOutOfBoundsException("空隊列異常");  }  return (T) elementData[front]; } //判斷循環隊列是否為空隊列 public boolean isEmpty() {  //rear==front且rear處的元素為null  return rear == front && elementData[rear] == null; } //清空循環隊列 public void clear() {  //將底層數組所有元素賦為null  Arrays.fill(elementData, null);  front = 0;  rear = 0; } public String toString() {  if (isEmpty()) {   return "[]";  } else {   //如果front < rear，有效元素就是front到rear之間的元素   if (front < rear) {    StringBuilder sb = new StringBuilder("[");    for (int i = front; i < rear; i++) {     sb.append(elementData[i].toString() + ", ");    }    int len = sb.length();    return sb.delete(len - 2, len).append("]").toString();   }   //如果front >= rear，有效元素為front->capacity之間、0->front之間的   else {    StringBuilder sb = new StringBuilder("[");    for (int i = front; i < capacity; i++) {     sb.append(elementData[i].toString() + ", ");    }    for (int i = 0; i < rear; i++) {     sb.append(elementData[i].toString() + ", ");    }    int len = sb.length();    return sb.delete(len - 2, len).append("]").toString();   }  } } public static void main(String[] args) {  LoopQueue<String> queue = new LoopQueue<String>("aaaa", 3);  //添加兩個元素  queue.add("bbbb");  queue.add("cccc");  //此時隊列已滿  System.out.println(queue);  //刪除一個元素后，隊列可以再多加一個元素  queue.remove();  System.out.println("刪除一個元素后的隊列：" + queue);  //再次添加一個元素，此時隊列又滿  queue.add("dddd");  System.out.println(queue);  System.out.println("隊列滿時的長度：" + queue.size());  //刪除一個元素后，隊列可以再多加一個元素  queue.remove();  //再次加入一個元素，此時隊列又滿  queue.add("eeee");  System.out.println(queue); }}