内容简介：数据结构学习之——队列与循环队列队列(Queue)同栈(stack)一样也是一种运算收限的线性数据结构，参考：数据结构之——栈。栈即：LIFO(Last In First Out),队列则是FIFO(First In First Out)，也就是说队列这种数据结构仅允许在一端(队尾)添加元素，在另一端(队首)删除元素，所以说队列是一种先进先出的数据结构。可以将队列想象成银行柜台的排队机制一样，在前面排队的人可以先办理业务，在最后排队的人等到前面所有的人办理完毕后，才可以进行业务的处理，如图：队列同Array
数据结构学习之——队列与循环队列
- 什么是队列(Queue)
- 队列基于动态数组的实现及时间复杂度分析
- 优化队列
- 循环队列(LoopQueue)
什么是队列(Queue)
队列(Queue)同栈(stack)一样也是一种运算收限的线性数据结构，参考：数据结构之——栈。栈即：LIFO(Last In First Out),队列则是FIFO(First In First Out)，也就是说队列这种数据结构仅允许在一端(队尾)添加元素，在另一端(队首)删除元素，所以说队列是一种先进先出的数据结构。可以将队列想象成银行柜台的排队机制一样，在前面排队的人可以先办理业务，在最后排队的人等到前面所有的人办理完毕后，才可以进行业务的处理，如图：
队列基于动态数组的实现及时间复杂度分析
队列同ArrayStack的实现一样，都需要基于动态数组作为底层实现。
在 设计模式 上，同ArrayStack一样，设计的是Queue这样一个接口，并创建ArrayQueue这样一个类implements这个接口，Queue接口的方法与Stack栈的方法大体相同，只不过我们将入栈push设计成enqueue(入队)，出栈pop设计为dequeue(出队)。接口代码如下：
public interface Queue<E>{
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean is Empty();
}
复制代码
ArrayQueue代码如下：
public class ArrayQueue<E> implements Queue<E>{
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
if(array.isEmpty)
throw new IllegalArgumentException("ArrayQueue is Empty");
return array.get(0)
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("Queue:\n");
sb.append("front:[");
for(int i=0;i<getSize();i++){
sb.append(array.get(i));
if(i!=getSize()-1){
sb.append(",");
}else{
sb.append("]tail");
}
}
return sb.toString();
}
}
复制代码
时间复杂度分析如下：
E getFront(); int getSize(); boolean is Empty(); 复制代码
以上方法，时间复杂度为：O(1)。
void enqueue(E e); 复制代码
因为入队操作相当于在动态数组的尾部添加元素，虽然有resize()这样一个O(n)级别的算法，但是以均摊时间复杂度分析，enqueue操作仍然是一个O(1)级别的算法。
E dequeue(); 复制代码
dequeue()操作相当于动态数组的removeFirst()操作，在数组的头部删除一个元素，array[0] 后面的所有元素都需要向前挪动一个位置，所以dequeue出队是一个O(n)级别的算法。
综上分析，ArrayQueue还是有些不完美的地方，ArrayStack所有的操作均为O(1)级别的算法，但是基于动态数组实现的队列ArrayQueue 在出队操作dequeue上性能还是略显不足，LoopQueue(循环队列)就优化了ArrayQueue出队这样一个问题。
优化ArrayQueue
我们已经知道了，ArrayQueue美中不足的地方就在于dequeue这样一个操作是O(n)级别的算法。出现这个问题的原因实际上是因为每次进行出队操作时，动态数组都需要将array[0]后面所有的元素向前挪动一个单位，但实际上想一想这个过程并不“划算”，因为，队列元素的数量达到万以上的级别时，仅仅删除一个元素，我们就需要将所有的元素进行一次大换血。和银行柜台业务办理的排队不同，银行柜台的一号办理人办理完毕，后面所有的人只需要上前一小步就可以了，但是对于计算机来讲，每一个数据的调整都需要计算机亲历躬行。有什么办法可以避免这种大规模的动辄呢？我们可以使用两个变量去维护队列的队首和队尾。
假设变量为front和tail。front维护队首，变量tail维护队尾，当front==tail时，队列为空，每增加一个元素，tail就像后移动一个单位，所以我们需要多使用一个空间去维护 tail这样一个变量，这样我们在设计模式上就需要开辟用户指定的capacity加1的数组空间。对于用户来讲，capacity==n,但实际上真正的capacity也就是data.length==n+1,因为我们需要多浪费一个空间去维护tail这个变量，但是浪费这样一个空间相比于dequeue的大换血O(n)操作也是值得的。
示例：enqueue元素“D”上述思路优化后的队列MyQueue代码如下：
public class MyQueue<E> implements Queue<E> {
private int front;
private int tail;
private E[]data;
public MyQueue(int capacity){
data = (E[])new Object[capacity+1];
}
public MyQueue(){
this(10);
}
@Override
public int getSize(){
return tail-front;
}
@Override
public boolean isEmpty(){
return front==tail;
}
@Override
public E getFront(){
return data[front];
}
private void resize(int newCapacity){
E[]newData = (E[])new Object[newCapacity+1];
for(int i=0;i<(tail-front);i++){
newData[i] = data[front+i];
}
data = newData;
tail = tail - front;
front = 0;
}
@Override
public void enqueue(E e){
if(tail == data.length-1)
resize((tail-front)*2);
data[tail] = e;
tail++;
}
@Override
public E dequeue(){
E ret = data[front];
// Loitering Object
data[front] = null;
front++;
if(((tail-front)==(data.length-1)/4) && (data.length-1)/2!=0)
resize((data.length-1)/2);
return ret;
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("MyQueue size=%d,capacity=%d\n",tail-front,data.length-1));
stringBuilder.append("front:[");
for(int i=front;i<tail;i++){
stringBuilder.append(data[i]);
if((i+1)!=tail){
stringBuilder.append(",");
}
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
}
复制代码
MyQueue对ArrayQueue进行了优化操作，原本dequeue需要O(n)的时间复杂度，进行优化后，dequeue由O(n)的时间复杂度变为了均摊O(1)的时间复杂度。这里面需要注意的是：MyQueue的enqueue入队操作规定了tail == data.length-1时进行“扩容”操作，这里面扩容二字我使用了双引号，因为有可能这个“扩容”实际上是缩容。
我们规定了enqueue操作中，
if(tail == data.length-1)
resize((tail-front)*2);
复制代码
在上图的示例中，如果reisze，我们实际上就相当于进行了缩容的操作。我们这样的设计看起来解决了问题，但仍然不灵活，我们希望在入队时的resize只涉及到扩容，出队时的resize只涉及缩容，我们是否能对这样的需求进行优化呢？
循环队列(LoopQueue)
循环队列的思想和ArrayQueue优化后的MyQueue大体相同，只不过循环队列里面加入了更加巧妙的循环机制。
上例中,我们规定tail == data.length-1队列为满进行resize,但是这一次我们换一种思路。当继续向当前队列添加元素时，我们这样做：
变量tail重新回到了起点，这也就是循环队列称之为“循环”的意义所在。那么什么时候表示当前队列已满需要进行resize呢？
当front == (tail+1)%data.length，当这个条件成立时，也就说明了队列为满，需要进行扩容操作了。循环队列实现代码如下：
public class LoopQueue<E> implements Queue<E> {
private E[]data;
private int front;
private int tail;
public LoopQueue(int capacity){
data = (E[])new Object[capacity+1];
}
public LoopQueue(){
this(10);
}
@Override
public int getSize(){
if(tail<front)
return data.length-(front-tail);
else{
return tail-front;
}
}
public int getCapacity(){
return data.length-1;
}
@Override
public boolean isEmpty(){
return getSize()==0;
}
private void resize(int newCapacity){
E[]newData = (E[])new Object[newCapacity+1];
for(int i=0;i<getSize();i++){
newData[i] = data[(i+front)%data.length];
}
data = newData;
tail = getSize();
front = 0;
}
@Override
public void enqueue(E e){
if(front==(tail+1)%data.length)
resize(2*getSize());
data[tail] = e;
tail = (tail+1)%data.length;
}
@Override
public E dequeue(){
E ret = data[front];
// Loitering Object
data[front] = null;
front = (front+1)%data.length;
if(getSize() == getCapacity()/4 && getCapacity()/2!=0){
resize(getCapacity()/2);
}
return ret;
}
@Override
public E getFront(){
if(getSize()==0)
throw new IllegalArgumentException("LoopQueue is empty");
return data[front];
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("LoopQueue size:%d,capacity:%d\n",getSize(),getCapacity()));
stringBuilder.append("front:[");
for(int i=front;i!=tail;i=(i+1)%data.length){
stringBuilder.append(data[i]);
if((i+1)%data.length!=tail)
stringBuilder.append(",");
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
}
复制代码
现在我们对ArrayQueue,LoopQueue进行性能上的测试，
import java.util.Random;
public class Main {
private static double testQueue(Queue<Integer>q,int testCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i=0;i<testCount;i++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i=0;i<testCount;i++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime-startTime)/1000000000.0;
}
public static void main(String[]args){
int testCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue,testCount);
double arrayQueueTime = testQueue(arrayQueue,testCount);
System.out.println("LoopQueue:"+loopQueueTime);
System.out.println("ArrayQueue"+arrayQueueTime);
}
}
复制代码
在jdk1.8的环境下测试结果为：
导致两者之间造成巨大差异的结果就是dequeue操作，ArrayQueue的dequeue操作为O(n)级别的算法，而LoopQueue的dequeue操作 在均摊的时间复杂度上为O(1)。
以上所述就是小编给大家介绍的《数据结构之——队列与循环队列》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Docker开发指南
[英] Adrian Mouat / 黄彦邦 / 人民邮电出版社 / 2017-4 / 79.00元
Docker容器轻量和可移植的特性尤其适用于动态和分布式的环境，它的兴起给软件开发流程带来了一场革命。本书对Docker进行了全面讲解，包括开发、生产以至维护的整个软件生命周期，并对其中可能出现的一些问题进行了探讨，如软件版本差异、开发环境与生产环境的差异、系统安全问题，等等。一起来看看 《Docker开发指南》 这本书的介绍吧!
