数据结构(五)-队列

参考文献

队列

• 先进先出(FIFO)

package com.holelin.queue;

/**
 * ClassName: Queue
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public interface Queue<E> {
    /**
     * 将元素添加至队尾
     *
     * @param e 需入队的元素
     */
    void enqueue(E e);

    /**
     * 将队头元素出队
     *
     * @return 队头元素的值
     */
    E dequeue();

    /**
     * 获得队头元素
     *
     * @return 队头元素
     */
    E getFront();

    /**
     * 获得队中元素的个数
     *
     * @return 队中元素的个数
     */
    int getSize();

    /**
     * 判断队是否为空
     *
     * @return 若为空则返回true;反之返回false;
     */
    boolean isEmpty();
}

顺序队列:数组实现队列

package com.holelin.queue;

import com.holelin.array.Array;

/**
 * ClassName: ArrayQueue
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public class ArrayQueue<E> implements Queue<E> {
    private Array<E> mArray;

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

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

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

    @Override
    public E dequeue() {
        return mArray.removeFirst();
    }

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

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

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d, capacity = %d\n", mArray.getSize(), mArray.getCapacity()));
        res.append("front [");
        for (int i = 0; i < mArray.getSize(); i++) {
            res.append(mArray.get(i));
            if (i != mArray.getSize() - 1) {
                res.append(",");
            }
        }
        res.append("] tail ");
        return res.toString();
    }
}

测试用例

package com.holelin.queue;

/**
 * ClassName: ArrayQueueTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 21; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }
        for (int i = 0; i < 11; i++) {
            queue.dequeue();
            System.out.println(queue);
        }

    }
}

链式队列:链表实现队列

package com.holelin.queue;

/**
 * ClassName: LinkedListQueue
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class LinkedListQueue<E> implements Queue<E> {
    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        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("Cannot dequeue from an empty queue.");
        }
        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if (head == null) {
            tail = null;
        }
        size--;
        return retNode.data;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return head.data;
    }

    @Override
    public String toString() {

        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");
        Node cur = head;
        while (cur != null) {
            res.append(cur).append("->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return  res.toString();
    }

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

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

    private class Node {
        /**
         * 数据域
         */
        E data;
        /**
         * 指针域
         */
        Node next;

        /**
         * 将传入的参数 连接到this指向的结点的后面
         *
         * @param data 后面的结点数据域
         * @param next 后面的结点指针域
         */
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

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

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

测试用例

package com.holelin.queue;

/**
 * ClassName: LinkedListQueueTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class LinkedListQueueTest {
    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }
        for (int i = 0; i < 5; i++) {
            queue.dequeue();
            System.out.println(queue);
        }
    }
}

循环队列

package com.holelin.queue;

/**
 * ClassName: LoopQueue
 * 循环队列
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/27
 */

public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    /**
     * 队头元素指针
     */
    private int front;
    /**
     * 队尾元素指针
     */
    private int tail;
    /**
     * 队列中元素的个数
     */
    private int size;

    /**
     * 设置指定容量的构造函数
     *
     * @param capacity 指定容量
     */
    public LoopQueue(int capacity) {
        // 需要浪费一个空间
        this.data = (E[]) new Object[capacity + 1];
        this.front = 0;
        this.tail = 0;
        this.size = 0;
    }

    /**
     * 默认容量的构造函数
     */
    public LoopQueue() {
        // 需要浪费一个空间
        this(10);
    }

    /**
     * 获取队列的容量
     *
     * @return
     */
    public int getCapcity() {
        return data.length - 1;
    }

    /**
     * 入队
     *
     * @param e 需入队的元素
     */
    @Override
    public void enqueue(E e) {
        if ((tail + 1) % data.length == front) {
            // 队列是满的
            resize(getCapcity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 扩容
     *
     * @param newCapacity 扩大的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            // data中第一个元素的位置可能不是0下标位置
            // 此处使用(front+i)%data.length来将data中元素复制到newData中
            newData[i] = data[(front + i) % data.length];
        }
        this.data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 出队
     *
     * @return 出队元素的值
     */
    @Override
    public E dequeue() {
        // 判断队列中是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue form an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size == getCapcity()/ 4 && getCapcity() / 2 != 0) {
            resize(getCapcity() / 2);
        }
        return ret;

    }

    /**
     * 获取对首元素的值
     *
     * @return 对首元素的值
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[front];
    }

    /**
     * 获取队列中元素的个数
     *
     * @return 队列中元素的个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断队列是否非空
     *
     * @return 为空, 返回true;反之返回false;
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        res.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapcity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i+1)%data.length!=tail) {
                res.append(", ");
            }
        }
        res.append("] tail ");
        return res.toString();
    }
}

测试用例

package com.holelin.queue;

/**
 * ClassName: ArrayQueueTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/21
 */

public class LoopQueueTest {
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i < 21; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }
        for (int i = 0; i < 12; i++) {
            queue.dequeue();
            System.out.println(queue);
        }

    }
}

优先队列

• 基于大顶堆实现

package com.holelin.queue;

import com.holelin.heap.MaxHeap;

/**
 * ClassName: PriorityQueue
 * 基于堆的优先队列
 * ******************入队        出队(拿出最大元素)
 * -- 普通线性结构    O(1)        O(n)
 * -- 顺序线性结构    O(n)        O(1)
 * -- 堆             O(logn)     O(logn)
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/13
 */

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
	private MaxHeap<E> mMaxHeap;

	public PriorityQueue() {
		mMaxHeap = new MaxHeap<>();
	}

	@Override
	public void enqueue(E e) {
		mMaxHeap.add(e);
	}

	@Override
	public E dequeue() {
		return mMaxHeap.extractMax();
	}

	@Override
	public E getFront() {
		return mMaxHeap.findMax();
	}

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

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

ArrayQueue与LoopQueue效率测试用例

package com.holelin.queue;

import java.util.Random;

/**
 * ClassName: QueueEfficiencyTest
 * 测试ArrayQueue和LoopQueue的效率
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/1/30
 */

public class QueueEfficiencyTest {
    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue time is " + time1 + " s");
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue time is " + time2 + " s");
        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue, opCount);
        System.out.println("LinkedListQueue time is " + time3 + " s");

//        ArrayQueue time is 2.475480353 s
//        LoopQueue time is 0.008487905 s
    }

    private static double testQueue(Queue<Integer> q, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        for (int i = 0; i < opCount; i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        for (int i = 0; i < opCount; i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
}