數(shù)據(jù)結(jié)構(gòu)-隊(duì)列
定義
隊(duì)列（queue）在計(jì)算機(jī)科學(xué)中杭攻，是一種先進(jìn)先出的線(xiàn)性表狮腿。
它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾辣垒，進(jìn)行刪除操作的端稱(chēng)為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)源葫，稱(chēng)為空隊(duì)列雄坪。
基于自定義數(shù)組實(shí)現(xiàn)的隊(duì)列
新建queue接口，用來(lái)規(guī)范所有queue子類(lèi)
package com.datastructure.queue;
import java.awt.*;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-03 16:44
**/
public class LoopQueue<E> implements Queue<E> {
private E[] data;
//指向隊(duì)列的第一個(gè)元素匹厘，初始指向0
private int front;
//指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置嘀趟，初始指向0
private int tail;
private int size;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity+1];
front=0;
tail=0;
size=0;
}
public LoopQueue(){
this(10);
}
/**
* 因?yàn)槿萘糠诺臅r(shí)候多了個(gè)1，所以get容量的時(shí)候愈诚，需要減1
* @return
*/
public int getCapacity(){
return data.length-1;
}
/**
* 1.if((tail + 1) % data.length == front) 如果tail + 1 超過(guò)了data.length的大小她按，
* 代表當(dāng)前tail指向已經(jīng)超出了容量的大小牛隅，因?yàn)槭茄h(huán)式，所以需要tail去循環(huán)頭元素中查看值是否有被占用尤溜，
* 如果 == front 代表循環(huán)頭沒(méi)有倔叼，就需要擴(kuò)容了。
* 2.舉例： 元素容量為8宫莱，tail目前指向7 front 指向2
* if((7 + 1) % 8 == 2 ) if(0 == 2) 這里是false丈攒，因?yàn)閒ront指向了2，所以代表 第0,1位是沒(méi)有值的
* 所以這個(gè)值需要在在第0位放(空間利用)
* 3.data[tail] = param tail當(dāng)前指向的地方需要賦值授霸，然后tail自增 循環(huán)體 的1巡验，size+1
* @param param
*/
@Override
public void enqueue(E param) {
if((tail + 1) % data.length == front){
resize(getCapacity() * 2);
}
data[tail] = param ;
tail = (tail + 1) % data.length;
size ++ ;
}
/**
* 擴(kuò)充隊(duì)列的容量
* 1.front代表了當(dāng)前元素初始位置的指向
* 2.newData的第i位元素，應(yīng)該等于 i + front % data.length 的值
* 3.舉例：元素容量20碘耳，i 等于 0 显设，front 等于 2，結(jié)果： newData[0] = data[(0 + 2) % 20]
* = data[2] 意思就是辛辨，newData的第一位元素捕捂，應(yīng)該等于data有值的第一位元素
* % data.length 的原因主要是為了防止數(shù)組越界錯(cuò)誤
* 4.新數(shù)組賦值完成需要將 front 重新指向0，因?yàn)樾聰?shù)組的front指針是從0開(kāi)始的斗搞。
* tail最后要指向等于size大小的值指攒，
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i++){
newData[i] = data[(i + front ) % data.length];
}
data=newData;
front = 0 ;
tail = size;
}
/**
* 1.如果隊(duì)列為空拋出異常
* 2.用ret變量來(lái)接受當(dāng)前隊(duì)列頭的值
* 3.接收成功之后將，隊(duì)列頭元素置空
* 4.front指針指向下一個(gè)元素
* 5.size大小-1
* 6.如果size大小占據(jù)了容量的1/4和size為容量的1/2且不等于0的時(shí)候僻焚，對(duì)容量進(jìn)行縮減允悦，縮減為原來(lái)容量的1/2
* 7.返回ret變量
* @return
*/
@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("dequeue is fail ,because queue is empty");
}
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size -- ;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0 ){
resize(getCapacity() / 2 );
}
return ret;
}
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("queue is empty");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
/**
* 當(dāng)front和tail的值相等時(shí)，隊(duì)列為空虑啤，初始兩個(gè)指向的是同一個(gè)值（只有初始的時(shí)候隙弛，指向的是同一個(gè)地方）
* @return
*/
@Override
public boolean isEmpty() {
return front == tail;
}
/**
* 1.元素從 front位置開(kāi)始循環(huán)遍歷，i的值不能等于tail狞山，
* 也就是到tail的前一位全闷，i = i + 1 且%data.length，
* 因?yàn)閕有可能從循環(huán)頭重新開(kāi)始
* 2.( i + 1 ) % data.length != tail 如果當(dāng)前i + 1 % data.length
* 不等于tail表示不到最后一個(gè)元素萍启，就拼接室埋，
* @return
*/
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append(String.format("Array: size = %d , capacity = %d\n", size, getCapacity()));
sb.append("front [");
for (int i = front; i != tail ; i = (i + 1) % data.length) {
sb.append(data[i]);
if (( i + 1 ) % data.length != tail) {
sb.append(", ");
}
}
sb.append("] tail");
return sb.toString();
}
}
新建ArrayQueue實(shí)現(xiàn)類(lèi)
package com.datastructure.queue;
import com.datastructure.array.Array;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-03 18:19
**/
public class ArrayQueue<E> implements Queue<E>{
Array<E> array;
public ArrayQueue(int capacity){
array=new Array<E>(capacity);
}
public ArrayQueue(){
array=new Array<E>();
}
@Override
public void enqueue(E param) {
array.addLast(param);
}
@Override
public E dequeue() {
return array.removeFirst();
}
@Override
public E getFront() {
return array.getFirst();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append("front: ");
sb.append("[");
for(int i=0;i<array.getSize();i++){
sb.append(array.get(i));
if(i!=array.getSize()-1){
sb.append(", ");
}
}
sb.append("] tail");
return sb.toString();
}
}
測(cè)試類(lèi)
package com.datastructure.queue;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-03 18:26
**/
public class QueueTest {
public static void main(String[] args) {
ArrayQueue<Integer> integerArrayQueue = new ArrayQueue<>();
for (int i = 0; i < 10; i++) {
integerArrayQueue.enqueue(i);
System.out.println(integerArrayQueue);
if(i % 3 == 2){
integerArrayQueue.dequeue();
System.out.println(integerArrayQueue);
}
}
}
}
測(cè)試結(jié)果
front: [0] tail
front: [0, 1] tail
front: [0, 1, 2] tail
front: [1, 2] tail
front: [1, 2, 3] tail
front: [1, 2, 3, 4] tail
front: [1, 2, 3, 4, 5] tail
front: [2, 3, 4, 5] tail
front: [2, 3, 4, 5, 6] tail
front: [2, 3, 4, 5, 6, 7] tail
front: [2, 3, 4, 5, 6, 7, 8] tail
front: [3, 4, 5, 6, 7, 8] tail
front: [3, 4, 5, 6, 7, 8, 9] tail
可以看到測(cè)試結(jié)果是正確的，也符合隊(duì)列結(jié)構(gòu)的數(shù)據(jù)存取伊约，但是因?yàn)槭腔谧远x數(shù)組來(lái)實(shí)現(xiàn)的姚淆，所以會(huì)調(diào)用數(shù)組方法的removeFirst方法，刪除第一個(gè)元素的同時(shí)屡律，會(huì)重新將后面所有元素前移腌逢，索引前移，均攤時(shí)間復(fù)雜度為O(n)超埋。
循環(huán)隊(duì)列
循環(huán)隊(duì)列中有兩個(gè)新詞搏讶，兩個(gè)指針
- front 指向隊(duì)列的第一個(gè)元素佳鳖，初始指向0
- tail 指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置，初始指向0
a.gif
建立一個(gè)loopqueue實(shí)現(xiàn)queue接口
package com.datastructure.queue;
import java.awt.*;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-03 16:44
**/
public class LoopQueue<E> implements Queue<E> {
private E[] data;
//指向隊(duì)列的第一個(gè)元素媒惕，初始指向0
private int front;
//指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置系吩，初始指向0
private int tail;
private int size;
public LoopQueue(int capacity){
data = (E[]) new Object[capacity+1];
front=0;
tail=0;
size=0;
}
public LoopQueue(){
this(10);
}
/**
* 因?yàn)槿萘糠诺臅r(shí)候多了個(gè)1，所以get容量的時(shí)候妒蔚，需要減1
* @return
*/
public int getCapacity(){
return data.length-1;
}
/**
* 1.if((tail + 1) % data.length == front) 如果tail + 1 超過(guò)了data.length的大小穿挨，
* 代表當(dāng)前tail指向已經(jīng)超出了容量的大小，因?yàn)槭茄h(huán)式肴盏，所以需要tail去循環(huán)頭元素中查看值是否有被占用科盛，
* 如果 == front 代表循環(huán)頭沒(méi)有，就需要擴(kuò)容了菜皂。
* 2.舉例： 元素容量為8贞绵，tail目前指向7 front 指向2
* if((7 + 1) % 8 == 2 ) if(0 == 2) 這里是false，因?yàn)閒ront指向了2恍飘，所以代表 第0,1位是沒(méi)有值的
* 所以這個(gè)值需要在在第0位放(空間利用)
* 3.data[tail] = param tail當(dāng)前指向的地方需要賦值榨崩，然后tail自增 循環(huán)體 的1，size+1
* @param param
*/
@Override
public void enqueue(E param) {
if((tail + 1) % data.length == front){
resize(getCapacity() * 2);
}
data[tail] = param ;
tail = (tail + 1) % data.length;
size ++ ;
}
/**
* 擴(kuò)充隊(duì)列的容量
* 1.front代表了當(dāng)前元素初始位置的指向
* 2.newData的第i位元素章母，應(yīng)該等于 i + front % data.length 的值
* 3.舉例：元素容量20蜡饵，i 等于 0 ，front 等于 2胳施，結(jié)果： newData[0] = data[(0 + 2) % 20]
* = data[2] 意思就是，newData的第一位元素肢专，應(yīng)該等于data有值的第一位元素
* % data.length 的原因主要是為了防止數(shù)組越界錯(cuò)誤
* 4.新數(shù)組賦值完成需要將 front 重新指向0舞肆，因?yàn)樾聰?shù)組的front指針是從0開(kāi)始的。
* tail最后要指向等于size大小的值博杖，
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i++){
newData[i] = data[(i + front ) % data.length];
}
data=newData;
front = 0 ;
tail = size;
}
/**
* 1.如果隊(duì)列為空拋出異常
* 2.用ret變量來(lái)接受當(dāng)前隊(duì)列頭的值
* 3.接收成功之后將椿胯，隊(duì)列頭元素置空
* 4.front指針指向下一個(gè)元素
* 5.size大小-1
* 6.如果size大小占據(jù)了容量的1/4和size為容量的1/2且不等于0的時(shí)候，對(duì)容量進(jìn)行縮減剃根，縮減為原來(lái)容量的1/2
* 7.返回ret變量
* @return
*/
@Override
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("dequeue is fail ,because queue is empty");
}
E ret = data[front];
data[front] = null;
front = (front + 1) % data.length;
size -- ;
if(size == getCapacity() / 4 && getCapacity() / 2 != 0 ){
resize(getCapacity() / 2 );
}
return ret;
}
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("queue is empty");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
/**
* 當(dāng)front和tail的值相等時(shí)哩盲，隊(duì)列為空，初始兩個(gè)指向的是同一個(gè)值（只有初始的時(shí)候狈醉，指向的是同一個(gè)地方）
* @return
*/
@Override
public boolean isEmpty() {
return front == tail;
}
/**
* 1.元素從 front位置開(kāi)始循環(huán)遍歷廉油，i的值不能等于tail，
* 也就是到tail的前一位苗傅，i = i + 1 且%data.length抒线，
* 因?yàn)閕有可能從循環(huán)頭重新開(kāi)始
* 2.( i + 1 ) % data.length != tail 如果當(dāng)前i + 1 % data.length
* 不等于tail表示不到最后一個(gè)元素，就拼接渣慕，
* @return
*/
@Override
public String toString(){
StringBuffer sb = new StringBuffer();
sb.append(String.format("Array: size = %d , capacity = %d\n", size, getCapacity()));
sb.append("front [");
for (int i = front; i != tail ; i = (i + 1) % data.length) {
sb.append(data[i]);
if (( i + 1 ) % data.length != tail) {
sb.append(", ");
}
}
sb.append("] tail");
return sb.toString();
}
}
測(cè)試代碼
package com.datastructure.queue;
/**
* @program: test
* @description:
* @author: Mr.Yang
* @create: 2019-05-03 18:26
**/
public class QueueTest {
public static void main(String[] args) {
LoopQueue<Integer> integerArrayQueue = new LoopQueue<>();
for (int i = 0; i < 10; i++) {
integerArrayQueue.enqueue(i);
System.out.println(integerArrayQueue);
if(i % 3 == 2){
integerArrayQueue.dequeue();
System.out.println(integerArrayQueue);
}
}
}
}
測(cè)試結(jié)果
Array: size = 1 , capacity = 10
front [0] tail
Array: size = 2 , capacity = 10
front [0, 1] tail
Array: size = 3 , capacity = 10
front [0, 1, 2] tail
Array: size = 2 , capacity = 5
front [1, 2] tail
Array: size = 3 , capacity = 5
front [1, 2, 3] tail
Array: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Array: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Array: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Array: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Array: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Array: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Array: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Array: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail
打印結(jié)果跟自定義數(shù)組的結(jié)果是一樣的嘶炭，但是因?yàn)橐昧酥羔樳@個(gè)概念抱慌，刪除的時(shí)候索引不會(huì)重排，均攤時(shí)間復(fù)雜度為O(1)
