數據結構-隊列

數據結構-隊列

隊列（queue）在計算機科學中，是一種先進先出的線性表。

它只允許在表的前端進行刪除操作，而在表的後端進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

基於自定義數組實現的隊列

新建queue接口，用來規範所有queue子類

package com.datastructure.queue;
import java.awt.*;
/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 16:44
 **/
public class LoopQueue implements Queue {
 private E[] data;
 //指向隊列的第一個元素，初始指向0
 private int front;
 //指向隊列的最後一個元素的後一個位置，初始指向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);
 }
 /**
 * 因為容量放的時候多了個1，所以get容量的時候，需要減1
 * @return
 */
 public int getCapacity(){
 return data.length-1;
 }
 /**
 * 1.if((tail + 1) % data.length == front) 如果tail + 1 超過了data.length的大小，
 * 代表當前tail指向已經超出了容量的大小，因為是循環式，所以需要tail去循環頭元素中查看值是否有被佔用，
 * 如果 == front 代表循環頭沒有，就需要擴容了。
 * 2.舉例： 元素容量為8，tail目前指向7 front 指向2
 * if((7 + 1) % 8 == 2 ) if(0 == 2) 這裡是false，因為front指向了2，所以代表 第0,1位是沒有值的
 * 所以這個值需要在在第0位放(空間利用)
 * 3.data[tail] = param tail當前指向的地方需要賦值，然後tail自增 循環體 的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 ++ ;
 }
 /**
 * 擴充隊列的容量 

 * 1.front代表了當前元素初始位置的指向
 * 2.newData的第i位元素，應該等於 i + front % data.length 的值
 * 3.舉例：元素容量20，i 等於 0 ，front 等於 2，結果： newData[0] = data[(0 + 2) % 20]
 * = data[2] 意思就是，newData的第一位元素，應該等於data有值的第一位元素
 * % data.length 的原因主要是為了防止數組越界錯誤
 * 4.新數組賦值完成需要將 front 重新指向0，因為新數組的front指針是從0開始的。
 * 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.如果隊列為空拋出異常
 * 2.用ret變量來接受當前隊列頭的值
 * 3.接收成功之後將，隊列頭元素置空
 * 4.front指針指向下一個元素
 * 5.size大小-1
 * 6.如果size大小佔據了容量的1/4和size為容量的1/2且不等於0的時候，對容量進行縮減，縮減為原來容量的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;
 }
 /**
 * 當front和tail的值相等時，隊列為空，初始兩個指向的是同一個值（只有初始的時候，指向的是同一個地方）
 * @return
 */
 @Override
 public boolean isEmpty() {
 return front == tail;
 }
 /**
 * 1.元素從 front位置開始循環遍歷，i的值不能等於tail，
 * 也就是到tail的前一位，i = i + 1 且%data.length，
 * 因為i有可能從循環頭重新開始
 * 2.( i + 1 ) % data.length != tail 如果當前i + 1 % data.length
 * 不等於tail表示不到最後一個元素，就拼接，
 * @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實現類

package com.datastructure.queue;
import com.datastructure.array.Array;
/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 18:19
 **/
public class ArrayQueue implements Queue{
 Array array;
 public ArrayQueue(int capacity){
 array=new Array(capacity);
 }
 public ArrayQueue(){
 array=new Array();
 }
 @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> sb.append(array.get(i));
 if(i!=array.getSize()-1){
 sb.append(", ");
 }
 }
 sb.append("] tail");
 return sb.toString();
 }
}
/<array.getsize>

測試類

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);
 }
 }
 }
}
/<integer>

測試結果

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

可以看到測試結果是正確的，也符合隊列結構的數據存取，但是因為是基於自定義數組來實現的，所以會調用數組方法的removeFirst方法，刪除第一個元素的同時，會重新將後面所有元素前移，索引前移，均攤時間複雜度為O(n)。

循環隊列

循環隊列中有兩個新詞，兩個指針

• front 指向隊列的第一個元素，初始指向0
• tail 指向隊列的最後一個元素的後一個位置，初始指向0

什麼是循環隊列

建立一個loopqueue實現queue接口

package com.datastructure.queue;
import java.awt.*;
/**
 * @program: test
 * @description:
 * @author: Mr.Yang
 * @create: 2019-05-03 16:44
 **/
public class LoopQueue implements Queue {
 private E[] data;
 //指向隊列的第一個元素，初始指向0
 private int front;
 //指向隊列的最後一個元素的後一個位置，初始指向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);
 }
 /**
 * 因為容量放的時候多了個1，所以get容量的時候，需要減1
 * @return
 */
 public int getCapacity(){
 return data.length-1; 

 }
 /**
 * 1.if((tail + 1) % data.length == front) 如果tail + 1 超過了data.length的大小，
 * 代表當前tail指向已經超出了容量的大小，因為是循環式，所以需要tail去循環頭元素中查看值是否有被佔用，
 * 如果 == front 代表循環頭沒有，就需要擴容了。
 * 2.舉例： 元素容量為8，tail目前指向7 front 指向2
 * if((7 + 1) % 8 == 2 ) if(0 == 2) 這裡是false，因為front指向了2，所以代表 第0,1位是沒有值的
 * 所以這個值需要在在第0位放(空間利用)
 * 3.data[tail] = param tail當前指向的地方需要賦值，然後tail自增 循環體 的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 ++ ;
 }
 /**
 * 擴充隊列的容量
 * 1.front代表了當前元素初始位置的指向
 * 2.newData的第i位元素，應該等於 i + front % data.length 的值
 * 3.舉例：元素容量20，i 等於 0 ，front 等於 2，結果： newData[0] = data[(0 + 2) % 20]
 * = data[2] 意思就是，newData的第一位元素，應該等於data有值的第一位元素
 * % data.length 的原因主要是為了防止數組越界錯誤 

 * 4.新數組賦值完成需要將 front 重新指向0，因為新數組的front指針是從0開始的。
 * 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.如果隊列為空拋出異常
 * 2.用ret變量來接受當前隊列頭的值
 * 3.接收成功之後將，隊列頭元素置空
 * 4.front指針指向下一個元素
 * 5.size大小-1
 * 6.如果size大小佔據了容量的1/4和size為容量的1/2且不等於0的時候，對容量進行縮減，縮減為原來容量的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;
 }
 /**
 * 當front和tail的值相等時，隊列為空，初始兩個指向的是同一個值（只有初始的時候，指向的是同一個地方）
 * @return
 */
 @Override
 public boolean isEmpty() {
 return front == tail;
 }
 /**
 * 1.元素從 front位置開始循環遍歷，i的值不能等於tail，
 * 也就是到tail的前一位，i = i + 1 且%data.length，
 * 因為i有可能從循環頭重新開始
 * 2.( i + 1 ) % data.length != tail 如果當前i + 1 % data.length
 * 不等於tail表示不到最後一個元素，就拼接，
 * @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(); 

 }
}

測試代碼

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);
 }
 }
 }
}
/<integer>

測試結果

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

打印結果跟自定義數組的結果是一樣的，但是因為引用了指針這個概念，刪除的時候索引不會重排，均攤時間複雜度為O(1)