雙向順序隊(duì)列ArrayDeque和雙向鏈?zhǔn)疥?duì)列LinkedList，JDK已經(jīng)包含，在此略。ArrayDeque包括順序棧和順序隊(duì)列，LinkedList包含鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列。ArrayDeque和LinkedList都是線程不安全的。PriorityQueue優(yōu)先隊(duì)列也在JDK。
成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)服務(wù)團(tuán)隊(duì)是一支充滿著熱情的團(tuán)隊(duì)，執(zhí)著、敏銳、追求更好，是創(chuàng)新互聯(lián)的標(biāo)準(zhǔn)與要求，同時(shí)竭誠(chéng)為客戶提供服務(wù)是我們的理念。創(chuàng)新互聯(lián)建站把每個(gè)網(wǎng)站當(dāng)做一個(gè)產(chǎn)品來開發(fā)，精雕細(xì)琢，追求一名工匠心中的細(xì)致，我們更用心！
1.順序隊(duì)列的實(shí)現(xiàn)
package lang; import java.io.Serializable; import java.util.Arrays; /** * @ClassName: ArrayQueue * @Description: 順序隊(duì)列 * @date 2014年1月20日 下午3:46:19 * @param*/ public class ArrayQueue 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è)初始化元素來創(chuàng)建順序隊(duì)列 public ArrayQueue(T element) { this(); elementData[0] = element; rear++; } public ArrayQueue(int initSize) { elementData = new Object[initSize]; } /** * 以指定長(zhǎng)度的數(shù)組來創(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(); } } }
2. 鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)
package lang; import java.io.Serializable; /** * @ClassName: LinkQueue * @Description: 鏈?zhǔn)疥?duì)列 * @date 2014年1月21日 下午3:24:38 * @param*/ public class LinkQueue 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)的引用 //無參數(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ù) /** * Title: LinkQueue
*Description: 創(chuàng)建空鏈隊(duì)列
*/ public LinkQueue() { //空鏈隊(duì)列，front和rear都是null front = null; rear = null; } /** *Title: LinkQueue
*Description: 以指定數(shù)據(jù)元素來創(chuàng)建鏈隊(duì)列，該鏈隊(duì)列只有一個(gè)元素
*/ 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) { LinkQueuequeue = new LinkQueue ("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); } }
3. 循環(huán)隊(duì)列的實(shí)現(xiàn)
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 LoopQueueimplements 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è)初始化元素來創(chuàng)建循環(huán)隊(duì)列 public LoopQueue(T element) { this(); elementData[0] = element; rear++; } /** * 以指定長(zhǎng)度的數(shù)組來創(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 queue = new LoopQueue ("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); } }
以上這篇java隊(duì)列實(shí)現(xiàn)方法(順序隊(duì)列,鏈?zhǔn)疥?duì)列,循環(huán)隊(duì)列)就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持創(chuàng)新互聯(lián)。
重慶分公司
重慶分公司
