数据结构-队列
定义
队列（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<E> implements Queue<E> {
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<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();
}
}
测试类
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);
}
}
}
}
测试结果
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
a.gif
建立一个loopqueue实现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;
//指向队列的第一个元素，初始指向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);
}
}
}
}
测试结果
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)
