数据结构系列之队列

发表评论
2,522次阅读

A+

所属分类：数据结构

数据结构系列之队列

如何理解“队列”

队列(queue) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。现实生活中火车排队买票就是这种模式，先进先出(FIFO)。

队列与栈的异同

相同点:都是操作受限的线性表数据结构。

不同点：

栈是先进后出，支持进栈(push)和出栈(pop)，一端进行操作。

队列是先进先出，支持入队(enqueue)和出队(dequeue)，两端进行操作。
数据结构系列之队列

顺序队列和链式队列

顺序队列：用数组实现的叫做顺序队列

在使用顺序队列时，队列中的元素是由数组中的元素构建，所以在入队与出队时可以使用数组的下标对数据元素进行操作，出队与入队的时间复杂度为O(1),还有一种情况就是出队操作是在队头进行的，每出队一次就会释放一些空闲的地址，而队尾达到队列的最大值时就不能再进行入队，这样就会造成空间的浪费，为了避免这种情况，再入队时可以先去做判断，如果入队的元素达到队列的最大值且队头不等零的情况下，就进行数据迁移，入队的时间复杂度有可能会为O(n)。如图：

数据结构系列之队列

Java代码实现数组队列示例:

package queue;

/**
 * @author liumengxi.zh
 * @Description 数组队列
 * @date 2019-07-08 17:38
 * @Copyright 2019 Alibaba.com All right reserved.
 */
public class ArrayQueue {

    /**
     * 数组元素
     */
    private String[] items;

    /**
     * 队列大小
     */
    private int size;

    /**
     * 队头
     */
    private int head = 0;
    /**
     * 对尾
     */
    private int tail = 0;

    /**
     * 初始化队列
     *
     * @param size
     */
    public ArrayQueue(int size) {
        items = new String[size];
        this.size = size;
    }

    /**
     * 入队
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        //表示队列没有空间了
        if (tail == size) {
            //如果tail == size && head == 0 说明队列已满，返回false
            if (head == 0) {return false;}
            //如果未满，需要进行数据搬移
            for (int i = head; i < tail; ++i) {
                //已head为基准，进行数据搬移，如：i为head，则将下标为[i-head]也就是下标为0的元素，设置为i(i为当前head下标的元素)，依次轮推
                items[i - head] = items[i];
            }
            //数据搬移后，更新head与tail的值
            //由于移动数据是从head开始，移动结束后，最后一个元素下标便为head，所以将tail设置为head
            tail = head;
            //而head的下标在移动后，则为队头，所以设置为0
            head = 0;
        }
        //正常入队元素，对尾设置元素
        items[tail] = item;
        //对尾自增
        tail++;
        return true;
    }

    /**
     * 出队 返回出队的元素值
     *
     * @return
     */
    public String dequeue() {
        //出队操作是针对对头元素进行操作
        //如果head==tail标识队列为空，返回null
        if (head == tail) {return null;}
        //返回对头数据
        String data = items[head];
        //对头自增
        head++;
        return data;
    }
}

定义队列使用的基本常量数组元素(队列中的元素)、队列大小(初始化队列)、队头(表示队头的位置)、队尾(表示队尾的位置)
初始化队列大小，初始化过程中将队列中的数组元素设置同等大小
入队操作，这里做了数据迁移的逻辑，第一步，去判断队尾是否已满，已满且队头等于零的情况下表示队列已满。若未队头不等于零，则开始迁移数据，逻辑很简单，把head的位置作为队头，tail位置作为队尾，依次遍历元素，将元素的位置依次设置为从0到当前head的位置，设置完成元素后，更新head与tail的值，head值为0，tail值为head。第二步，就是队尾未满，正常设置队尾元素，将数组下标为tail的设置为item，tail自增。
出队操作，顺序队列的出队操作相对比较简单，判断队头与队尾的位置是否相等，如果相等表示队列为空，返回null，不相等则返回当前head位置的元素即可。最后，head自增

链式队列：用链表实现的叫做链式队列

链式队列的实现方式是链表，前面我们已经讲过链表的组成单元，就是由内存地址中零散的指针组成的。顾名思义，链式队列中的元素是有一个一个节点组成的，节点的next指针指向下个节点的元素，与链表一样，写好链式队列代码要掌握好队列中每个节点指针的指向。

链式队列
数据结构系列之队列
链式队列入队

链式队列出队

Java代码实现链式队列示例:

package queue;

/**
 * @Description 链式
 * @Author liumengxi.zh
 * @date 2019-07-08 18:11
 * @Copyright 2019 Alibaba.com All right reserved.
 */
public class LinkQueue {

    /**
     * 队列长度
     */
    int size;
    /**
     * 头节点，作为固定的节点，没有实际含义。
     */
    Node head = new Node("head", null);

    /**
     * 对尾
     */
    Node tail;

    /**
     * 队列数据大小
     */
    int count;

    public LinkQueue(int size) {
        this.size = size;
    }

    /**
     * 入队
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        //队列已满，无法入队
        if (count == size) {
            return false;
        }
        Node newNode = new Node(item, null);
        //如果tail为null，则标识为空队列
        if (tail == null) {
            tail = newNode;
            head.next = newNode;
        }
        //如果队列中存在元素，则添加元素将对尾的节点指针指向新节点
        tail.next = newNode;
        //将尾节点设置为新节点
        tail = tail.next;
        ++count;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public String dequeue() {
        //如果第一个节点且尾节点为空，则队列为空，返回null
        if (head.next == null && tail == null) {
            return null;
        }
        //队列第一个节点
        Node c = head.next;
        //队列下一个节点
        Node n = c.next;
        //返回当前元素数据
        String data = c.data;
        //设置头节点的下一个节点为n
        head.next = n;
        //设置c节点为空
        c = null;
        //count递减
        count--;
        //如果下一个节点为空，则表示队列为空，没有元素可以再进行出队
        if (n == null) { tail = null; }
        return data;

    }

    /**
     * 链表节点
     */
    private class Node {

        /**
         * 链表元素
         */
        String data;
        /**
         * 后继元素
         */
        Node next;

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

}

循环队列

循环队列，顾名思义就是队头与队尾连起来，形成一个环，循环队列可以规避数据迁移工作，时间复杂度为O(1)。写好循环队列代码，需要确定好队空与队满的判定条件。

数据结构系列之队列
队列空的判断条件依然为 head = tail

入队，tail的指针为 tail = (tail + 1) % size

数据结构系列之队列
出队，head的指针为head = (head + 1) % size

判断队列已满的条件为 (tail + 1) % size = head 实际上tail的位置上实际没有存储元素，所以循环队列判断队满是牺牲了一个存储空间

Java代码实现循环队列示例:

package loopqueue;

/**
 * 循环队列
 */
public class LoopQueue {

    //数组元素
    String[] items;
    //队列大小
    int size;
    //队头
    int head = 0;
    //队尾
    int tail = 0;

    /**
     * 初始化队列
     *
     * @param size
     */
    public LoopQueue(int size) {
        items = new String[size];
        this.size = size;
    }

    /**
     * 入队
     *
     * @param item
     * @return
     */
    public boolean enqueue(String item) {
        //判断队满
        if ((tail + 1) % size == head) {
            return false;
        }
        //设置队列元素
        items[tail] = item;
        //tail指针为(tail + 1) % size
        tail = tail + 1 % size;
        return true;

    }

    /**
     * 出队
     *
     * @return
     */
    public String dequeue() {
        //如果队列为空，则返回null
        if (tail == head) {
            return null;
        }
        //返回出队元素
        String data = items[head];
        //设置队头指针
        head = (head + 1) % size;
        return data;

    }
}