java队列实现方法(顺序队列,链式队列,循环队列)

双向顺序队列ArrayDeque和双向链式队列LinkedList，JDK已经包含，在此略。ArrayDeque包括顺序栈和顺序队列，LinkedList包含链式栈和链式队列。ArrayDeque和LinkedList都是线程不安全的。PriorityQueue优先队列也在JDK。

1.顺序队列的实现

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();
 }
}
}

2. 链式队列的实现

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);
}
}

3. 循环队列的实现

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);
}
}

来源：http://blog.csdn.net/jiutianhe/article/details/18606295