玩转数据结构（六）基于动态数组的队列

「爱情、让人受尽委屈。」 2022-05-21 08:37 167阅读 0赞

队列是先进先出的线性表。在具体应用中通常使用链表或者数组来实现。队列只允许在后端进行入队操作(enqueue)，在前端进行出队操作(dequeue)。如下图示例：

![70][]

<图片来源于百度>

下面我们基于数组实现一个队列。

数组对象在之前的博客中已经讲过：[封装自己的Array对象][Array]

### 1、队列接口 ###

public interface Queue<E> {
        int getSize();
        void enqueue(E e);
        E dequeue();
        E getFront();
        boolean isEmpty();
    }

### 2、实现代码 ###

public class ArrayQueue<E> implements Queue<E> {
        //自定义数组对象
        private Array<E> array;
    
        //初始化
        public ArrayQueue() {
            this(10);
        }
    
        public ArrayQueue(int capacity) {
            array = new Array<E>(capacity);
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @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 boolean isEmpty() {
            return array.isEmpty();
        }
    
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            str.append(String.format("ArrayQueue: size=%d, capacity=%d ", array.getSize(), array.getCapacity()));
            str.append("front [");
            for(int i = 0; i < array.getSize(); i++) {
                str.append(array.get(i));
                if(i != array.getSize()-1) {
                    str.append(",");
                }
            }
            str.append("]");
    
            return str.toString();
        }
    }

### 3、测试代码 ###

public static void main(String[] args) {
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
            for (int i = 0; i < 12; i++) {
                arrayQueue.enqueue(i);
                System.out.println(arrayQueue);
    
                if(i % 3 == 2) {//每个3次入队，就出队一次
                    arrayQueue.dequeue();
                    System.out.println(arrayQueue);
                }
            }
        }

### 4、结果 ###

ArrayQueue: size=1, capacity=10 front [0]
    ArrayQueue: size=2, capacity=10 front [0,1]
    ArrayQueue: size=3, capacity=10 front [0,1,2]
    ArrayQueue: size=2, capacity=10 front [1,2]
    ArrayQueue: size=3, capacity=10 front [1,2,3]
    ArrayQueue: size=4, capacity=10 front [1,2,3,4]
    ArrayQueue: size=5, capacity=10 front [1,2,3,4,5]
    ArrayQueue: size=4, capacity=10 front [2,3,4,5]
    ArrayQueue: size=5, capacity=10 front [2,3,4,5,6]
    ArrayQueue: size=6, capacity=10 front [2,3,4,5,6,7]
    ArrayQueue: size=7, capacity=10 front [2,3,4,5,6,7,8]
    ArrayQueue: size=6, capacity=10 front [3,4,5,6,7,8]
    ArrayQueue: size=7, capacity=10 front [3,4,5,6,7,8,9]
    ArrayQueue: size=8, capacity=10 front [3,4,5,6,7,8,9,10]
    ArrayQueue: size=9, capacity=10 front [3,4,5,6,7,8,9,10,11]
    ArrayQueue: size=8, capacity=10 front [4,5,6,7,8,9,10,11]
    ArrayQueue: size=3, capacity=10 front [9,10,11]

### 5、时间复杂度分析 ###

在入队时，Array对象的底层是将新数据直接放到数组的末尾，时间复杂度为O（1）；

在出队时，Array对象的底层是将数组首部元素移除，之后需要进行数组移位操作，因此时间复杂度为O（n）;

[70]: /images/20220521/3a09de4dad5547d3a54903b4c6a7a422.png
[Array]: https://blog.csdn.net/zhoujian_Liu/article/details/80900912