java隊(duì)列實(shí)現(xiàn)方法(順序隊(duì)列,鏈?zhǔn)疥?duì)列,循環(huán)隊(duì)列)

package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
 * @ClassName: ArrayQueue
 * @Description: 順序隊(duì)列
 * @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;//保存數(shù)組的長(zhǎng)度
 private Object[] elementData;//定義一個(gè)數(shù)組用于保存順序隊(duì)列的元素
 private int front = 0;//隊(duì)頭
 private int rear = 0;//隊(duì)尾
 //以默認(rèn)數(shù)組長(zhǎng)度創(chuàng)建空順序隊(duì)列
 public ArrayQueue() {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 //以一個(gè)初始化元素來(lái)創(chuàng)建順序隊(duì)列
 public ArrayQueue(T element) {
  this();
  elementData[0] = element;
  rear++;
 }
 
 public ArrayQueue(int initSize) {
  elementData = new Object[initSize];
 }
 /**
  * 以指定長(zhǎng)度的數(shù)組來(lái)創(chuàng)建順序隊(duì)列
  * @param element 指定順序隊(duì)列中第一個(gè)元素
  * @param initSize 指定順序隊(duì)列底層數(shù)組的長(zhǎng)度
  */
 public ArrayQueue(T element, int initSize) {
  this.capacity = initSize;
  elementData = new Object[capacity];
  elementData[0] = element;
  rear++;
 }
 /**
  * @Title: size   
  * @Description: 獲取順序隊(duì)列的大小  
  * @return
  */
 public int size() {
  return rear - front;
 }
 /**
  * @Title: offer   
  * @Description: 入隊(duì)  
  * @param element
  */
 public void offer(T element) {
  ensureCapacity(rear + 1);
  elementData[rear++] = element;
 }
 
 private void ensureCapacity(int minCapacity) {
  //如果數(shù)組的原有長(zhǎng)度小于目前所需的長(zhǎng)度
  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: 出隊(duì)  
  * @return
  */
 public T poll() {
  if (isEmpty()) {
   throw new IndexOutOfBoundsException("空隊(duì)列異常");
  }
  //保留隊(duì)列的front端的元素的值
  T oldValue = (T) elementData[front];
  //釋放隊(duì)列的front端的元素
  elementData[front++] = null;
  return oldValue;
 }
 /**
  * @Title: peek   
  * @Description: 返回隊(duì)列頂元素，但不刪除隊(duì)列頂元素  
  * @return
  */
 public T peek() {
  if (isEmpty()) {
   throw new IndexOutOfBoundsException("空隊(duì)列異常");
  }
  return (T) elementData[front];
 }
 /**
  * @Title: isEmpty   
  * @Description: 判斷順序隊(duì)列是否為空隊(duì)列  
  * @return
  */
 public boolean isEmpty() {
  return rear == front;
 }
 /**
  * @Title: clear   
  * @Description: 清空順序隊(duì)列
  */
 public void clear() {
  //將底層數(shù)組所有元素賦為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: 鏈?zhǔn)疥?duì)列
 * @date 2014年1月21日 下午3:24:38
 * @param <T>
 */
public class LinkQueue<T> implements Serializable{
 /**
  * @Fields serialVersionUID : TODO
  */
 private static final long serialVersionUID = -6726728595616312615L;
 //定義一個(gè)內(nèi)部類Node，Node實(shí)例代表鏈隊(duì)列的節(jié)點(diǎn)。
 private class Node {
  
  private T data;//保存節(jié)點(diǎn)的數(shù)據(jù)
  
  private Node next;//指向下個(gè)節(jié)點(diǎn)的引用
  //無(wú)參數(shù)的構(gòu)造器
  public Node() {
  }
  //初始化全部屬性的構(gòu)造器
  public Node(T data, Node next) {
   this.data = data;
   this.next = next;
  }
 }
 
 private Node front;//保存該鏈隊(duì)列的頭節(jié)點(diǎn)
 
 private Node rear;//保存該鏈隊(duì)列的尾節(jié)點(diǎn)
 private int size;//保存該鏈隊(duì)列中已包含的節(jié)點(diǎn)數(shù)
 /**
  * <p>Title: LinkQueue </p>   
  * <p>Description: 創(chuàng)建空鏈隊(duì)列 </p> 
  */
 public LinkQueue() {
  //空鏈隊(duì)列，front和rear都是null
  front = null;
  rear = null;
 }
 /**
  * <p>Title: LinkQueue </p>  
  * <p>Description: 以指定數(shù)據(jù)元素來(lái)創(chuàng)建鏈隊(duì)列，該鏈隊(duì)列只有一個(gè)元素</p> 
  */
 public LinkQueue(T element) {
  front = new Node(element, null);
  //只有一個(gè)節(jié)點(diǎn)，front、rear都指向該節(jié)點(diǎn)
  rear = front;
  size++;
 }
 /**
  * @Title: size   
  * @Description: 獲取順序隊(duì)列的大小  
  * @return
  */
 public int size() {
  return size;
 }
 /**
  * @Title: offer   
  * @Description: 入隊(duì)  
  * @param element
  */
 public void offer(T element) {
  //如果該鏈隊(duì)列還是空鏈隊(duì)列
  if (front == null) {
   front = new Node(element, null);   
   rear = front;//只有一個(gè)節(jié)點(diǎn)，front、rear都指向該節(jié)點(diǎn)
  } else {   
   Node newNode = new Node(element, null);//創(chuàng)建新節(jié)點(diǎn)   
   rear.next = newNode;//讓尾節(jié)點(diǎn)的next指向新增的節(jié)點(diǎn)   
   rear = newNode;//以新節(jié)點(diǎn)作為新的尾節(jié)點(diǎn)
  }
  size++;
 }
 /**
  * @Title: poll   
  * @Description: 出隊(duì)  
  * @return
  */
 public T poll() {
  Node oldFront = front;
  front = front.next;
  oldFront.next = null;
  size--;
  return oldFront.data;
 }
 /**
  * @Title: peek   
  * @Description: 返回隊(duì)列頂元素，但不刪除隊(duì)列頂元素  
  * @return
  */
 public T peek() {
  return rear.data;
 }
 /**
  * @Title: isEmpty   
  * @Description: 判斷順序隊(duì)列是否為空隊(duì)列  
  * @return
  */
 public boolean isEmpty() {
  return size == 0;
 }
 /**
  * @Title: clear   
  * @Description: 清空順序隊(duì)列
  */
 public void clear() {
  //將front、rear兩個(gè)節(jié)點(diǎn)賦為null
  front = null;
  rear = null;
  size = 0;
 }
 public String toString() {
  //鏈隊(duì)列為空鏈隊(duì)列時(shí)
  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");
  //添加兩個(gè)元素
  queue.offer("bbbb");
  queue.offer("cccc");
  System.out.println(queue);
  //刪除一個(gè)元素后
  queue.poll();
  System.out.println("刪除一個(gè)元素后的隊(duì)列：" + queue);
  //再次添加一個(gè)元素
  queue.offer("dddd");
  System.out.println("再次添加元素后的隊(duì)列：" + queue);
  //刪除一個(gè)元素后，隊(duì)列可以再多加一個(gè)元素
  queue.poll();
  //再次加入一個(gè)元素
  queue.offer("eeee");
  System.out.println(queue);
 }
}

package lang;
import java.io.Serializable;
import java.util.Arrays;
/**
 * @ClassName: LoopQueue
 * @Description: 循環(huán)隊(duì)列
 * @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;//保存數(shù)組的長(zhǎng)度
 private Object[] elementData;//定義一個(gè)數(shù)組用于保存循環(huán)隊(duì)列的元素
 private int front = 0;//隊(duì)頭
 private int rear = 0;//隊(duì)尾
 //以默認(rèn)數(shù)組長(zhǎng)度創(chuàng)建空循環(huán)隊(duì)列
 public LoopQueue() {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 //以一個(gè)初始化元素來(lái)創(chuàng)建循環(huán)隊(duì)列
 public LoopQueue(T element) {
  this();
  elementData[0] = element;
  rear++;
 }
 /**
  * 以指定長(zhǎng)度的數(shù)組來(lái)創(chuàng)建循環(huán)隊(duì)列
  * @param element 指定循環(huán)隊(duì)列中第一個(gè)元素
  * @param initSize 指定循環(huán)隊(duì)列底層數(shù)組的長(zhǎng)度
  */
 public LoopQueue(T element, int initSize) {
  this.capacity = initSize;
  elementData = new Object[capacity];
  elementData[0] = element;
  rear++;
 }
 //獲取循環(huán)隊(duì)列的大小
 public int size() {
  if (isEmpty()) {
   return 0;
  }
  return rear > front ? rear - front : capacity - (front - rear);
 }
 //插入隊(duì)列
 public void add(T element) {
  if (rear == front && elementData[front] != null) {
   throw new IndexOutOfBoundsException("隊(duì)列已滿的異常");
  }
  elementData[rear++] = element;
  //如果rear已經(jīng)到頭，那就轉(zhuǎn)頭
  rear = rear == capacity ? 0 : rear;
 }
 //移除隊(duì)列
 public T remove() {
  if (isEmpty()) {
   throw new IndexOutOfBoundsException("空隊(duì)列異常");
  }
  //保留隊(duì)列的rear端的元素的值
  T oldValue = (T) elementData[front];
  //釋放隊(duì)列的rear端的元素
  elementData[front++] = null;
  //如果front已經(jīng)到頭，那就轉(zhuǎn)頭
  front = front == capacity ? 0 : front;
  return oldValue;
 }
 //返回隊(duì)列頂元素，但不刪除隊(duì)列頂元素
 public T element() {
  if (isEmpty()) {
   throw new IndexOutOfBoundsException("空隊(duì)列異常");
  }
  return (T) elementData[front];
 }
 //判斷循環(huán)隊(duì)列是否為空隊(duì)列
 public boolean isEmpty() {
  //rear==front且rear處的元素為null
  return rear == front && elementData[rear] == null;
 }
 //清空循環(huán)隊(duì)列
 public void clear() {
  //將底層數(shù)組所有元素賦為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);
  //添加兩個(gè)元素
  queue.add("bbbb");
  queue.add("cccc");
  //此時(shí)隊(duì)列已滿
  System.out.println(queue);
  //刪除一個(gè)元素后，隊(duì)列可以再多加一個(gè)元素
  queue.remove();
  System.out.println("刪除一個(gè)元素后的隊(duì)列：" + queue);
  //再次添加一個(gè)元素，此時(shí)隊(duì)列又滿
  queue.add("dddd");
  System.out.println(queue);
  System.out.println("隊(duì)列滿時(shí)的長(zhǎng)度：" + queue.size());
  //刪除一個(gè)元素后，隊(duì)列可以再多加一個(gè)元素
  queue.remove();
  //再次加入一個(gè)元素，此時(shí)隊(duì)列又滿
  queue.add("eeee");
  System.out.println(queue);
 }
}