小码哥《恋上数据结构与算法》笔记（六）：队列、双端队列、循环队列、循环双端队列

￡神魔★判官ぃ 2023-07-24 13:14 22阅读 0赞

> 具体代码在 [Queue][] , 欢迎 `star`

# 目录 #

*  一、队列（Queue）
 *  二、队列接口设计
 *  三、队列的实现
 *  四、leetcode-栈实现队列
 *  五、双端队列（Deque）
 *  六、双端队列的接口设计与实现
 *  七、循环队列（Circle Queue）
 *  八、循环队列的接口设计
 *  九、循环队列的实现
    
     *  1、构造方法
     *  2、入队
        
         *  2.1、数组扩容
         *  2.2、索引计算
     *  3、出队
 *  十、循环双端队列

--------------------

# 一、队列 #

跳转到目录

*  `队列`是一种特殊的`线性表`，只能在`头尾两端`操作。
 *  队尾（`rear`）: 只能从`队尾添加`元素, 一般叫做`enQueue`, 入队。
 *  队头（`front`）: 只能从`队头移除`元素, 一般叫做`deQueue`, 出队。
 *  先进先出的原则，First In First Out，`FIFO`。
 *  队列的内部实现可以使用`动态数组`或`双向链表`实现。
 *  优先使用双向链表，因为队列主要是往`头尾操作`元素。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

# 二、队列的接口设计 #

跳转到目录

public class Queue<E> { 
    
        // 使用双向链表实现队列
        private List<E> list = new DoubleLinkedList<>();
        
        // 元素的数量
        public int size();
        
        // 是否为空
        public boolean isEmpty();
        
        // 入队
        public void enQueue(E element);
        
        // 出队
        public E deQueue();
        
        // 获取队列的头元素
        public E front();
        
        // 清空队列
        public void clear();
    }

# 三、队列的实现 #

跳转到目录

/** * Description: 队列的实现(根据双向链表实现) * * @author zygui * @date 2020/4/11 21:08 */
    public class Queue<E> { 
    
        private List<E> list = new DoubleLinkedList<>();
    
        // 元素的数量
        public int size() { 
            return list.size();
        }
    
        // 队列是否为空
        public boolean isEmpty() { 
            return list.inEmpty();
        }
    
        // 入队, 相当于在链表的尾部添加元素
        public void enQueue(E element) { 
            list.add(element);
        }
    
        // 出队, 相当于移除链表0处的元素
        public E deQueue() { 
            return list.remove(0);
        }
    
        // 获取队列的头元素
        public E front() { 
            return list.get(0);
        }
    
        // 清空队列
        public void clear() { 
            list.clear();
        }
    }

# 四、leetcode-栈实现队列 #

