基礎(chǔ)知識(shí)
隊(duì)列是一種特殊的線性表，他的特殊性在于我們只能操作他頭部和尾部的元素冲粤，中間的元素我們操作不了，我們只能在他的頭部進(jìn)行刪除页眯，尾部進(jìn)行添加梯捕。就像大家排隊(duì)到銀行取錢一樣，先來(lái)的肯定要排到前面窝撵，后來(lái)的只能排在隊(duì)尾傀顾，所有元素都要遵守這個(gè)操作，沒(méi)有VIP會(huì)員碌奉，所以走后門插隊(duì)的現(xiàn)象是不可能存在的短曾，他是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)寒砖。我們來(lái)看一下隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是什么樣的
1，一般隊(duì)列
他只能從左邊進(jìn)嫉拐，右邊出哩都，隊(duì)列實(shí)現(xiàn)方式一般有兩種，一種是基于數(shù)組的婉徘，還一種是基于鏈表的漠嵌，如果基于鏈表的倒還好說(shuō)，因?yàn)殒湵淼拈L(zhǎng)度是隨時(shí)都可以變的判哥，這個(gè)實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單献雅。如果是基于數(shù)組的，就會(huì)稍微有點(diǎn)不同塌计，因?yàn)閿?shù)組的大小在初始化的時(shí)候就已經(jīng)固定了挺身，我們來(lái)看一下基于數(shù)組的實(shí)現(xiàn)，假如我們初始化一個(gè)長(zhǎng)度是10的隊(duì)列
front指向的是隊(duì)列的頭锌仅，tail指向的是隊(duì)列尾的下一個(gè)存儲(chǔ)空間章钾，最初始的時(shí)候front=0，tail=0热芹，每添加一個(gè)元素tail就加1贱傀，每移除一個(gè)元素front就加1，但是這樣會(huì)有一個(gè)問(wèn)題伊脓，如果一個(gè)元素不停的加入隊(duì)列府寒，然后再不停的從隊(duì)列中移除，會(huì)導(dǎo)致tail和front越來(lái)越大报腔，最后會(huì)導(dǎo)致隊(duì)列無(wú)法再加入數(shù)據(jù)了株搔，但實(shí)際上隊(duì)列前面全部都是空的，這導(dǎo)致空間的極大浪費(fèi)纯蛾。我們自己來(lái)寫一個(gè)簡(jiǎn)單的隊(duì)列看一下
public class MyQueue<E> {
private final Object[] data;
private final int maxSize;
private int size;
private int front = 0;
private int tail = 0;
public MyQueue(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("隊(duì)列容量必須大于0 : " + maxSize);
}
this.maxSize = maxSize;
data = new Object[this.maxSize];
}
public void add(E e) {
if (isFull()) {//這地方可以擴(kuò)容也可以拋異常纤房，為了方便這里我們就不在擴(kuò)容了。
throw new IllegalStateException("隊(duì)列已經(jīng)滿了翻诉，無(wú)法再加入……");
}
data[tail++] = e;
size++;
}
public E remove() {
if (isEmpty()) {
throw new IllegalStateException("隊(duì)列是空的炮姨，無(wú)法移除……");
}
E t = (E) data[front];
data[front++] = null;
size--;
return t;
}
//隊(duì)列頭和隊(duì)列尾指向同一空間的時(shí)候，并且沒(méi)到隊(duì)尾碰煌，表示隊(duì)列是空的
public boolean isEmpty() {
return front == tail && !isFull();
}
public boolean isFull() {//最后一個(gè)位置是不存儲(chǔ)數(shù)據(jù)的
return tail == maxSize - 1;
}
public int getSize() {
return size;
}
}
代碼非常簡(jiǎn)單舒岸，當(dāng)然隊(duì)列的實(shí)現(xiàn)不一定是這一種方式，比如我們可以讓tail指向隊(duì)尾的元素拄查，或者以鏈表的形式來(lái)實(shí)現(xiàn)都是可以的吁津，不同的實(shí)現(xiàn)方式會(huì)導(dǎo)致上面的方法有所不同。我們來(lái)測(cè)試一下
public static void main(String[] args) {
MyQueue myQueue = new MyQueue(10);
System.out.println("isEmpty()=" + myQueue.isEmpty());
System.out.println("isFull()=" + myQueue.isFull());
System.out.println("getSize()=" + myQueue.getSize());
for (int i = 0; i < 9; i++) {
myQueue.add(i * 100);
myQueue.remove();
}
System.out.println("----------------------------");
System.out.println("isEmpty()=" + myQueue.isEmpty());
System.out.println("isFull()=" + myQueue.isFull());
System.out.println("getSize()=" + myQueue.getSize());
}
看一下打印的結(jié)果
isEmpty()=true
isFull()=false
getSize()=0
----------------------------
isEmpty()=false
isFull()=true
getSize()=0
我們添加了9次堕扶，然后又移除了9次碍脏，結(jié)果隊(duì)列竟然滿了，如果我們?cè)偬砑右淮蔚脑捒隙〞?huì)拋異常稍算，但實(shí)際上隊(duì)列的size是0典尾，還是空的，也就是說(shuō)數(shù)組的每個(gè)位置只能使用一次糊探，這樣就造成了極大的浪費(fèi)钾埂。那么前面使用過(guò)的空間還能不能再次利用了呢，實(shí)際上是可以的科平，我們可以把隊(duì)列看成是環(huán)形的褥紫，當(dāng)tail到達(dá)數(shù)組末尾的時(shí)候，如果數(shù)組的前面有空位子瞪慧，我們可以讓tail從頭開始髓考，這個(gè)時(shí)候一個(gè)新的隊(duì)列就產(chǎn)生了，那就是雙端隊(duì)列弃酌。
2氨菇，雙端隊(duì)列
雙端隊(duì)列也是有兩個(gè)指針，front指向隊(duì)首妓湘，tail指向隊(duì)尾的下一個(gè)存儲(chǔ)單元查蓉，并且雙端隊(duì)列的隊(duì)首和隊(duì)尾都可以添加和刪除元素，我們來(lái)看一下圖
這樣空間就可以循環(huán)利用了榜贴，不會(huì)造成浪費(fèi)豌研，我們來(lái)看下代碼
public class MyQueue<E> {
//存儲(chǔ)的元素
private Object[] data;
//指向隊(duì)列頭，這個(gè)頭并不是數(shù)組的第0個(gè)元素唬党，如果這樣
// front就沒(méi)有意義了鹃共，這個(gè)從下面的addFirst(E e)方
// 法也可以看出，如果當(dāng)front等于0的時(shí)候初嘹，在添加到
// first及汉，那么會(huì)添加到數(shù)組的末尾，并且front也指向
// 數(shù)組的末尾
private int front;
//指向隊(duì)列尾的下一個(gè)空間屯烦，可以這樣理解坷随，front指向
// 的是第一個(gè)元素，tail指向的是最后一個(gè)元素的下一
// 個(gè)驻龟，指的是空的温眉。
private int tail;
public MyQueue(int numElements) {
data = new Object[numElements];
}
//空間擴(kuò)容，我們這里選擇擴(kuò)大一倍翁狐，當(dāng)然也可以選擇其
// 他值类溢，僅僅當(dāng)滿的時(shí)候才能觸發(fā)擴(kuò)容， 這時(shí)候front
// 和tail都會(huì)指向同一個(gè)元素
private void doubleCapacity() {
int p = front;
int n = data.length;//數(shù)組的長(zhǎng)度
//關(guān)鍵是r不好理解，舉個(gè)例子闯冷，在數(shù)組中砂心，front
// 不一定是之前0位置的，他可以指向其他位置蛇耀，
// 比如原來(lái)空間大小為16辩诞，front為13，也就是第
// 14個(gè)元素（數(shù)組是從0開始的）纺涤，那么r就是16-13=3译暂，
// 也就是從front往后還有多少元素，待會(huì)copy的時(shí)候
// 也是先從最后的r個(gè)元素開始
int r = n - p;
Object[] a = new Object[n << 1];//擴(kuò)大一倍
System.arraycopy(data, p, a, 0, r);//先copy后面的r個(gè)
System.arraycopy(data, 0, a, r, p);//再copy前面的p個(gè)
data = a;
//重新調(diào)整front和tail的值
front = 0;
tail = n;
}
public void addFirst(E e) {
//添加到front的前面撩炊，所以front-1
front = (front - 1 + data.length) % data.length;
data[front] = e;
if (front == tail)//判斷是否滿了
doubleCapacity();
}
public void addLast(E e) {
//添加到最后一個(gè)外永，這個(gè)方法和addFirst有很明顯的不同，
// addFirst是添加的時(shí)候就要計(jì)算front的位置拧咳，而addLast
// 方法是存值之后在計(jì)算tail的伯顶，/因?yàn)閠ail位置是沒(méi)有
// 存值的，他表示的末端元素的下一個(gè)呛踊，是空砾淌，所以存值之后
//要計(jì)算tail的值
data[tail] = e;
tail = (tail + 1) % data.length;
if (tail == front)//判斷是否滿
doubleCapacity();
}
public E removeFirst() {//刪除第一個(gè)
if (isEmpty())
throw new IllegalStateException("隊(duì)列是空的，無(wú)法移除……");
E result = (E) data[front];
data[front] = null;
// 刪除第一個(gè)谭网，這里的所有第一我們都認(rèn)為是front所指的汪厨，
// 不是數(shù)組的0位置，然后在計(jì)算front的值
front = (front + 1) % data.length;
return result;
}
public E removeLast() {//刪除最后一個(gè)
if (isEmpty())
throw new IllegalStateException("隊(duì)列是空的愉择，無(wú)法移除……");
tail = (tail - 1 + data.length) % data.length;
E result = (E) data[tail];
data[tail] = null;
return result;
}
public E peekFirst() {
if (isEmpty())
throw new IllegalStateException("隊(duì)列是空的劫乱，無(wú)法獲取……");
return (E) data[front];
}
public E peekLast() {
if (isEmpty())
throw new IllegalStateException("隊(duì)列是空的，無(wú)法獲取……");
return (E) data[(tail - 1 + data.length) % data.length];
}
public int size() {//元素的size
return (tail - front + data.length) % data.length;
}
//是否為空锥涕，在上面添加元素的時(shí)候也可能front==tail衷戈，當(dāng)添加
// 元素之后front==tail的時(shí)候就認(rèn)為是滿了，然后擴(kuò)容层坠，重新
// 調(diào)整front和tail的值,所以擴(kuò)容之后front就不可能等于tail殖妇。
//如果沒(méi)有觸發(fā)上面添加元素的時(shí)候front等于tail我們就認(rèn)為他是空的。
public boolean isEmpty() {
return front == tail;
}
}
代碼中都有詳細(xì)的注釋破花，就不在過(guò)多介紹谦趣。
