java隊(duì)列實(shí)現(xiàn)方法(順序隊(duì)列,鏈?zhǔn)疥?duì)列,循環(huán)隊(duì)列)
更新時(shí)間：2017年12月18日 15:00:52 作者：jiutianhe
下面小編就為大家分享一篇java隊(duì)列實(shí)現(xiàn)方法(順序隊(duì)列,鏈?zhǔn)疥?duì)列,循環(huán)隊(duì)列)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
雙向順序隊(duì)列ArrayDeque和雙向鏈?zhǔn)疥?duì)列LinkedList，JDK已經(jīng)包含，在此略。ArrayDeque包括順序棧和順序隊(duì)列，LinkedList包含鏈?zhǔn)綏：玩準(zhǔn)疥?duì)列。ArrayDeque和LinkedList都是線程不安全的。PriorityQueue優(yōu)先隊(duì)列也在JDK。
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 <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ù)組的長度
private Object[] elementData;//定義一個(gè)數(shù)組用于保存順序隊(duì)列的元素
private int front = 0;//隊(duì)頭
private int rear = 0;//隊(duì)尾
//以默認(rèn)數(shù)組長度創(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];
}
/**
* 以指定長度的數(shù)組來創(chuàng)建順序隊(duì)列
* @param element 指定順序隊(duì)列中第一個(gè)元素
* @param initSize 指定順序隊(duì)列底層數(shù)組的長度
*/
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ù)組的原有長度小于目前所需的長度
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 <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)的引用
//無參數(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ù)元素來創(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);
}
}
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 LoopQueue<T> implements Serializable{
/**
* @Fields serialVersionUID : TODO
*/
private static final long serialVersionUID = -3670496550272478781L;
private int DEFAULT_SIZE = 10;
private int capacity;//保存數(shù)組的長度
private Object[] elementData;//定義一個(gè)數(shù)組用于保存循環(huán)隊(duì)列的元素
private int front = 0;//隊(duì)頭
private int rear = 0;//隊(duì)尾
//以默認(rèn)數(shù)組長度創(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++;
}
/**
* 以指定長度的數(shù)組來創(chuàng)建循環(huán)隊(duì)列
* @param element 指定循環(huán)隊(duì)列中第一個(gè)元素
* @param initSize 指定循環(huán)隊(duì)列底層數(shù)組的長度
*/
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í)的長度：" + 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ì)列)就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
java使用Feign實(shí)現(xiàn)聲明式Restful風(fēng)格調(diào)用
這篇文章主要為大家詳細(xì)介紹了java使用Feign實(shí)現(xiàn)聲明式Restful風(fēng)格調(diào)用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-04-04
Java的Socket實(shí)現(xiàn)長連接以及數(shù)據(jù)的發(fā)送和接收方式
這篇文章主要介紹了Java的Socket實(shí)現(xiàn)長連接以及數(shù)據(jù)的發(fā)送和接收方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
SpringBoot使用druid配置多數(shù)據(jù)源問題
這篇文章主要介紹了SpringBoot使用druid配置多數(shù)據(jù)源問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
Java實(shí)現(xiàn)讀取鍵盤輸入保存到txt文件,再統(tǒng)計(jì)并輸出每個(gè)單詞出現(xiàn)次數(shù)的方法
這篇文章主要介紹了Java實(shí)現(xiàn)讀取鍵盤輸入保存到txt文件,再統(tǒng)計(jì)并輸出每個(gè)單詞出現(xiàn)次數(shù)的方法,涉及java文件I/O操作及字符串遍歷、運(yùn)算實(shí)現(xiàn)統(tǒng)計(jì)功能相關(guān)技巧,需要的朋友可以參考下2017-07-07
Mybatis foreach標(biāo)簽使用不當(dāng)導(dǎo)致異常的原因淺析
這篇文章主要介紹了Mybatis foreach標(biāo)簽使用不當(dāng)導(dǎo)致異常的原因探究,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-12-12
springboot中validator數(shù)據(jù)校驗(yàn)功能的實(shí)現(xiàn)
這篇文章主要介紹了springboot中validator數(shù)據(jù)校驗(yàn)功能,校驗(yàn)分為普通校驗(yàn)和分組校驗(yàn)，每種校驗(yàn)方式通過實(shí)例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2021-10-10
MyBatis Mapper XML中比較操作符轉(zhuǎn)義問題解決
在使用MyBatis編寫Mapper XML時(shí),有時(shí)會(huì)遇到比較操作符需要進(jìn)行轉(zhuǎn)義的情況,本文主要介紹了MyBatis Mapper XML中比較操作符轉(zhuǎn)義問題解決,具有一定的參考價(jià)值,感興趣的可以了解一下2024-01-01
java中用數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列的示例代碼
這篇文章主要介紹了java中用數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-04-04
java去除空格、標(biāo)點(diǎn)符號(hào)的方法實(shí)例
這篇文章主要給大家介紹了關(guān)于java去除空格、標(biāo)點(diǎn)符號(hào)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要介紹了使用java實(shí)現(xiàn)的京東商城登陸示例,需要的朋友可以參考下2014-03-03