跳转到目录  
[栈实现队列][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

/** * Description: 栈实现队列 https://leetcode-cn.com/problems/implement-queue-using-stacks/ * * 1、 如果outStack为空的话, 将inStack中的所有元素pop并push到outStack中, * 并将outStack的栈顶元素弹出 * 2、如果outStack不为空, 说明此时就不能再往outStack中push元素, 否则顺序将会打乱, * 所以outStack不为空, 就一直弹出元素即可 * * @author zygui * @date 2020/4/11 21:27 */
    public class _232_用栈实现队列 { 
    
        private Stack<Integer> inStack = new Stack<>();
        private Stack<Integer> outStack = new Stack<>();
    
        /** * Initialize your data structure here. */
        public _232_用栈实现队列() { 
    
        }
    
        // 入队
        public void push(int x) { 
            inStack.push(x);
        }
    
        // 出队 (返回出队的元素, 并删除该元素)
        public int pop() { 
            checkOutStack();
            return outStack.pop();
        }
    
        // 获取队头元素 (只是获取,并不删除该元素)
        public int peek() { 
            checkOutStack();
            return outStack.peek(); // 获取队头元素
        }
    
        // 队列是否为空
        public boolean empty() { 
            return outStack.isEmpty() && inStack.isEmpty();
        }
    
        private void checkOutStack() { 
        	// 判断outStack栈中是否为空
            if (outStack.isEmpty()) { 
            	// outStack为空, 此时将inStack中的元素都pop出来, 并push到outStack中
                while (!inStack.isEmpty()) { 
                    outStack.push(inStack.pop());
                }
            }
        }
    }

# 五、双端队列（Deque） #

*  双端队列是能在`头尾`两端`添加`、`删除`的队列。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

# 六、双端队列的接口设计&实现 #

跳转到目录

/** * Description: 双端队列的实现 * * ------------------- * 队尾(rear) 队头(front) * ------------------- * * @author zygui * @date 2020/4/11 21:49 */
    public class Deque<E> { 
        private List<E> list = new DoubleLinkedList<>();
    
        // 元素的数量
        public int size() { 
            return list.size();
        }
    
        // 队列是否为空
        public boolean isEmpty() { 
            return list.inEmpty();
        }
    
        // 从队尾入队
        public void enQueueRear(E element) { 
            list.add(element);
        }
    
        // 从队头出队
        public E deQueueFront() { 
            return list.remove(0);
        }
    
        // 从队头入队
        public void enQueueFront(E element) { 
            list.add(0, element);
        }
    
        // 从队尾出队
        public E deQueueRear() { 
            return list.remove(list.size() - 1);
        }
    
        // 获取队列的头元素
        public E front() { 
            return list.get(0);
        }
    
        // 获取队列的尾元素
        public E rear() { 
            return list.get(list.size() - 1);
        }
    }

测试

/** * Description: 测试类 * * @author zygui * @date 2020/4/11 21:07 */
    public class Main { 
        public static void main(String[] args) { 
        
            Deque<Integer> deque = new Deque<>();
            deque.enQueueFront(11); // 从队头入队
            deque.enQueueFront(22);
            deque.enQueueRear(33); // 从队尾入队
            deque.enQueueRear(44);
    
            /* 44 33 11 22 */
    
            while (!deque.isEmpty()) { 
                // 如果双端队列不为空,则从队头出队
                //System.out.println(deque.deQueueFront()); // 22, 11, 33, 44
                // 如果双端队列不为空,则从队尾出队
                System.out.println(deque.deQueueRear());  // 44, 33, 11, 22
            }
        }
    }

# 七、循环队列（Circle Queue） #

跳转到目录

*  实现循环队列的`思路`: 请先看[《恋上数据结构与算法》笔记（一）：动态数组][Link 2] *ArrayList能否进一步优化的部分。*
 *  队列内部实现也可以用`动态数组`实现，并且将各项接口优化到`O(1)`的时间复杂度， 这个用**数组实现并优化之后的队列**就叫做: `循环队列`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]
 *  **这里定义一个成员变量`front`来记录`首元素`的下标**
 *  每一次`出队`，就将`front`位置的元素**取出并删除**，然后`front`向后`+1`。**(这样就避免了后面的元素都要向前进行移动的操作)**
 *  这是`循环队列`只能从`队头`进行`出队`操作  
    ![在这里插入图片描述][20200413232632122.png]
 *  每一次`入队`，都根据`front`和`当前元素数量(size)`计算出入队元素应该存入的`索引`，然后将元素存入到`数组对应索引`的位置上。
 *  **`上图`: 如果按照我们之前的在尾部添加元素 elements\[size++\] = element, 如上图, size=3, 此时就覆盖掉了3位置的元素; 因为我们想在上图5的位置插入元素, 正好发现front所指向的位置+size正好为5, 所以可以根据这种方式来找到要插入元素的位置**
 *  **`下图`: 如果该动态数组满了, 我们还想往队尾添加元素, 此时就需要计算元素的位置, `(front+size) % elements.length` 即可**
    
     *  > 此时动态数组已经满了, 使用front+size的方式, 只能往索引7的位置添加元素, 这样的话就造成了越界, 可以通过`(front+size)%数组的长度` ===> (2 + 5) % 7 = 0 所以在0的位置插入元素即可!  
        > ![在这里插入图片描述][20200413232452867.png]

