重庆建设工程招标网站,如何攻击网站,精选网站建立 推广 优化,因网站开发需要本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。两种实现方式的基本原理和特点#xff0c;以及详细的Java代码实现和分析。
引言
双端队列(Deque, Double-ended queue)是一种具有队列和栈的性质的数据结构。它允许在两端插入和删除元素#xff0c…本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。两种实现方式的基本原理和特点以及详细的Java代码实现和分析。
引言
双端队列(Deque, Double-ended queue)是一种具有队列和栈的性质的数据结构。它允许在两端插入和删除元素具有较高的灵活性。双端队列在数据结构和算法领域有广泛的应用如在解决滑动窗口最值问题、实现特定需求的优先队列等场景。本文主要介绍了两种实现双端队列的数据结构 —— 基于环形链表和循环数组。以下分别对这两种实现方式进行分析和讲解。
1.基于环形链表的双端队列
环形链表是一种链表的扩展 其中链表的首尾相连形成一个环。在实现双端队列时我们可以使用环形链表来存储元素这样就可以方便地在表头表尾进行插入和删除操作。
以下是基于环形链表实现双端队列的Java代码
/*** 基于环形链表的双端队列* param E 元素类型*/
public class LinkedListDequeE implements DequeE, IterableE {Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}size;NodeE a sentinel;NodeE b sentinel.next;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}size;NodeE a sentinel.prev;NodeE b sentinel;NodeE offered new Node(a, e, b);a.next offered;b.prev offered;return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}NodeE a sentinel;NodeE polled sentinel.next;NodeE b polled.next;a.next b;b.prev a;size--;return polled.value;}Overridepublic E pollLast() {if (isEmpty()) {return null;}NodeE polled sentinel.prev;NodeE a polled.prev;NodeE b sentinel;a.next b;b.prev a;size--;return polled.value;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return sentinel.next.value;}Overridepublic E peekLast() {if (isEmpty()) {return null;}return sentinel.prev.value;}Overridepublic boolean isEmpty() {return size 0;}Overridepublic boolean isFull() {return size capacity;}Overridepublic IteratorE iterator() {return new IteratorE() {NodeE p sentinel.next;Overridepublic boolean hasNext() {return p ! sentinel;}Overridepublic E next() {E value p.value;p p.next;return value;}};}static class NodeE {NodeE prev;E value;NodeE next;public Node(NodeE prev, E value, NodeE next) {this.prev prev;this.value value;this.next next;}}NodeE sentinel new Node(null, null, null);int capacity;int size;public LinkedListDeque(int capacity) {sentinel.next sentinel;sentinel.prev sentinel;this.capacity capacity;}
}优点基于环形链表实现的双端队列具有较好的灵活性可以实现任意容量大小的双端队列。此外存储空间会根据实际需求进行动态调整避免了空间的浪费。
缺点由于链表结构的特性相较于数组实现的双端队列环形链表实现的双端队列空间开销较大。同时每次访问元素时都需要遍历链表导致时间复杂度较高。
2.基于循环数组的双端队列
循环数组是一种线性数据结构它的逻辑结构和顺序表相似但在实际存储时将首尾相接形成一个环状结构。在实现双端队列时可以使用循环数组来存储元素。当队列的一端进行插入或删除操作时对应的数组下标只需加一或减一即可。
以下是基于循环数组实现双端队列的Java代码
/*** 基于循环数组实现, 特点* ul* litail 停下来的位置不存储, 会浪费一个位置/li* /ul* param E*/
public class ArrayDeque1E implements DequeE, IterableE {/*ht0 1 2 3b a*/Overridepublic boolean offerFirst(E e) {if (isFull()) {return false;}head dec(head, array.length);array[head] e;return true;}Overridepublic boolean offerLast(E e) {if (isFull()) {return false;}array[tail] e;tail inc(tail, array.length);return true;}Overridepublic E pollFirst() {if (isEmpty()) {return null;}E e array[head];array[head] null;head inc(head, array.length);return e;}Overridepublic E pollLast() {if (isEmpty()) {return null;}tail dec(tail, array.length);E e array[tail];array[tail] null;return e;}Overridepublic E peekFirst() {if (isEmpty()) {return null;}return array[head];}Overridepublic E peekLast() {if (isEmpty()) {return null;}return array[dec(tail, array.length)];}Overridepublic boolean isEmpty() {return head tail;}Overridepublic boolean isFull() {if (tail head) {return tail - head array.length - 1;} else if (tail head) {return head - tail 1;} else {return false;}}Overridepublic IteratorE iterator() {return new IteratorE() {int p head;Overridepublic boolean hasNext() {return p ! tail;}Overridepublic E next() {E e array[p];p inc(p, array.length);return e;}};}E[] array;int head;int tail;SuppressWarnings(unchecked)public ArrayDeque1(int capacity) {array (E[]) new Object[capacity 1];}static int inc(int i, int length) {if (i 1 length) {return 0;}return i 1;}static int dec(int i, int length) {if (i - 1 0) {return length - 1;}return i - 1;}
}该实现中为了区分队列为空和队列已满的情况我们采用了一种方法:浪费一个数组元素。这样当 tail head时队列为空当 (tail 1) % array.length head时队列已满。
优点: 基于循环数组实现的双端队列具有较好的时间复杂度访问元素的时间复杂度为O(1)。此外相比链表实现的双端队列循环数组实现的双端队列空间开销较小占用内存较少。
缺点: 循环数组实现的双端队列存在一定的空间浪费。并且数组的容量固定在初始化时就要确定。如果访问量较大可能导致数组不够用而需要进行扩容操作这将导致时间复杂度的降低。
结论
本文主要介绍了两种实现双端队列的数据结构基于环形链表的双端队列和基于循环数组的双端队列。根据不同的应用场景和需求可以选择合适的数据结构进行实现。环形链表的双端队列适合容量不固定、对时间复杂度要求不高的场景循环数组的双端队列适合对空间和时间复杂度有较高要求的场景。
