查看: 185|回复: 0

什么是队列?

[复制链接]
发表于 2020-2-19 17:37:48 | 显示全部楼层 |阅读模式
与前面提到的数据结构相同,队列中的数据也呈线性排列。虽然与有些相似,但队列中添加和删除数据的操作分别是在两头进行的,就和队列这个名字一样,把它想象成排成一队的人更容易明白。在队列中,处理总是从第一名开始今后进行,而新来的人只能排在队尾。
队列是什么?


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

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

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

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

假如再进行一次出队操作,取出的就是 Green 了。
像队列这种开始进去的数据开始被取来,即先进先出的结构,我们称为 First In First Out,简称 FIFO
与栈类似,队列中可以操作数据的位置也有肯定的限制。在栈中,数据的添加和删除都在同一端进行,而在队列中则分别是在两头进行的。队列也不能直接访问位于中间的数据,必须通过出队操作将目标数据变成首位后才能访问。
介绍完队列的基本知识后,接下来举一个例子,好比生存中常见的排队买票。
怎样明白队列?

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

上一篇讲到栈只支持两个基本操作:入栈和出栈。队列跟栈非常相似,支持的操作也很有限,最基本的操作也是两个:入队,放一个数据到队列尾部;出队,从队列头部取一个元素。
以是,队列跟栈一样,也是一种操作受限的线性表数据结构,队列的概念很好明白,基本操作也很容易把握。作为一种非常底子的数据结构,队列的应用也非常广泛,特别是一些具有某些额外特性的队列,好比循环队列、阻塞队列、并发队列。
队列的实现

看到这里,相信你已经对队列有了初步的明白,队列主要包含两个操作,入队出队。光明白还不敷,我们还要动手去实现队列,接下来让我们来看一看怎样用代码实现一个队列。
跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的栈叫作顺序栈,用链表实现的栈叫作链式栈。同样,用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列
首先来看下用数组实现的队列是怎么样的,其实现如下图所示:

那么我先用 Java 语言来实现下顺序队列,代码如下:
  1. /** * 基于数组实现的顺序队列 * * @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;    }}
复制代码
别的一种就是链式队列,它的实现如下图所示:

再用链表去实现队列,代码如下:
  1. /** * 基于链表实现的链式队列 * * @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)的原则,主要的两个操作是入队和出队。队列既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用链表实现的叫链式队列。
参考
《我的第一本算法书》

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?用户注册

x

天涯海角也要找到Ni:什么是队列?

中发现Ni: 什么是队列?
中发现Ni: 什么是队列?
中发现Ni: 什么是队列?
中发现Ni: 什么是队列?
中发现Ni: 什么是队列?
中发现Ni: 什么是队列?
相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表