# 八、循环队列的接口设计 #

跳转到目录

public class CircleQueue<E> { 
        // 记录第0个元素的索引
        private int front;
        // 当前队列存储的元素个数
        private int size;
        // 用来存储元素的数组
        private E[] elements;
        // 当前队列存储的元素数量
        public int size();
        // 当前队列是否为空
        public boolean isEmpty();
        // 入队
        public void enQueue(E element);
        // 出队
        public E deQueue();
        // 查看索引为0的元素
        public E front();
    }

# 九、循环队列的实现 #

### 1、构造方法 ###

跳转到目录

*  这里设置默认空间来构建循环队列。

private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() { 
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

### 2、入队 ###

跳转到目录

*  入队前需要考虑两个问题：队列是否需要`扩容`和`计算元素入队实际索引`。
 *  **根据`front`和`当前元素数量`计算出入栈元素应该存入的`索引`，然后将元素存入到`数组对应索引`的位置上。**
    
     *  入队的实际索引计算: `(front+size) % 队列的长度`
        
            public void enQueue(E element) { 
                // 计算出入队的实际位置
                elements[(front + size) % elements.length] = element;
                size++;
            }

###### 2.1、数组扩容 ######

跳转到目录

*  扩容相关内容请看 [*动态数组*][Link 2] 中的扩容部分!
 *  扩容后`front`需重置为`0`。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]

/** * 保证要有capacity的容量 * * @param capacity */
    private void ensureCapacity(int capacity) { 
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
    
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) { 
        	// 将之前元素的位置挪动到新数组的位置
            newElements[i] = elements[(i + front) % elements.length];
        }
        elements = newElements;
    
        // 重置front
        front = 0;
    }

###### 2.2、索引计算 ######

跳转到目录

*  `预期入队索引` = `第0个元素索引` \+ `当前队列元素个数`。
 *  如果`预期入队索引`大于等于`数组长度`，`实际入队索引` = `预期入队索引` \- `数组长度`。
 *  如果`预期入队索`引小于`数组长度`，`实际入队索引` = `预期入队索引`。

/** * 将之前的索引转换到现在循环数组的真实索引 * * @param index * @return */
    private int index(int index) { 
        // return (front + index) % elements.length; // 下面两行代码只是为了优化 % 的运算
        index += front;
        return index - (index >= elements.length ? elements.length : 0);
    }

*  入队代码如下

public void enQueue(E element) { 
        ensureCapacity(size + 1);
        // 计算出入队的实际位置
        elements[index(size)] = element;
        size++;
    }

### 3、出队 ###

跳转到目录

*  出队后需要更新`front`。

public E deQueue() { 
        // 获取出队元素
        E frontElement = elements[front];
        // 将索引位置致空
        elements[front] = null;
        // 更新front
        //front++; // 需要计算front的位置,不然会指向最后不存在的位置
        //front = (front + 1) % elements.length;
        front = index(1);
        // size减一
        size--;
        // 返回出队元素
        return frontElement;
    }

# 十、循环双端队列 #

跳转到目录

*  可以进行`两端`添加、删除操作的`循环队列`。

具体代码

