什么是队列?

与前面提到的数据结构相同,队列中的数据也呈线性排列。虽然与有些相似,但队列中添加和删除数据的操作分别是在两端进行的,就和队列这个名字一样,把它想象成排成一队的人更容易理解。在队列中,处理总是从第一名开始往后进行,而新来的人只能排在队尾。

队列是什么?

如上就是队列的概念图,现在队列中只有数据 Blue。往队列中添加数据时,数据被加在最上面。

然后,队列中添加了数据 Green。往队列中添加数据的操作叫作入队

紧接着,数据 Red 也入队了。

从队列中取出(删除)数据时,是从最下面,也就是最早入队的数据开始的,即 Blue。从队列中删除数据的操作叫作出队

如果再进行一次出队操作,取出的就是 Green 了。

像队列这种最先进去的数据最先被取来,即先进先出的结构,我们称为 First In First Out,简称 FIFO

与栈类似,队列中可以操作数据的位置也有一定的限制。在栈中,数据的添加和删除都在同一端进行,而在队列中则分别是在两端进行的。队列也不能直接访问位于中间的数据,必须通过出队操作将目标数据变成首位后才能访问。

介绍完队列的基本知识后,接下来举一个例子,比如生活中常见的排队买票。

如何理解队列?

队列这个概念非常好理解,你可以把它想象成排队买票,先来的先买,后来的人只能站末尾,不允许插队,先进者先出,这就是典型的队列。

上一篇讲到栈只支持两个基本操作:入栈和出栈。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队,放一个数据到队列尾部;出队,从队列头部取一个元素。

所以,队列跟栈一样,也是一种操作受限的线性表数据结构,队列的概念很好理解,基本操作也很容易掌握。作为一种非常基础的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。

队列的实现

看到这里,相信你已经对队列有了初步的理解,队列主要包含两个操作,入队出队。光理解还不够,我们还要动手去实现队列,接下来让我们来看一看如何用代码实现一个队列。

跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列

首先来看下用数组实现的队列是怎么样的,其实现如下图所示:

那么我先用 Java 语言来实现下顺序队列,代码如下:

/**
 * 基于数组实现的顺序队列
 *
 * @author wupx
 * @date 2020/02/13
 */
public class ArrayQueue {

    private String[] items;
    /**
     * 数组大小
     */
    private int n = 0;
    /**
     * 队头下标
     */
    private int head = 0;
    /**
     * 队尾下标
     */
    private int tail = 0;

    /**
     * 申请一个大小为 capacity 的数组
     *
     * @param capacity
     */
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    /**
     * 入队
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        // 如果 tail == n 表示队列已经满了
        if (tail == n) {
            return false;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public String dequeue() {
        // 如果 head == tail 表示队列为空
        if (head == tail) {
            return null;
        }
        String ret = items[head];
        ++head;
        return ret;
    }
}

另外一种就是链式队列,它的实现如下图所示:

再用链表去实现队列,代码如下:

/**
 * 基于链表实现的链式队列
 *
 * @author wupx
 * @date 2020/02/13
 */
public class LinkedListQueue {
    /**
     * 队头
     */
    private Node head = null;
    /**
     * 队尾
     */
    private Node tail = null;

    /**
     * 入队
     *
     * @param value
     */
    public void enqueue(String value) {
        if (tail == null) {
            Node newNode = new Node(value, null);
            head = newNode;
            tail = newNode;
        } else {
            tail.next = new Node(value, null);
            tail = tail.next;
        }
    }

    /**
     * 出队
     *
     * @return
     */
    public String dequeue() {
        if (head == null) {
            return null;
        }

        String value = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    private static class Node {
        private String data;
        private Node next;

        public Node(String data, Node next) {
            this.data = data;
            this.next = next;
        }

        public String getData() {
            return data;
        }
    }
}

到此,我们就分别实现了基于数组和链表的队列,大家可以自己实现下。

队列还有很多扩展,比如循环队列、阻塞队列、并发队列等,将在以后的文章中进行介绍。

总结

这篇主要讲了一种跟很相似的数据结构-队列,也是一种线性逻辑结构。

队列遵循先进先出(FIFO)的原则,主要的两个操作是入队和出队。队列既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。

参考 《我的第一本算法书》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 该如何选择消息队列?

    在高并发业务场景下,消息队列在流量削峰、解耦上有不可替代的作用。当前使用较多的消息队列有 RabbitMQ、RocketMQ、ActiveMQ、Kafka、Ze...

    武培轩
  • 该如何选择消息队列?

    在高并发业务场景下,消息队列在流量削峰、解耦上有不可替代的作用。当前使用较多的消息队列有 RabbitMQ、RocketMQ、ActiveMQ、Kafka、Ze...

    武培轩
  • 剑指Offer-链表中环的入口结点

    package LinkedList; import java.util.HashSet; /** * 链表中环的入口结点 * 一个链表中包含环,请找出...

    武培轩
  • 0761-7.0.3-如何使用YARN Queue Manager UI配置集群资源

    在CDP DC上,YARN资源的调度程序默认为Capacity Scheduler。我们可以通过YARN Queue Manager UI来界面化配置YARN的...

    Fayson
  • Hadoop FairScheduler

    本文档描述FairScheduler,一个允许YARN应用程序公平共享集群资源的调度插件。

    用户1217611
  • 三分钟基础:什么是队列?

    像线程池、异步队列、消息队列等有限的资源容器中,往往存储大量的任务事件,这些大量的任务事件需要进行有条理的进行任务分发以及各种情况处理,为了能够使得资源容器的正...

    帅地
  • 栈与队列:总结篇!

    相信不仅仅是C++中有这些问题,那么大家使用其他编程语言,也可以考虑一下这四个问题,栈和队列是如何实现的。

    代码随想录
  • AI_第一部分 数据结构与算法(8.队列)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java
  • 算法与数据结构(二) 栈与队列的线性和链式表示(Swift版)

    数据结构中的栈与队列还是经常使用的,栈与队列其实就是线性表的一种应用。因为线性队列分为顺序存储和链式存储,所以栈可以分为链栈和顺序栈,队列也可分为顺序队列和链队...

    lizelu

扫码关注云+社区

领取腾讯云代金券