Data Structures (四) - 队列Queue实现

RiemannHypothesis

发布于 2022-08-19 16:10:55

34700

代码可运行

文章被收录于专栏：ElixirElixir

运行总次数：0

代码可运行

一、队列Queue的概念

队列是一种特殊的线性表，它只允许在队列的头和尾进行操作。在队列的尾部添加元素即入列enQueue；在队列的头部移除元素即出列deQueue，队列的操作遵循先进先出First In First Out。

队列Queue的方法设计

int size(); //获取队列中元素的数量
boolean isEmpty(); // 判断队列是否为空
void enQueue(T element); // 入列，在尾部添加元素
T deQueue(); // 出列，在头部移除元素
T front(); // 获取 队列的头元素
void clear(); // 清空队列

队列头和尾操作频繁，可以基于双向链表来实现

二、队列的实现

在data-structures项目中新建Module 05-队列，将链表数据结构中的双向链表LinkedList、抽象链表AbstractList、接口List放入com.citi.list包中供队列引用，将utils中的工具类拷贝至com.citi包下。新建queue.Queue类，并将LinkedList作为私有属性

public class Queue<T> {

    // 私有属性LinkedList
    private List<T> list = new LinkedList<>();

    public int size(){

        return 0;
    }
    public boolean isEmpty(){
        return false;
    }
    public void enQueue(T element){

    }
    public T deQueue(){
       return null;
    }
    public T front(){
        return null;
    }
    public void clear(){

    }
}

size() 和 isEmpty() 方法实现

public int size(){
    return list.size();
}
public boolean isEmpty(){
    return list.isEmpty();
}

enQueue() 入队，即在队尾添加元素(链表尾部添加元素)

public void enQueue(T element){
    list.add(element);
}

deQueue() 出列，在队头删除元素(删除链表头元素，索引为0)

public T deQueue(){
   return list.remove(0);
}

**front()**，获取队列头元素

public T front(){
    return list.get(0);
}

clear()

public void clear(){
    list.clear();
}

新建测试类QueueTest

public class QueueTest {

    Queue<Integer> queue = null;

    @Before
    public void init(){
        queue = new Queue<>();
        queue.enQueue(10);
        queue.enQueue(20);
        queue.enQueue(30);
        System.out.println("Init Queue：" + queue);
    }

    @Test
    public void enQueue() {
        queue.enQueue(50);
        System.out.println("enQueue Queue：" + queue);
    }

    @Test
    public void deQueue() {
        queue.deQueue();
        System.out.println("deQueue Queue：" + queue);
    }

    @Test
    public void front() {
        System.out.println("Front Queue: " + queue.front());
    }
}

之前测试前先重写toString方法

@Override
public String toString() {
    return "Queue{" +
            "list=" + list +
            '}';
}

执行测试

使用Stack实现Queue

public class QueueByStack {

    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();

    public void push(int x){
        inStack.push(x);
    }

    public int pop(){
        checkOutStack();
        return outStack.pop();
    }

    public int peek(){
        checkOutStack();
        return outStack.peek();
    }

    public boolean empty(){
        return inStack.isEmpty() &amp;&amp; outStack.isEmpty();
    }

