数据结构 | 队列Queue

数据结构 | 队列Queue

队列 Queue

  • 队列是一种特殊的线性表,只能在头尾两端操作
  • 队尾(rear): 只能从队尾添加元素,即 enQueue,入队
  • 队头(front): 只能从队头移除元素,即 deQueue,出队
  • 队列遵循先进先出的原则,First In First Out,FIFO

队列

实现队列

  • 队列的内部实现可以使用动态数组双向链表实现,但是优先使用双向链表 LinkedList,因为队列主要是操作头尾元素
  • 官方 JDK 源码的 Queue 是一个接口,由 LinkedList 实现了该接口
import java.util.LinkedList;
import java.util.List;

public class Queue<E> {
    private List<E> list;

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

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

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

    // 入队,将元素添加至链表尾部
    public void enQueue(E ele) {
        list.add(ele);
    }

    // 出队,删除并返回链表的头节点元素
    public E deQueue() {
        return list.remove(0);
    }
    
    // 获取队头元素但不出队,获取链表的头节点元素
    public E front() {
        return list.get(0);
    }
}

双端队列 Deque

  • 双端队列是在队头和队尾都可以添加、删除元素的特殊队列

实现双端队列

import java.util.LinkedList;
import java.util.List;

public class Deque<E> {
    private List<E> list;

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

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

    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    // 从队头入队
    public void enQueueFront(E ele) {
        list.add(0,ele);
    }
    
    // 从队尾入队
    public void enQueueRear(E ele) {
        list.add(ele);
    }
    
    // 从队头出队
    public E deQueueFront() {
        return list.remove(0);
    }
    
    // 从队尾出队
    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);
    }
}

参考

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://yzt.cool/archives/2020-04-16-datastructure-queue