数据结构-队列Queue

女爷i 2021-09-23 11:04 338阅读 0赞

# 一、什么是队列 #

队列也是一种线性结构，相比数组，队列对应的操作是数组的子集，只能从一端（ 队尾）添加元素，也只能从另一端（队首）取出元素！队列是一种先进先出的数据结构（先到先得 ）First In First Out（FIFO）。队列又有数组队列和循环队列，相对于数组队列来说，循环队列具有更低的时间复杂度！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

# 二、数组队列的实现 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

#### **2.1 Queue接口** ####

package Queue;
    
    //队列
    public interface Queue<E> { 
    
        int getSize();
    
        boolean isEmpty();
    
        void enqueue(E e); //入队
    
        E dequeue(); //出队
    
        E getFront();//查看队首的元素
    }

#### **2.2 基于[动态数组][Link 1]来实现(实现类)** ####

package Queue;
    
    import Array.MyArray;
    
    public class ArrayQueue<E> implements Queue<E> { 
    
        private MyArray<E> array;
    
    
        //有参构造
        public ArrayQueue(int capacity) { 
            array = new MyArray<E>(capacity);
        }
    
        //无参构造
        public ArrayQueue() { 
            array = new MyArray<E>();
        }
    
    
        @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() { 
            return array.getFirst();
        }
    
        @Override
        public String toString() { 
            StringBuffer res = new StringBuffer();
            res.append("Queue:");
            res.append("Front [");
            for (int i = 0; i < array.getSize(); i++) { 
                res.append(array.get(i));
                if (i != array.getSize() - 1) { 
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    }

#### **2.3 编写测试类QueueMain以及运行结果截图** ####

package Queue;
    
    public class QueueMain { 
        public static void main(String[] args) { 
            ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
            for (int i = 0; i < 10; i++) { 
                queue.enqueue(i);
                System.out.println(queue);
                //每入队列三个取出一个
                if (i % 3 == 2) { 
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]

# 三、数组队列的复杂度分析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]  
出队时的时间复杂度为O(n),这是因为在出队的时候，我们每一次把整个数组的第一个元素，也就是索引为0的那个元素拿出来之后，数组中后面剩下的元素都要向前移动一个位置，这是在我们的动态数组中removeFirst()这个方法的逻辑，因此这个复杂度显然是O(n)的。在本次的测试中只有十个元素，因此我们进入一次队列是O(n)的复杂度也没有关系，但是如果数组要承载100w个元素的话，每次出队都要进行100w次的操作，这个时间性能的消耗显然已经太大了。那么有什么办法让队列在出队的时候相应的时间复杂度是O(1)同时入队的时候时间复杂度依然是O(1)，这个时候就应该想到循环队列了！

# 四、循环队列 #

在数组队列中，当队首元素出队的时候，后面剩下的元素都要向前移动一个位置，size--，这个就是出队的底层实现 ，因为都要向前移动一个位置，因此时间复杂度为O(n)，那么有什么办法可以让这些元素不向前移动一个位置呢？这个时候就需要创建一个循环队列了。在循环队列中，我们设置三个变量，分别是front, tail,size，用来指示队首元素的位置，队尾元素后一个空间的位置和元素的个数，当元素出队或者入队时，不需要再移动元素了，只需要维护一下变量的指向就好了。当出队时：front++；当入队时tail++。初始的情况下，队列中没有任何一个元素，在这种情况下front和tail都指向0，也就意味着队列为空。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]

#### **4.1 循环队列实现类** ####

package Queue;
    
    public class LoopQueue<E> implements Queue<E> { 
    
        private E[] data;
        //这两个变量分别指向队首和队尾的下一个位置的索引
        private int front, tail;
    
        private int size;//整个队列中元素
    
    
        public LoopQueue(int capacity) { 
            //对于循环队列 我们要有意识的浪费一个空间，因此在这里我们要提前添加一个空间
            data = (E[]) new Object[capacity + 1];
            front = 0;
            tail = 0;
            size = 0;
        }
    
        public LoopQueue() { 
            this(10);
        }
    
        public int getCapacity() { 
            return data.length - 1;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return front == tail;
        }
    
        //入队
        @Override
        public void enqueue(E e) { 
            if ((tail + 1) % data.length == front) { 
                resize(getCapacity() * 2);
            }
            data[tail] = e;
            tail = (tail + 1) % data.length;
            size++;
        }
    
        //出队
        @Override
        public E dequeue() { 
            if (isEmpty()) { 
                throw new IllegalArgumentException("Cannot dequeue from an empty queue");
            }
            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];
        }
    
    
        //扩容操作 将原来data中的元素发在newData中
        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;
        }
    
        @Override
        public String toString() { 
            StringBuffer res = new StringBuffer();
            res.append(String.format("Queue:size=%d,capacity=%d\n", size, getCapacity()));
            res.append("front [");
    
            for (int i = front; i != tail; i = (i + 1) % data.length) { 
                res.append(data[i]);
                if ((i + 1) % data.length != tail) { 
                    res.append(", ");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    }

#### **4.2 编写测试类LoopMain以及运行结果截图** ####

package Queue;
    
    public class LoopMain { 
        public static void main(String[] args) { 
    
            LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
            for (int i = 0; i < 10; i++) { 
                loopQueue.enqueue(i);
                System.out.println(loopQueue);
                //每入队列三个取出一个
                if (i % 3 == 2) { 
                    loopQueue.dequeue();
                    System.out.println(loopQueue);
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]  **Bug小结**   
在编写扩容操作的时候，由于将data = newData;front = 0;tail = size;这三行代码放在了for循环中(如下)从而出现了null值(如下截图)

//扩容操作 将原来data中的元素发在newData中
        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;
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]

# 五、循环队列的复杂度分析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 7]  
 **编写测试类来测试比较数组队列和循环队列运行opCount个enqueue和dequeue操作所需的时间**

package Queue;
    
    import java.util.Random;
    
    //测试主函数 用来测试数组队列和循环队列的时间复杂度
    public class Main { 
    
        //测试使用q运行opCount个enqueue和dequeue操作所需的时间 单位：秒
        private static double testQueue(Queue<Integer> q, int opCount) { 
            //System.nanoTime()的返回值只和进程已运行的时间有关, 不受调系统时间影响.返回值为纳秒
            long startTime = System.nanoTime();
    
            //执行队列的入队和出队
            Random random = new Random();
            for (int i = 0; i < opCount; i++) { 
                q.enqueue(random.nextInt(Integer.MAX_VALUE));
            }
            for (int i = 0; i < opCount; i++) { 
                q.dequeue();
            }
            long endTime = System.nanoTime();
    
            return (endTime - startTime) / 1000000000.0;//将纳秒转化为秒
        }
    
        public static void main(String[] args) { 
            int opCount = 100000;
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
            double time1 = testQueue(arrayQueue, opCount);
            System.out.println("ArrayQueue, time:" + time1 + "s");
    
            LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
            double time2 = testQueue(loopQueue, opCount);
            System.out.println("loopQueue, time:" + time2 + "s");
        }
    }

测试截图  
![在这里插入图片描述][20191116164336892.png]  
  
通过运行结果，我们可以很明显的看出，当进行大量的数据入队和出队的时候，数组队列花费的时间要远远超出循环队列所运行的时间，这也就是我们优化算大的意义所在！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/6978ab8492b048729300442141e4b21a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/57e2357a59d6474f81e99a78ef528cf8.png
[Link 1]: https://blog.csdn.net/qq_43229543/article/details/103055051
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/316c6e58c20e4a9f8a7a934c995a0f26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/5d81ba14b99941bfa064aa575d0156f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/f5da5f3bf9d842cea19ee2da7f6ae94b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/617ce05f9daf4b5b8315348a305828a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]: /images/20210923/480158ea57e1495db47aebf3b6bd6e03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 7]: /images/20210923/9b6393dedad445059049a06febde4bb6.png
[20191116164336892.png]: /images/20210923/b0f6bb16112a468c9e285e35a1faa96b.png