【算法之旅】基础数据结构之队列

女爷i 2023-09-25 20:41 13阅读 0赞

![请添加图片描述][ea689b325bd64e3d99e44e943c5dbdb3.png]  
一名软件工程专业学生的算法之旅，记录自己从零开始学习数据结构与算法，从小白的视角学习数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树等，学习算法：枚举、排序、搜索、计数、分治策略、动态规划、贪心、回溯、图论、数论、字符串算法等，欢迎加入我，一起来学吧！

#### 基础数据结构之队列 ####

*   *   *  一、概述
         *  二、链表实现
         *  三、环形数组实现
     *

#### 一、概述 ####

计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为**尾**，移除的一端称为**头**，就如同生活中的排队买商品

> In computer science, a **queue** is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence

先定义一个简化的队列接口

public interface Queue<E> {
        
    
        /**
         * 向队列尾插入值
         * @param value 待插入值
         * @return 插入成功返回 true, 插入失败返回 false
         */
        boolean offer(E value);
    
        /**
         * 从对列头获取值, 并移除
         * @return 如果队列非空返回对头值, 否则返回 null
         */
        E poll();
    
        /**
         * 从对列头获取值, 不移除
         * @return 如果队列非空返回对头值, 否则返回 null
         */
        E peek();
    
        /**
         * 检查队列是否为空
         * @return 空返回 true, 否则返回 false
         */
        boolean isEmpty();
    
        /**
         * 检查队列是否已满
         * @return 满返回 true, 否则返回 false
         */
        boolean isFull();
    }

#### 二、链表实现 ####

下面以**单向环形带哨兵**链表方式来实现队列

![在这里插入图片描述][bcf5f3d4a413475f9c3b0a5901426556.png]  
![在这里插入图片描述][ccddffa7b26f49489c8ab1307e5ad3fe.png]  
![在这里插入图片描述][7ae9bea0e36d48b68f42d18ab669e89e.png]

代码

public class LinkedListQueue<E>
            implements Queue<E>, Iterable<E> {
        
    
        private static class Node<E> {
        
            E value;
            Node<E> next;
    
            public Node(E value, Node<E> next) {
        
                this.value = value;
                this.next = next;
            }
        }
    
        private Node<E> head = new Node<>(null, null);
        private Node<E> tail = head;
        private int size = 0;
        private int capacity = Integer.MAX_VALUE;
    
        {
        
            tail.next = head;
        }
    
        public LinkedListQueue() {
        
        }
    
        public LinkedListQueue(int capacity) {
        
            this.capacity = capacity;
        }
    
        @Override
        public boolean offer(E value) {
        
            if (isFull()) {
        
                return false;
            }
            Node<E> added = new Node<>(value, head);
            tail.next = added;
            tail = added;
            size++;
            return true;
        }
    
        @Override
        public E poll() {
        
            if (isEmpty()) {
        
                return null;
            }
            Node<E> first = head.next;
            head.next = first.next;
            if (first == tail) {
        
                tail = head;
            }
            size--;
            return first.value;
        }
    
        @Override
        public E peek() {
        
            if (isEmpty()) {
        
                return null;
            }
            return head.next.value;
        }
    
        @Override
        public boolean isEmpty() {
        
            return head == tail;
        }
    
        @Override
        public boolean isFull() {
        
            return size == capacity;
        }
    
        @Override
        public Iterator<E> iterator() {
        
            return new Iterator<E>() {
        
                Node<E> p = head.next;
                @Override
                public boolean hasNext() {
        
                    return p != head;
                }
                @Override
                public E next() {
        
                    E value = p.value;
                    p = p.next;
                    return value;
                }
            };
        }
    }

#### 三、环形数组实现 ####

**好处**

1.  对比普通数组，起点和终点更为自由，不用考虑数据移动
2.  “环”意味着不会存在【越界】问题
3.  数组性能更佳
4.  环形数组比较适合实现有界队列、RingBuffer 等

![在这里插入图片描述][35ff018e305a43c9adcb1aeaf4dfa0c6.png]

**下标计算**

例如，数组长度是 5，当前位置是 3 ，向前走 2 步，此时下标为  ( 3 + 2 ) % 5 = 0 (3 + 2)\\%5 = 0 (3\+2)%5=0

![在这里插入图片描述][222a62d18b1f4e798d8985022926339d.png]

( c u r + s t e p ) % l e n g t h (cur + step) \\% length (cur\+step)%length

*  cur 当前指针位置
 *  step 前进步数
 *  length 数组长度

> 注意：
> 
>  *  如果 step = 1，也就是一次走一步，可以在 >= length 时重置为 0 即可

**判断空**  
![在这里插入图片描述][ea556cf1dc864d06ba3e9507e6a9891f.png]

**判断满**

![在这里插入图片描述][74cd5d8174ab4435bdcbb483ddc456ef.png]

满之后的策略可以根据业务需求决定

*  例如我们要实现的环形队列，满之后就拒绝入队

代码

public class ArrayQueue<E> implements Queue<E>, Iterable<E>{
        
    
        private int head = 0;
        private int tail = 0;
        private final E[] array;
        private final int length;
    
        @SuppressWarnings("all")
        public ArrayQueue(int capacity) {
        
            length = capacity + 1;
            array = (E[]) new Object[length];
        }
    
        @Override
        public boolean offer(E value) {
        
            if (isFull()) {
        
                return false;
            }
            array[tail] = value;
            tail = (tail + 1) % length;
            return true;
        }
    
        @Override
        public E poll() {
        
            if (isEmpty()) {
        
                return null;
            }
            E value = array[head];
            head = (head + 1) % length;
            return value;
        }
    
