📚队列-DS笔记

数组队列

数组队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（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)

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

使用栈实现队列

使用队列实现栈

链表

链表的几个要点：

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

链表的实现

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.javapublic class LinkedListQueue<E> implements Queue<E> {    // 定义一个节点    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过程虽然还需赋值（旧数组元素拷贝到新数组），但该拷贝过程是远远快于对内存的操作的