（二）数组队列

我会带着你远行 2022-05-14 11:25 188阅读 0赞

*  前言
 *  已实现方法
 *  复杂度分析
 *  java代码

--------------------

# 前言 #

实现自己的 `数组队列`，底层利用之前实现的 `动态数组` ；实现的接口和 `java` 队列实现的接口，基本一致 ；在 `动态数组` 的基础上进行二次封装，很简单；

--------------------

# 已实现方法 #

![写个鸡儿的描述，谁看呢][70]

--------------------

# 复杂度分析 #

对于 `deQueue()` 的复杂度是 `O(n)` ，因为，每次移走队首元素，我们都要让后面的元素，移上来，这对于数组来说，是个很费时的操作 ；

我们是可以利用 **`循环队列`** 将 `deQueue()` 的复杂度降低到 `O(1)` ；

--------------------

# java代码 #

---------------- 队列接口 -----------------
    
    package xin.ijava.quene;
    
    /** * * 队列抽取的接口 * @author An */
    @SuppressWarnings("unused")
    public interface Queue<E> {
    
        /** * 获取队列中的实际元素个数 * @return 元素个数 */
        int getSize()  ;
    
        /** * 队列是否为空 * @return 队列的情况 */
        boolean isEmpty() ;
    
        /** * 获取当其队列的队首元素 * @return 队首元素 */
        E getFront();
    
        /** * 移除当前队首元素 * @return 队首元素 */
        E deQueue() ;
    
        /** * 将元素添加到 队尾 * @param e 目标元素 */
        void enQueue(E e) ;
    
    }
    
    
    ------------- 数组队列 实现类 --------------
    
    package xin.ijava.quene;
    
    import xin.ijava.array.Array;
    
    /** * 数组队列，底层利用动态数组实现 * <p> * ------------- 复杂度分析 ------------- * <p> * getSize() O(1) : * isEmpty() O(1) ; * deQueue() O(n) ； * enQueue() O(1) 均摊 ; * getFront() O(1) ; * <p> * 除了 deQueue() 的复杂度为： O(n) ，其他都是常数级别的复杂化的 ； * 对于 deQueue() 的复杂度，可以使用循环队列，将其 复杂度降低到 O(1) ; * * @author An */
    @SuppressWarnings("unused")
    public class ArrayQueue<E> implements Queue<E> { 
        /** * 底层维护着一个 Array 动态数组 */
        private Array<E> array;
    
    
        public ArrayQueue() {
            array = new Array<E>();
        }
    
        public ArrayQueue(int capacity) {
            array = new Array<E>(capacity);
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }
    
        @Override
        public E getFront() {
            return array.getFirst();
        }
    
        @Override
        public E deQueue() {
            return array.removeFirst();
        }
    
        @Override
        public void enQueue(E e) {
            array.addLast(e);
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append(String.format("ArrayQueue : size = %d , capacity = %d \n", getSize(), array.getCapacity()));
            res.append("Front [ ");
            for (int i = 0; i < getSize(); i++) {
                res.append(array.get(i));
                if (i != getSize() - 1) {
                    res.append(", ");
                }
            }
            res.append(" ] Tail ");
            return res.toString() ;
        }
    }

[70]: /images/20220514/02199119f6424f42ae62d231a1283b69.png