        @Override
        public E peek() {
        
            if (isEmpty()) {
        
                return null;
            }
            return array[head];
        }
    
        @Override
        public boolean isEmpty() {
        
            return tail == head;
        }
    
        @Override
        public boolean isFull() {
        
            return (tail + 1) % length == head;
        }
    
        @Override
        public Iterator<E> iterator() {
        
            return new Iterator<E>() {
        
                int p = head;
                @Override
                public boolean hasNext() {
        
                    return p != tail;
                }
    
                @Override
                public E next() {
        
                    E value = array[p];
                    p = (p + 1) % array.length;
                    return value;
                }
            };
        }
    }

**判断空、满方法2**

引入 size

public class ArrayQueue2<E> implements Queue<E>, Iterable<E> {
        
    
        private int head = 0;
        private int tail = 0;
        private final E[] array;
        private final int capacity;
        private int size = 0;
    
        @SuppressWarnings("all")
        public ArrayQueue2(int capacity) {
        
            this.capacity = capacity;
            array = (E[]) new Object[capacity];
        }
    
        @Override
        public boolean offer(E value) {
        
            if (isFull()) {
        
                return false;
            }
            array[tail] = value;
            tail = (tail + 1) % capacity;
            size++;
            return true;
        }
    
        @Override
        public E poll() {
        
            if (isEmpty()) {
        
                return null;
            }
            E value = array[head];
            head = (head + 1) % capacity;
            size--;
            return value;
        }
    
        @Override
        public E peek() {
        
            if (isEmpty()) {
        
                return null;
            }
            return array[head];
        }
    
        @Override
        public boolean isEmpty() {
        
            return size == 0;
        }
    
        @Override
        public boolean isFull() {
        
            return size == capacity;
        }
    
        @Override
        public Iterator<E> iterator() {
        
            return new Iterator<E>() {
        
                int p = head;
    
                @Override
                public boolean hasNext() {
        
                    return p != tail;
                }
    
                @Override
                public E next() {
        
                    E value = array[p];
                    p = (p + 1) % capacity;
                    return value;
                }
            };
        }
    }

**判断空、满方法3**

*  head 和 tail 不断递增，用到索引时，再用它们进行计算，两个问题
    
     *  如何保证 head 和 tail 自增超过正整数最大值的正确性
     *  如何让取模运算性能更高
 *  答案：让 capacity 为 2 的幂

public class ArrayQueue3<E> implements Queue<E>, Iterable<E> {
        
    
        private int head = 0;
        private int tail = 0;
        private final E[] array;
        private final int capacity;
    
        @SuppressWarnings("all")
        public ArrayQueue3(int capacity) {
        
            if ((capacity & capacity - 1) != 0) {
        
                throw new IllegalArgumentException("capacity 必须为 2 的幂");
            }
            this.capacity = capacity;
            array = (E[]) new Object[this.capacity];
        }
    
        @Override
        public boolean offer(E value) {
        
            if (isFull()) {
        
                return false;
            }
            array[tail & capacity - 1] = value;
            tail++;
            return true;
        }
    
        @Override
        public E poll() {
        
            if (isEmpty()) {
        
                return null;
            }
            E value = array[head & capacity - 1];
            head++;
            return value;
        }
    
        @Override
        public E peek() {
        
            if (isEmpty()) {
        
                return null;
            }
            return array[head & capacity - 1];
        }
    
        @Override
        public boolean isEmpty() {
        
            return tail - head == 0;
        }
    
        @Override
        public boolean isFull() {
        
            return tail - head == capacity;
        }
    
        @Override
        public Iterator<E> iterator() {
        
            return new Iterator<E>() {
        
                int p = head;
    
                @Override
                public boolean hasNext() {
        
                    return p != tail;
                }
    
                @Override
                public E next() {
        
                    E value = array[p & capacity - 1];
                    p++;
                    return value;
                }
            };
        }
    }

###  ###

@Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
    
            @Override
            public boolean hasNext() {
                return p != tail;
            }
    
            @Override
            public E next() {
                E value = array[p & capacity - 1];
                p++;
                return value;
            }
        };
    }
    }

[ea689b325bd64e3d99e44e943c5dbdb3.png]: https://img-blog.csdnimg.cn/ea689b325bd64e3d99e44e943c5dbdb3.png
[bcf5f3d4a413475f9c3b0a5901426556.png]: https://img-blog.csdnimg.cn/bcf5f3d4a413475f9c3b0a5901426556.png
[ccddffa7b26f49489c8ab1307e5ad3fe.png]: https://img-blog.csdnimg.cn/ccddffa7b26f49489c8ab1307e5ad3fe.png
[7ae9bea0e36d48b68f42d18ab669e89e.png]: https://img-blog.csdnimg.cn/7ae9bea0e36d48b68f42d18ab669e89e.png
[35ff018e305a43c9adcb1aeaf4dfa0c6.png]: https://img-blog.csdnimg.cn/35ff018e305a43c9adcb1aeaf4dfa0c6.png
[222a62d18b1f4e798d8985022926339d.png]: https://img-blog.csdnimg.cn/222a62d18b1f4e798d8985022926339d.png
[ea556cf1dc864d06ba3e9507e6a9891f.png]: https://img-blog.csdnimg.cn/ea556cf1dc864d06ba3e9507e6a9891f.png
[74cd5d8174ab4435bdcbb483ddc456ef.png]: https://img-blog.csdnimg.cn/74cd5d8174ab4435bdcbb483ddc456ef.png