/** * Description: 循环双端队列 * * @author zygui * @date 2020/4/14 08:07 */
    public class CircleDeque<E> { 
        // 存储队头(首元素)元素的下标
        private int front;
        private int size;
        private E[] elements;
        private static final int DEFAULT_CAPACITY = 10;
    
        public CircleDeque() { 
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        }
    
        // 元素的数量
        public int size() { 
            return size;
        }
    
        // 队列是否为空
        public boolean isEmpty() { 
            return size == 0;
        }
    
        // 从队尾入队
        public void enQueueRear(E element) { 
            ensureCapacity(size + 1);
            
            /* if(front - 1 < 0){ front += elements.length; } front = front - 1; elements[front-1] = element; */
    
            elements[index(size)] = element;
            size++;
        }
    
        // 从队头出队
        public E deQueueFront() { 
            E frontElement = elements[front];
            elements[front] = null;
            front = index(1);
            size--;
            return frontElement;
        }
    
        // 从队头入队
        public void enQueueFront(E element) { 
            ensureCapacity(size + 1);
    
            front = index(-1); // 存放真实索引
            elements[front] = element;
            size++;
        }
    
        // 从队尾出队
        public E deQueueRear() { 
            int rearIndex = index(size - 1);
            E rear = elements[rearIndex];
            elements[rearIndex] = null;
            size--;
            return rear;
        }
    
    
        // 获取队列的头元素
        public E front() { 
            return elements[front];
        }
    
        // 获取队列的尾元素
        public E rear() { 
            // 队头下标+size-1就是队尾下标
            // return elements[(front + size - 1) % elements.length];
            return elements[index(size - 1)];
        }
    
        /** * 保证要有capacity的容量 * * @param capacity */
        private void ensureCapacity(int capacity) { 
            int oldCapacity = elements.length;
            if (oldCapacity >= capacity) return;
    
            // 新容量为旧容量的1.5倍
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            E[] newElements = (E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) { 
                newElements[i] = elements[index(i)];
            }
            elements = newElements;
    
            // 重置front
            front = 0;
        }
    
        /** * 将之前的索引转换到现在循环数组的真实索引 * * @param index * @return */
        private int index(int index) { 
            index += front;
            if (index < 0)
                return index + elements.length;
            //return index % elements.length;
            return index - (index >= elements.length ? elements.length : 0);
        }
    
        @Override
        public String toString() { 
            StringBuilder string = new StringBuilder();
            string.append("capacity=").append(elements.length)
                    .append(" size=").append(size)
                    .append(" front=").append(front)
                    .append(", [");
            for (int i = 0; i < elements.length; i++) { 
                if (i != 0) { 
                    string.append(", ");
                }
                string.append(elements[i]);
            }
            string.append("]");
            return string.toString();
        }
    }

测试

/** * Description: 测试类 * * @author zygui * @date 2020/4/11 21:07 */
    public class Main { 
        public static void main(String[] args) { 
    
            CircleDeque<Integer> queue = new CircleDeque<>();
            // 头 5 4 3 2 1 100 101 102 103 104 105 106 8 7 6 尾
    
            // 头 8 7 6 5 4 3 2 1 100 101 102 103 104 105 106 107 108 109 null null 10 9 尾
            for (int i = 0; i < 10; i++) { 
                queue.enQueueFront(i + 1);
                queue.enQueueRear(i + 100);
            }
            System.out.println(queue);
    
            // 头 null 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null null 尾
            for (int i = 0; i < 3; i++) { 
                queue.deQueueFront();
                queue.deQueueRear();
            }
            System.out.println(queue);
    
            // 头 11 7 6 5 4 3 2 1 100 101 102 103 104 105 106 null null null null null null 12 尾
            queue.enQueueFront(11);
            queue.enQueueFront(12);
            System.out.println(queue);
            while (!queue.isEmpty()) { 
                System.out.print(queue.deQueueFront() + " ");
            }
    
        }
    }

[Queue]: https://github.com/coderZYGui/queue-structure
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20230528/7c1ce4ff6d494ff781d9e93e19091318.png
[Link 1]: https://leetcode-cn.com/problems/implement-queue-using-stacks/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20230528/972828be280b47abbe6c8a8e881234b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20230528/f29acf40aaea43ed91d733f372e5e5f6.png
[Link 2]: https://blog.csdn.net/m0_37989980/article/details/105156706
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 3]: /images/20230528/cacbdc9beda2412abafb6c1a62bc9a9e.png
[20200413232632122.png]: /images/20230528/51ff8a87aeb44af9adf64574d1c288b4.png
[20200413232452867.png]: /images/20230528/00b6e385cfb54d148f1418555ffd877a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 4]: /images/20230528/64950f980c204732b9ea743d4f98b3bb.png