数据结构与算法(七):队列

数据结构与算法 2020-04-25 494 次浏览 本文字数:2447字

本文主要内容:队列、双端队列

队列

1.队列是一种特殊的线性表,只能在头尾两端操作

2.队尾(rear):只能从队尾添加元素,一般叫做入队(enQueue)

3.队头(front):只能从队头移除元素,一般叫做出队(deQueue)

4.队列内部实现可以使用动态数组或双向链表实现

5.优先使用双向链表,因为队列主要往头尾操作元素

6.先进先出原则:First In First Out(FIFO)

队列基本展示

队列的接口设计

1.public lit size();

2.public boolean isEmpty();

3.public void enQueue(E element);

4.public void deQueue();

5.public E front();

队列的实现

public class Queue<E> {
    private List<E> list = new LinkedList<>();
    
    //元素数量
    public int size() {
        return list.size();
    }

    //是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    //入队 说明:官方API为add()或offer()
    public void enQueue(E element) {
        list.add(element);
    }

    //出队 说明:官方API为remove()或poll()
    public E deQueue() {
        return list.remove(0);
    }

    //获取队列头元素 说明:官方API为peek()
    public E front() {
        return list.get(0);
    }
}

双端队列

双端队列是可以在头尾两端进行添加、删除的队列
双端队列展示

双端队列接口设计

1.public lit size();

2.public boolean isEmpty();

3.public void enQueueFront(E element);

4.publiv void enQueueRear(E element);

5.public void deQueueFront();

6.public void deQueueRear();

7.public E front();

8.public E rear();

双端队列的实现

public class Deque<E> {
    private List<E> list = new LinkedList<>();
    
    // 元素的数量
    public int size() {
        return list.size();
    }

    // 是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 从队头出队
    public E deQueueFront() {
        return list.remove(0);
    }

    // 从队头入队
    public void enQueueFront(E element) {
        list.add(0, element);
    }

    // 从队尾入队
    public void enQueueRear(E element) {
        list.add(element);
    }

    // 从队尾出队
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }

    // 获取队列的头元素
    public E front() {
        return list.get(0);
    }

    // 获取队列的尾元素
    public E rear() {
        return list.get(list.size() - 1);
    }
}

本文由 WarlockMT 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。