数据结构与算法系列——队列

作者: KEEPINUP | 来源:发表于2019-03-30 21:17 被阅读1次

    什么是队列

    队列也是一种操作受限制的线性表,只允许在表的前端进行删除,也就是出队,而在表的后端进行插入,即入队。

    举一个生活中常见的例子,我们经常会遇到排队办事,先来的排在前边先办理,后来的排在后边,不允许插队。先进先出,这就是典型的队列。

    队列的实现

    队列的概念很容易理解,操作也比较简单,很容易掌握。

    跟栈一样,队列也能用数组和链表来实现,用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列。

    下面我们先来看一下用数组的实现方式。

    public class ArrayQueue {
        private String[] items;
        private int n = 0;
        private int head = 0;
        private int tail = 0;
    
        public ArrayQueue(int n){
            items = new String[n];
            this.n = n;
        }
    
        public boolean Enqueue(String item){
            if(tail == n){
                return false;
            }
            items[tail++] = item;
            return true;
        }
    
        public String Dequeue(){
            if(head == tail){
                return null;
            }
            String item = items[head++];
            return item;
        }
    }
    
    

    队列的数组实现比栈的实现稍微复杂一点点,队列需要两个指针,一个指向队头的 head 指针,一个指向队尾的 tail 指针。同样老办法,我们用画图来更清楚的了解一下这个过程。


    image.png

    如果这个时候我们调用一次出队,那么 head 指针就指向 1 的位置,并把 0 的位置的元素移除出队。如图。

    image.png

    如果这个时候插入一个新的元素,那么 tail 指针就指向 5 的位置,然后把新的元素放到 4 的位置。

    image.png

    我们通过图可以看到,这种实现方法有一个缺点,那就是随着我们不断的入队操作,等到 tail 指向最后一位的时候就没有办法接受新的元素入队了,即使前边有空闲的空间没有元素。所以我们来优化一下我们的代码,当 tail 等于数组的长度 n 的时候,这个时候如果再有新的元素入队,我们就看数组前边是不是有空闲的空间,如果有我们就把队列的元素整体向前移动几个单位。

    public class ArrayQueue {
        private String[] items;
        private int n = 0;
        private int head = 0;
        private int tail = 0;
    
        public ArrayQueue(int n){
            items = new String[n];
            this.n = n;
        }
    
        public boolean Enqueue(String item){
            if(tail == n){
                if(head == 0){
                    return false;
                }
                for (int i = head; i<tail;i++){
                    items[i-head] = items[I];
                }
                tail -= head;
                head = 0;
            }
            items[tail++] = item;
            return true;
        }
    
        public String Dequeue(){
            if(head == tail){
                return null;
            }
            String item = items[head++];
            return item;
        }
    }
    
    

    老办法,画图来展示这一过程。

    image.png

    这样就不会有空间的浪费了,但是还有个问题就是数组不能动态扩展,数组满了之后就不能再入队新的元素了,我们来再来修改一下让数组支持动态扩展。当数组满了的时候我们重新申请一个新的数组,长度为原数组的两倍,然后把原数组的元素移到新数组里,然后再进行入队操作。

    public class ArrayQueue {
        private String[] items;
        private int n = 0;
        private int head = 0;
        private int tail = 0;
        private String[] newItems;
    
        public ArrayQueue(int n){
            items = new String[n];
            this.n = n;
        }
    
        public boolean Enqueue(String item){
            if(tail == n){
                if(head == 0){
                    newItems = new String[2*n];
                    for (int i=0;i<tail;i++){
                        newItems[i] = items[I];
                    }
                    items = newItems;
                }else {
                    for (int i = head; i < tail; i++) {
                        items[i - head] = items[I];
                    }
                    tail -= head;
                    head = 0;
                }
            }
            items[tail++] = item;
            return true;
        }
    
        public String Dequeue(){
            if(head == tail){
                return null;
            }
            String item = items[head++];
            return item;
        }
    }
    

    同样,上图。

    image.png

    还有一种特殊的数组实现是循环队列,当 tail == n 的时候我们不迁移数组的元素,而是去看数组下标为 0 的位置为不为空,如果为空的话我们直接入队新的元素,tail 就等于 1 。我们来看一下代码实现。

    public class CycleArrayQueue {
        private String[] items;
        private int n;
        private int head = 0;
        private int tail = 0;
    
        public CycleArrayQueue(int n){
            items = new String[n];
            this.n = n;
        }
    
        public boolean Enqueue(String item){
            //数组满了
            if((tail+1)%n == head)
                return false;
    
            items[tail] = item;
            tail = (tail+1)%n;
            return true;
        }
    
        public String Dequeue(){
            if(head == tail) return null;
            String str = items[head];
            head = (head+1)%n;
            return str;
        }
    }
    

    下边我们来看一下队列的链表实现,同样我们需要两个指针,head 指向链表第一个结点,tail 指向链表最后一个结点。入队时 tail->next=new_node,tail=tail->next。出队时 head=head->next。

    public class ListNodeQueue {
    
        private ListNode head;
        private ListNode tail;
    
        public void Enqueue(String val){
            ListNode node = new ListNode(val, null);
            if(tail == null){
                head = node;
                tail = node;
            }else {
                tail.next = node;
                tail = tail.next;
            }
        }
    
        public String Dequeue(){
            if(head == null){
                return null;
            }
            String string = head.val;
            head = head.next;
            if(head == null){
                tail = null;
            }
            return string;
        }
    
        class ListNode{
            private String val;
            private ListNode next;
    
            public ListNode(String x, ListNode next) {
                val = x;
                this.next = next;
            }
    
            public String GetValue() {
                return val;
            }
        }
    }
    

    队列的应用

    前边将的都是一些基本的理论知识,那队列在实际的项目中都在什么情况下使用呢?阻塞队列和并发队列应用的比较广泛。

    • 阻塞队列
      阻塞队列实际就是在队列的基础上加上了阻塞操作,当队列为空时,出队操作就会被阻塞,因为队列里没有数据,直到队列里有数据之后才能返回;当队列满的时候,入队操作就会被阻塞,直到队列中有空闲的空间时再执行入队操作。
      我们可以用阻塞队列很容易的实现一个”生产者-消费者“模型,这样我们可以有效的控制生产和消费的速度。当生产者生产的过快时,队列很快就满了,这个时候生产者就阻塞等待,直到消费者消费了,生产者才会被唤醒继续生产。反之消费者消费过快时也同样被阻塞。不仅如此,我们还可以通过调整生产者和消费者的个数,来实现生产和消费的供需平衡。
    • 并发队列
      在多线程应用中,多个线程同时操作队列,就会存在线程安全问题,处理这个问题的队列我们称为并发队列。最简答的方法就是在入队和出队的时候加锁,保证同时只有一个线程执行队列的入队或出队,但是这样以来就会大大降低线程的并发度。
      我们可以用上边提到的数组实现的循环队列来解决这个问题,利用 CAS 的原子操作,可以实现非常高效的并发队列。因此,循环队列比链式队列应用的更为广泛。

    欢迎关注公众号:「努力给自己看」

    公众号200x200

    相关文章

      网友评论

        本文标题:数据结构与算法系列——队列

        本文链接:https://www.haomeiwen.com/subject/wrmsbqtx.html