利用动态数组实现队列

利用动态数组实现队列

  1. 队列是一种先进先出的数据结构First in First out(FIFO)
  2. 队列的至少应该实现以下接口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package StacksAndQueues.ArrayQueue;

/**
* @ Description: Queue接口
* @ Date: Created in 20:49 11/07/2018
* @ Author: Anthony_Duan
*/
public interface Queue<E> {
//获取队列的长度
int getSize();

//判断队列是否为空
boolean isEmpty();

//入队
void enqueue(E e);

//出队
E dequeue();

//得到队列尾部的元素的值
E getFront();
}
  1. 利用动态数组实现队列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    package StacksAndQueues.ArrayQueue;

    /**
    * @ Description: 利用动态数组作为底层实现队列接口 包括动态增长与缩减
    * @ Date: Created in 20:52 11/07/2018
    * @ Author: Anthony_Duan
    */
    public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity) {
    array = new Array<E>(capacity);
    }

    public ArrayQueue() {
    array = new Array<E>();
    }

    @Override
    public int getSize() {
    return array.getSize();
    }

    @Override
    public boolean isEmpty() {
    return array.isEmpty();
    }

    @Override
    public void enqueue(E e) {
    array.addLast(e);
    }

    /**
    * 出队操作的时间复杂度为O(n)
    *
    * @return
    */
    @Override
    public E dequeue() {
    return array.removeFirst();
    }

    @Override
    public E getFront() {
    return array.getFirst();
    }

    @Override
    public String toString() {
    StringBuilder res = new StringBuilder();
    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. 利用动态数组实现队列的复杂度分析

  • void enqueue(E e);————O(1)均摊
  • E dequeue();——————O(n)
  • E getFront();——————O(1)
  • int getSize();——————O(1)
  • boolean isEmpty();———O(1)
-------------End Of This ArticleThank You For Reading-------------