搜 索

Java数据结构基础丨队列

  • 375阅读
  • 2021年02月19日
  • 0评论
首页 / 默认分类 / 正文

队列的基本知识

  • 队列,Queue,是一种特殊的线性表,它也类似栈,操作也有限制:只允许在表的前端进行删除操作,而在表的后端进行插入操作。
  • 与栈的入栈出栈类似,在队列中插入一个队列元素成为入队,从队列中删除一个队列元素成为出队。但与栈的特点相反,队列的元素只能先入先出(First In First Out,简称FIFO)。
  • 队列的出口端叫作队头(front),队列的入口端叫作队尾(rear)。

生活中,可以体现出队列特点的情景也不少:商城排队购物结算;客运站排队刷脸检票;红绿灯等候起步的车流......先进先出,公平有序。

队列的基本操作

  1. 入队(enque),也可以称作 insert、add,就是把新元素放入队列中,只允许在队尾的位置放入元素,新元素的下一个位置将成为新的队尾。
  2. 出队(deque),也可以称作 remove、delete,就是把元素移出队列,只允许在队头一侧移出元素,出队元素的后一个元素将会成为新的队头。
  3. peek(),返回队头数据项的值,并不从队中删除这个数据项。
  4. size(),返回队列内元素的数量。
  5. isEmpty(),测试队列是否为空,返回布尔值。
  6. isFull(),测试队列是否为满,返回布尔值。

队列的实现

同样地,队列既可以用数组来实现,也可以用链表来实现。

循环队列

注意,当使用数组来实现队列时,执行一次出队操作:数据项被移除,同时队头指针增加一。那么问题出现了:如果不断执行出队操作,队头的左侧空间是否失去了作用?如果此时要入队一个数据,但是队尾已经没有空间了,队尾指针不能再向后移动了,那么是不是需要将所有元素往数组开头移动,给队尾腾出空间呢?这很符合生活中排队的情境——前面的人出队了,后面一位补上。这就是顺序队列


出队操作
空闲的空间

如果队头的左侧空闲的空间失去了作用,那队列的容量岂不是越来越小了?也不要忽略在数组中将所有元素往数组开始移动的开销,所以顺序队列的性能很低。在数组不扩容的前提下,为了避免队列不满却不能插入新数据项的问题,让队头队尾指针绕回到数组开头的位置,同时维持了队列容量的恒定,这就是循环队列。在物理存储上,队尾的位置也可以在队头之前,当再有元素入队时,队尾指针继续后移即可。
循环队列

静态数组实现
单链表实现

class ArrayQueue {
    // 数组的大小
    private int maxSize;
    // 存储数据的数组
    private int[] queArray;
    // 队头
    private int front;
    // 队尾
    private int rear;
    // 队列现有元素数量
    private int nItems;

    public ArrayQueue(int s) {
        maxSize = s + 1;
        queArray = new int[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return (nItems == 0);
    }

    // 判断是否为满
    public boolean isFull() {
        return (nItems == maxSize);
    }

    // 现有元素个数
    public int size(){
        return nItems;
    }

    // 查看队头数据项的值
    public int peek(){
        return queArray[front];
    }

    // 入队
    public void enque(int value) throws Exception{
        if (isFull()){
            throw new Exception("队列已满!");
        }
        if (rear == maxSize-1){
            rear = -1;
        }
        queArray[++rear] = value;
        nItems++;
    }

    // 出队
    public int deque()throws Exception{
        if (isEmpty()){
            throw new Exception("队列是空的!");
        }
        if (front == maxSize){
            front = 0;
        }
        int temp = queArray[front++];
        nItems--;
        return temp;
    }

    // 输出队列
    public void show(){
        for (int i = front; i != rear+1; i = (i+1)%queArray.length){
            System.out.print(queArray[i] + " ");
        }
    }

}

class LinkedQueue<T> {
    // 链表结点
    class Node<T> {
        //数据域
        private T data;
        // 后续指针
        private Node<T> next;
        // 无参构造
        public Node() {
            this.data = null;
            this.next = null;
        }
        // 有参构造
        public Node(T data) {
            this.data = data;
            this.next = null;
        }

        public void setNext(Node<T> t) {
            this.next = t;
        }

        public T getData() {
            return this.data;
        }

        public Node<T> getNext() {
            return this.next;
        }
    }
    // 队头
    private Node<T> front;
    // 队尾
    private Node<T> rear;
    // 队列当前长度
    private int size;

    public LinkedQueue() {
        this.front = null;
        this.rear = null;
    }

    // 判断是否为空
    public boolean isEmpty() {
        return (size == 0);
    }

    // 获取队列的长度
    public int size(){
        return size;
    }

    //查看队头的数据
    public T peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空!");
        } else {
            return front.getData();
        }
    }

    //入队
    public boolean enQue(T t) {
        Node<T> newNode = new Node<>(t);
        //如果头等于空
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            //插入尾部
            rear.next = newNode;
            rear = newNode;
        }
        size++;
        return true;
    }

    //出队
    public Node<T> deQue() throws Exception {
        if(isEmpty()){
            throw new Exception("空队列异常!");
        } else {
            //得到队列头元素
            Node<T> value = front;
            front = front.next;
            value.next = null;
            size--;
            return value;
        }
    }
}

队列的应用以及效率

在多线程中,争夺公平锁的等待队列,就是按照访问顺序来决定线程在队列中的次序的。还可以使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。
例如,不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须 100%处理成功、不知道谁依赖“我”的处理结果、不关心其他系统如何处理后续业务、不需要强一致性,只需保证最终一致性即可、想要保证数据处理的有序性等等,这些问题都考虑使用队列来解决。
循环队列插入数据项和移除数据项的时间复杂度都是O(1)

参考

Segmentfault
掘金
数据结构C语言版教程
打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar