雙向順序隊列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); }}以上這篇java隊列實現方法(順序隊列,鍊式隊列,循環隊列)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持武林網。