队列的学习(一)用数组和链表实现单向队列

您好,我是码农飞哥,感谢您阅读本文,欢迎一键三连哦
这是Pyhon系列文章的第三篇,本文主要介绍用数组和链表实现单向队列。
干货满满,建议收藏,需要用到时常看看。 小伙伴们如有问题及需要,欢迎踊跃留言哦~ ~ ~。

线性表

前面我们学习了链表的相关知识,今天我们接着来学习另外一种数据结构-----》队列。其实,不管是数组还是链表,都是属于线性表,那么什么是线性表呢?线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。其中n为表长,当n=0时,该线性表是一个空表。若用 L 命名线性表,则其一般表示如下:
L = ( a1 , a2 , a3 , … , a(i) , a( i + 1) , … , a(n) ) 其中,a1 是唯一的 “ 第一个 ” 数据元素,又称为表头元素;a(n) 是唯一的 “ 最后一个 ” 数据元素, 又称为表尾元素。除了第一个元素外,每个元素有且仅有一个直接前驱。除最后一个元素外 ,每个 元素 有且仅有一个直接后继。以上就是线性表的逻辑特性,这种线性表有序的逻辑结构正是线性表 名字的由来。

队列

队列,是一种操作受限,先进先出的的线性表数据结构,其只有入队enqueue和出队dequeue两个操作。我们可以用数组和链表来实现队列。用数组实现的是顺序队列,用链表实现的是链式队列。

数组实现队列的逻辑

队列有两个指针,分别是队头指针head和队尾指针tail。队头的指针指向队列的头部。例如:
我们定义一个大小为6的数组,然后,以及将 a,b,c,d 入队。那么过程变化图如下:
在这里插入图片描述
如上图,我们可以清楚的看出队列入队的话就是tail指针不断向后移动,知道tail等当前数组的长度,就表示队列已满,head指针保持不变。
代码实现如下:

    public boolean enqueue(String item) {
        //如果tail==n 表示队列已经满了
        if (tail == n) {
            return false;
        }
		//将要插入的元素放在tail 位置上
        items[tail] = item;
        ++tail;
        return true;
    }

接下来,我们来看看队列的出队操作。出队的过程图如下所示:
在这里插入图片描述
如上图所示,我们可以清楚的看出队列的出队操作过程就是每出一个元素,head指针就向后移动一次,直到head等于tail 就表示队列为空。tail指针不变。
代码实现如下:

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

每次进行出队操作都相当于删除数组下标为0的数据,要搬移这个队列中的数据,这样出队的操作的时间复杂度就会从原来的O(1)变成O(n)。
实际上,我们在出队时如果不用搬移数据,如果没有空闲空间了,我们只需要在入队是,在集中触发一次数据的搬移操作。借助这个思想,出队函数dequeue() 保持不变,我们稍加改造下入队函数
enqueue()。

public boolean enqueueNew(String item) {
        //tail==n 表示队列末尾没有空间了
        if (tail == n) {
            //tail==n && head==0 表示整个队列都占满了
            if (head == 0) {
                return false;
            }
            //数据搬移
            for (int i=head;i<tail;++i) {
                items[i - head] = items[i];
            }
            //搬移完之后重新更新head和tail
            tail -= head;
            head = 0;
        }
        items[tail] = item;
        ++tail;
        return true;
    }

如上代码,当tail==n是表示队列末尾没有空间,此时,就可以进行数据的迁移,迁移的过程就是将位置为i的元素移动到 i-head上去搬移的操作如下图所示:
在这里插入图片描述

链表实现队列的逻辑

说完了通过数组实现的顺序队列,接下来我们来看看通过链表实现的链式队列。首先我们还是先定义好链表的数据结构

 class Node {
        /**
         * 数据域
         */
        String value;
        /**
         * 下一个结点对象的引用
         */
        Node next;

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

        public Node(String value) {
            this.value = value;
        }

        public Node(Node next) {
            this.next = next;
        }
    }

入队和出队的操作示意图如下所示:
在这里插入图片描述

如上图,队列中有a,b,c,d四个节点,此时,head指针指向a节点,tail 指向d节点。当我们需要向队列中插入e节点时,我们只需要将tail指针指向e节点,即tail->next=e,tail=tail->next;
当a节点从队列中出队时,那么只需要将head指针指向后一个结点。即head=head->next
所以:入队的实现代码是:

public void enqueue(String item) {
        Node newNode = new Node(item);
        //队列没有元素
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = tail.next;
        }
    }

入队操作其实是尾插法,从队列的尾部插入元素。当tail为null时表示队列中没有元素,此时head指针和tail指针都指向新结点。否则,只需要调整tail指针的指向即可。
出队的实现代码是:

public Object dequeue() {
        //队列为空
        if (head == null) {
            return null;
        }
        String value = head.value;
        head = head.next;
        //队列为空
        if (head == null) {
            tail = null;
        }
        return value;
    }

当head为null时表示队列为空。否则,就调整head结点的位置。

总结

本文我们主要介绍了如何用数组和链表实现单向队列。队列是一种操作受限先进先出的的线性表数据结构,其只有入队和出队操作。可以通过数组和链表来实现队列

参考

https://time.geekbang.org/column/article/41330

源码

https://github.com/XWxiaowei/ConcurrencyDemo/tree/master/concurrency-demo/src/main/java/chapter_4/queue

(完)