内容简介:数据结构-队列队列(queue)在计算机科学中,是一种先进先出的线性表。它只允许在表的前端进行删除操作,而在表的后端进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
数据结构-队列
定义
队列(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
建立一个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)
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。