    public void checkOutStack(){
        if (outStack.isEmpty()){
            while (!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
    }
}

三、双端队列

双端队列也是一种队列，它可以在头尾两端进行添加和删除。

双端队列方法设计

int size(); //获取队列中元素的数量
boolean isEmpty(); // 判断队列是否为空
void enQueueRear(T element); // 入列，在尾部添加元素
T deQueueFront(); // 出列，在头部移除元素
void enQueueFront(T element); //从头部入列
T deQueueRear(); //此尾部删除元素
T front(); // 获取 队列的头元素
T rear(); // 获取尾部元素
void clear(); // 清空队列

在queue包下新增双端队列Deque，基于LinkedList实现

public class Deque<T> {

    private List<T> list = new LinkedList<>();

    public int size(){
        return list.size();
    }
    public boolean isEmpty(){
        return list.isEmpty();
    }
    public void clear(){
        list.clear();
    }

}

双端队列从头尾添加删除元素

public void enQueueRear(T element){
    list.add(element);
}

public T deQueueFront(){
    return list.remove(0);
}

public void enQueueFront(T element){
    list.add(0, element);
}

public T deQueueRear(){
    return list.remove(list.size() - 1);
}

获取双端队列头和尾的元素

public T front(){
    return list.get(0);
}

public T rear(){
    return list.get(list.size() - 1);
}

测试类

public class DequeTest {

    Deque<Integer> deque = null;

    @Before
    public void init(){
        deque = new Deque<>();
        deque.enQueueRear(10);
        deque.enQueueRear(20);
        deque.enQueueRear(30);
        System.out.println("Init Queue：" + deque);
    }


    @Test
    public void enQueueRear() {
        deque.enQueueRear(40);
        System.out.println("After enQueueRear: " + deque);
        
    }

    @Test
    public void deQueueFront() {
        deque.enQueueFront(0);
        System.out.println("After deQueueFront: " + deque);
    }

    @Test
    public void enQueueFront() {
        deque.enQueueFront(40);
        System.out.println("After enQueueFront: " + deque);
    }

    @Test
    public void deQueueRear() {
        deque.deQueueRear();
        System.out.println("After deQueueRear: " + deque);
    }

    @Test
    public void front() {
        System.out.println("Front:" + deque.front());
    }

    @Test
    public void rear() {
        System.out.println("Rear:" + deque.rear());
    }
}

给Deque类增加toString方法

@Override
public String toString() {
    return "Deque{" +
            "list=" + list +
            '}';
}

执行测试类中所有的测试方法

四、循环队列

循环队列底层使用数组实现，拥有队头（front）属性，指定数组中的某一个索引为队列的头部，front指的是数组中的索引，为int类型，front不一定是索引0的位置

删除元素演示

循环队列在队头删除元素的时候，需要将front向后移动一个位置，再次删除一个元素，front就在向后移动一个位置，front的范围始终小于数组的容量

添加元素演示

添加元素时往队尾添加元素，front的位置始终不变，当右边的没有空位时就循环到数组左边空位添加元素，新增加的元素的索引使用小于数组的容量

当数组的左边也没有空位时再添加就需要进行动态扩容，循环队列中的循环是指添加元素时循环。

循环队列所拥有的方法与普通队列一致

循环队列实现

public class CircleQueue<T> {

    private int size;
    private T[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    // 构造函数，定义数组的长度
    public CircleQueue(){
        elements = (T[]) new Object[DEFAULT_CAPACITY];
    }
    public int size(){
        return size;
    }

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

获取队列头元素

public T front(){
   return elements[front];
}

在尾部添加元素，添加元素的索引小于数组容量

public void enQueue(T element){
    elements[(front + size) % elements.length] = element;
    size++;
}

移除队列头部元素，front所在的范围小于数组容量

public T deQueue(){
    // 先获取对头的元素
    T frontEle = elements[front];
    // 将对头的元素置为空
    elements[front] = null;
    // 队头要往后移动一次
    // front++;
    front = (front + 1) % elements.length;
    // 长度-1
    size--;
    // 返回队头元素
    return frontEle;
}

清楚队列中的元素，遍历所有的元素，置为null

public void clear(){
    for (int i = 0; i < elements.length; i++) {
        elements[i] = null;
    }
    size = 0;
    front = 0;
}

增加测试类

public class CircleQueueTest {

    CircleQueue<Integer> queue = null;

    @Before
    public void init(){
        queue = new CircleQueue<>();
        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        System.out.println("Init CircleQueue: " + queue);
    }

    @Test
    public void front() {

        System.out.println("CircleQueue Front: " + queue.front());
    }

    @Test
    public void enQueue() {

        queue.enQueue(55);
        System.out.println("After enQueue: " + queue);
    }

    @Test
    public void deQueue() {
        queue.deQueue();
        System.out.println("After deQueue: " + queue);
    }
}

增加toString方法

@Override
public String toString() {
    return "CircleQueue{" +
            "front=" + front +
            ", size=" + size +
            ", elements=" + Arrays.toString(elements) +
            '}';
}

执行所有的测试方法

特殊情况测试

@Test
public void deQueueAndEnQueue() {
    for (int i = 0; i < 3; i++) {
        queue.deQueue();
    }
    System.out.println("After deQueue: " + queue);
    for (int i = 0; i < 4; i++) {
        queue.enQueue(i + 100);
    }
    System.out.println("After enQueue: " + queue);
    for (int i = 0; i < 8; i++) {
        queue.deQueue();
    }
    System.out.println(queue);
}

增加扩容方法

private void expansionCapacity(int newCapacity){
    int oldCapacity = elements.length;
    if (oldCapacity >= size + 1) return;

    // 创建一个新的容量的数组
    // newCapacity = oldCapacity + (oldCapacity >> 1);
    T[] newElements = (T[]) new Object[newCapacity];
    // 拷贝元素
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[(i + front) % elements.length];
    }
    // 指向新的内存空间
    elements = newElements;
    front = 0;
    System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity);
}

修改enQueue方法代码

public void enQueue(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    elements[(front + size) % elements.length] = element;
    size++;
}

扩容测试代码

@Test
public void testExpansion() {
    queue.deQueue();
    System.out.println(queue);
    for (int i = 0; i < 3; i++) {
        queue.enQueue(i);
    }

    System.out.println(queue);
    for (int i = 0; i < 3; i++) {
        queue.deQueue();
    }
    System.out.println("After deQueue: " + queue);
    for (int i = 0; i < 4; i++) {
        queue.enQueue(i + 100);
    }
    System.out.println("After enQueue: " + queue);
    for (int i = 0; i < 8; i++) {
        queue.deQueue();
    }
    System.out.println(queue);
}

执行测试

五、循环双端队列

可以在两端进行添加、删除操作的循环队列

新建一个CircleDeque

public class CircleDeque<T> {

    private int front;
    private int size;
    private T[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    // 构造函数，定义数组的长度
    public CircleDeque(){
        elements = (T[]) new Object[DEFAULT_CAPACITY];
    }
    public int size(){
        return size;
    }
    
    public boolean isEmpty(){
        return size == 0;
    }

    public void clear(){
        for (int i = 0; i < elements.length; i++) {
            elements[index(i)] = null;
        }
        size = 0;
        front = 0;
    }

    public int index(int index){
        return (front + index) % elements.length;
    }

    private void expansionCapacity(int newCapacity){
        int oldCapacity = elements.length;
        if (oldCapacity >= size + 1) return;

        // 创建一个新的容量的数组
        // newCapacity = oldCapacity + (oldCapacity >> 1);
        T[] newElements = (T[]) new Object[newCapacity];
        // 拷贝元素
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(i + front) % elements.length];
        }
        // 指向新的内存空间
        elements = newElements;
        front = 0;
        System.out.println("扩容成功,由" + oldCapacity + "扩展至" + newCapacity);
    }

    @Override
    public String toString() {
        return "CircleQueue{" +
                "front=" + front +
                ", size=" + size +
                ", elements=" + Arrays.toString(elements) +
                '}';
    }
}

获取头部和尾部的元素

public T front(){
    return elements[front];
}

public T rear(){
    return elements[index(front + size - 1)];
}

从尾部入队和从头部移除与双端队列的方法一致

// 从尾部入队
public void enQueueRear(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    elements[(front + size) % elements.length] = element;
    size++;
}

// 从头部出队
public T deQueueFront(){
    // 先获取对头的元素
    T frontEle = elements[front];
    // 将对头的元素置为空
    elements[front] = null;
    // 队头要往后移动一次
    // front++;
    front = (front + 1) % elements.length;
    // 长度-1
    size--;
    // 返回队头元素
    return frontEle;
}

从头部入队时，如果front是0，那么插入的位置是-1，数组中不存在-1的索引，使用-1 + 数组长度就可以变成真正数组中的索引，index方法需要增加判断

public int index(int index){
    index += front;
    if (index < 0){
        return index + elements.length;
    }
    return (front + index) % elements.length;
}

从尾部出队和从头部入队方法实现

// 从尾部出队
public T deQueueRear(){
    // 获取真实索引
    int rearIndex = index(size - 1);
    T rear = elements[rearIndex];
    elements[rearIndex] = null;
    size--;
    return rear;
}

// 从头部入队
public void enQueueFront(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    front = index(front - 1);
    elements[front] = element;
    size ++;
}

新增测试类

public class CircleDequeTest {

    CircleDeque<Integer> deque = null;

    @Before
    public void init(){
        deque = new CircleDeque<>();
        for (int i = 0; i < 8; i++) {
            deque.enQueueRear(i + 10);
        }

        System.out.println("After Init" + deque);
    }

    @Test
    public void front() {
        System.out.println("CircleDeque Front: " + deque.front());
    }

    @Test
    public void rear() {
        System.out.println("CircleDeque Rear: " + deque.rear());
    }

    @Test
    public void enQueueRear() {
        deque.enQueueRear(18);
        System.out.println("After enQueueRear:" + deque);
    }

    @Test
    public void deQueueFront() {
        deque.deQueueFront();
        System.out.println("After deQueueFront: " + deque);
    }

    @Test
    public void deQueueRear() {
        deque.deQueueRear();
        System.out.println("After deQueueRear: " + deque);
    }

    @Test
    public void enQueueFront() {
        deque.enQueueFront(9);
        System.out.println("After enQueueFront: " + deque);
    }
}

执行测试