数据结构与算法学习之(六)队列

一、如何理解“队列”?

1、队列是一种操作受限的线性表数据结构。
2、队列最大的特点就是先进先出。
3、最基本的操作:入队,放一个数据到队列尾部;出队,从队列头部取一个元素。

二、顺序队列和链式队列

1、用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列。
2、队列需要两个指针:一个是 head 指针,指向队头;一个是 last指针,指向队尾。
3、随着不停地进行入队、出队操作,head 和 last都会持续往后移动。当 last移动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。
​ 如果没有空闲空间了,也可以再集中触发一次数据的搬移操作。
4、基于链表的实现,同样需要两个指针:head 指针和 last指针。分别指向链表的第一个结点和最后一个结点。

三、循环队列

1、循环队列,原本数组是有头有尾的,是一条直线。把首尾相连,扳成了一个环。
2、在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,需要像环一样的循环队列。
3、要想写出没有 bug 的循环队列的实现代码,最关键的是,确定好队空和队满的判定条件。

四、阻塞队列和并发队列

1、阻塞队列

1)阻塞队列就是在队列基础上增加了阻塞操作。
2)在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。
3)基于阻塞队列实现的“生产者 - 消费者模型”,可以有效地协调生产和消费的速度。

2、并发队列

1)线程安全的队列,叫作并发队列。
2)最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。
3)实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

五、数组实现队列以及循环队列

/**
 * 队列--数组实现
 *
 * @Author: chenqi
 * @Date: 2020.7.10 15:33
 */
@Data
public class MyQueueByArray {
    private Object[] value; // 存放的值
    private int head; // 队列的头索引 初始化为0
    private int last; // 队列的尾索引 初始化0
    private int size; // 队列的大小 根据传入的值初始化
    private int count; // 当前队列的大小 初始化0

    public MyQueueByArray() {
    }

    public MyQueueByArray(int size) {
        this.value = new Object[size];
        this.head = 0;
        this.last = 0;
        this.size = size;
        this.count = 0;
    }

    /**
     * 向队列添加元素 非循环队列 会涉及到数据移动
     *
     * @param obj
     */
    private void push(Object obj) {
        if (count >= size) { // 处理越界情况
            throw new RuntimeException("queue is full");
        } else if (last + 1 == value.length) { // 处理 null,null,1,2,3 这时候数组满了,加入新数据4,就要变成 1,2,3,4,null
            int flag = head; // 记录head头的初始索引
            for (int i = 0; i < size; i++) { // 遍历之前的数组
                if (flag <= last) {  // 避免head++之后值超过size
                    value[i] = value[flag];
                    value[flag] = null;
                }
                flag++;
            }
            // 数组变成类似1,2,3,4,null后需要修改队列头尾的索引
            head = 0;
            last = count;
            value[count] = obj;
        } else {
            // 当前位置有值跳过 放到队列尾处
            if (value[count] != null) {
                value[last + 1] = obj;
                last = last + 1;
            } else {
                value[count] = obj;
                last = count;
            }
        }
        count++;
    }


    /**
     * 向队列添加元素 循环队列 不会移动数据
     *
     * @param obj
     */
    private void push2(Object obj) {
        if (count >= size) { // 处理越界情况
            throw new RuntimeException("queue is full");
        } else if (last + 1 == value.length) { // 处理 null,null,1,2,3 这时候数组满了,加入新数据4,就要变成 4,null,1,2,3,
            if (value[0] != null) {
                last++;
                value[last] = obj;
            } else {
                last = 0;
                value[last] = obj;
            }
        } else {
            // 当前位置有值跳过 放到队列尾处
            if (value[count] != null) {
                value[last + 1] = obj;
                last = last + 1;
            } else {
                value[count] = obj;
                last = count;
            }
        }
        count++;
    }

    /**
     * 取元素
     *
     * @return
     */
    private Object pop() {
        if (count == 0) {
            return null;
        }
        Object result = value[head];
        value[head] = null;
        head++;
        count--;
        return result;

    }


    @Override
    public String toString() {
        return "MyQueueByArray{" +
                "value=" + Arrays.toString(value) +
                ", head=" + head +
                ", last=" + last +
                ", size=" + size +
                ", count=" + count +
                '}';
    }

    public static void main(String[] args) {
        MyQueueByArray queue = new MyQueueByArray(5);
        // 正常队列测试
//        queue.push("1");
//        queue.push("2");
//        queue.push("3");
//        queue.push("4");
//        queue.push("5");
//        System.out.println(queue);
//        System.out.println(queue.pop());
//        System.out.println(queue.pop());
//        System.out.println(queue.pop());
//        System.out.println(queue);
//        queue.push("6");
//        System.out.println(queue);
//        System.out.println(queue.pop());
//        System.out.println(queue);
//        queue.push("7");
//        System.out.println(queue);
//        queue.push("8");
//        queue.push("9");
//        System.out.println(queue);

        // 循环链表测试
        queue.push2("1");
        queue.push2("2");
        queue.push2("3");
        queue.push2("4");
        queue.push2("5");
        System.out.println(queue);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue);
        queue.push2("6");
        System.out.println(queue);
        queue.push2("7");
        System.out.println(queue);
        queue.push2("8");
        System.out.println(queue);

        System.out.println(queue.pop());
        System.out.println(queue);
        queue.push2("9");
        System.out.println(queue);
    }

}

六、链表实现队列

/**
 * 队列--链表实现
 *
 * @Author: chenqi
 * @Date: 2020.7.10 15:33
 */
@Data
public class MyQueueByLinked {
    private Node first; // 队列头
    private Node last; // 队列尾
    private int count = 0; // 当前队列的大小

    private MyQueueByLinked() {
    }

    class Node {
        Object value;
        Node next;

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

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }


    /**
     * 向队列添加元素尾插法
     *
     * @param obj
     */
    private void push(Object obj) {
        Node node = new Node(obj);
        if (first == null) {
            this.first = node;
            this.last = node;
        } else {
            last.next = node;
            last = node;
        }
        count++;
    }

    /**
     * 取出队列,从头取
     *
     * @return
     */
    private Object pop() {
        if (first == null) {
            return null;
        } else {
            Node firstNode = first;
            Node nextNode = first.next;
            first = nextNode;
            count--;
            // 处理出最后一个元素的情况
            if (first == null) {
                last = null;
            }
            return firstNode.value;
        }

    }

    @Override
    public String toString() {
        return "MyQueueByLinked{" +
                "first=" + first +
                ", last=" + last +
                ", count=" + count +
                '}';
    }

    public static void main(String[] args) {
        MyQueueByLinked queue = new MyQueueByLinked();
        queue.push("1");
        queue.push("2");
        queue.push("3");
        queue.push("4");
        queue.push("5");
        System.out.println(queue);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue);
        queue.push("6");
        System.out.println(queue);
        System.out.println(queue.pop());
        System.out.println(queue);
        queue.push("7");
        queue.push("8");
        queue.push("9");
        System.out.println(queue);
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue);
        queue.push("10");
        System.out.println(queue);
        System.out.println(queue.pop());
        System.out.println(queue);
    }
}

1

Last modification:July 13th, 2020 at 06:47 pm