用数组和链表实现单向队列

码农飞哥

发布于 2021-08-18 10:37:32

5000

发布于 2021-08-18 10:37:32

文章被收录于专栏：好好学习

线性表

前面我们学习了链表的相关知识，今天我们接着来学习另外一种数据结构-----》队列。其实，不管是数组还是链表，都是属于线性表，那么什么是线性表呢？线性表是具有相同数据类型的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结点的位置。