📚 队列-DS笔记

阅读原文时间：2022年03月24日阅读：1

数组队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。遵循先进先出（FIFO）原则。

【数组队列代码实现】

先定义一个Queue接口

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


import com.algorithm.week3.c1.Array;
public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

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

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

    @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() {
        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();
    }
}

百度百科：

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。

循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有 front == tail，而当所有队列空间全占满时，也有 front == tail。

为了区别这两种情况，规定循环队列最多只能有 MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是 front == tail，而队列判满的条件是 front ==（tail+1) % MaxSize

图1.空队列

图2.插入元素，tail++

图3.删除队头元素front++

图4. 继续队尾添加元素

图5. 第一个位置空闲，便可将元素加入到第一个位置

图6.计算循环索引

public LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front, tail;
    private int size;

    public LoopQueue(int capacity) {
        data = new Object[capacity + 1]; // 循环队列中空闲了一个空间
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void equeue(E e) {
        // 首先判断队列是否满了
        if (front == (tail + 1) % data.length) {
            // 扩容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue 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;
    }

    public 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;
    }
}

数组队列和循环队列比较

复杂度
- 循环队列：E dequeue()，O(1)
- 数组队列：E dequeue()，O(n)

使用动态数组实现栈和队列

使用栈实现队列

使用队列实现栈

链表的几个要点：

虚拟头结点，能解决很多问题（有时候短的链表，就会出现一些我们逻辑操作越界的问题）。
要注意先处理后面的结点，避免改指针时找不到它了，必要时用临时指针存着。
用好双指针！

链表的实现

public class LinkedList<E> {

    public class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }
    public Node(E e) {
        this(e, null);
    }
    public Node() {
        this(null, null);
    }
    @Override
    public String toString() { return e.toString(); }
    }

    private Node dummyHead;
    private int size;

    public LinkedList() {
        dummyHead = new Node(null, null);  // 虚拟头结点
        size = 0;
    }
    public int getSize() { return size; }

    public boolean isEmpty() { return size== 0;}

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index error.");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index - 1; i++)
            prev = prev.next;
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        // prev.next = new Node(e, prev.next);
        size++;
    }
    public void addFirst(E e) {
        add(0, e);
    }
    public void addLast(E e) { add(size, e); }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Index error.");
        }
        Node prev = dummyHead;
        // 找到待删除节点的前一结点
        for (int i = 0; i < index; i++)
            prev = prev.next;
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;
        return retNode.e;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void set(int index, E e) {
        if (index <  0 || index >= size)
            throw new IllegalArugmentException("Index error");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;
        cur.e = e;
    }

    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.next != null & cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }
    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        Node cur = dummyHead.next;
        while (cur != null) {
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }
 }

用链表实现栈

Stack.java

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

LinkedListStack.java

public LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;  // 先声明一个链表

    public LinkedListStack() {
        list = new LinkedList<>();
    }

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

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

    @Override
    public void push(E e) {
        list.addFirst(e); // 插入栈顶
    }

    @Override
    public E pop() {
        return list.removeFirst(); // 弹出栈顶元素
    }

    @Override
    public E peek() {
        return list.getFirst();  // 查看栈顶元素
    }
}

改进链表

从head端删除元素，从tail端插入元素

没有dummyHead，需注意链表为空的情况

// LinkedListQueue.java
public class LinkedListQueue implements Queue {
// 定义一个节点
private class Node {
public E e;
public Node next;

    public Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }
    public Node(E e) {
        this(e, null);
    }
    public Node() {
        this(null, null);
    }
}

private Node head, tail;
private size;

public LinkedListQueue() {}

@Override
public int getSize() { return size; }

@Override
public boolean isEmpty() { return size==0; }

@Override
public void enqueue(E e) {
    if (tail == null) {
        tail = new Node(e);
        head = tail;
    } else {
        tail.next = new Node(e);
        tail = tail.next;
    }
    size++;
}
@Override
public E dequeue() {
    if (isEmpty()) throw new IllegalArgumentException("queue is empty!");Node retNode = head;
head = head.next;
retNode.next = null;
if (head == null)
    tail = null;
size--;
return retNode.e;}
@Override
public E getFront() {
    if (isEmpty()) throw new IllegalArgumentException("queue is empty!");
    return head.e;
}

}

链表的性能问题

虽然只在链表表头添加元素，时间复杂度O(1)，同时，使用链表不需要resize，直觉上链表性能更好；

But，实际上，当数据量达一定程度，其性能是更差的，因为：

对于链表，每添加一个元素，都需要重新创建一个Node类对象（需要进行一次new内存操作），这是非常慢的。

为什么即使有resize，对大规模数据，动态数组还是快于链表？

对动态数组，一方面，每次resize容量倍增，但对大规模数据，实际上触发resize次数非常少的

resize的过程，一次申请一大片内存空间。链表每次申请一个空间

申请一次10万的空间远远快于10万次1的空间。

相较于堆内存空间的操作，动态数组的resize过程虽然还需赋值（旧数组元素拷贝到新数组），但该拷贝过程是远远快于对内存的操作的

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

synchronized中wait、notify的原理与源码

MQTT vs. XMPP，哪一个才是IoT通讯协议的正解

在.NET Framework中使用RocketMQ（阿里云版）实战【第二章】

《HelloGitHub》第 87 期

在.NET Framework中使用RocketMQ（阿里云版）实战【第一章】

Java - ReentrantLock锁分析

万字长文硬核AQS源码分析

深入解析React DnD拖拽原理，轻松掌握拖放技巧！

快手Java一面11问（附参考答案）

JUC同步锁原理源码解析五----Phaser