数据结构与算法——13.队列的拓展

这篇文章主要讲一下双端队列，优先队列，阻塞队列等队列的拓展内容。

1.队列拓展概述

2.双端队列的链表实现

3.双端队列的数组实现

4.优先队列无序数组实现

5.阻塞队列

6.总结

1.队列拓展概述

首先来看一张图，来大致了解一下他们的区别。

双端队列：即两端都可以删除和添加的队列，并且满足队列FIFO的特点。

2.双端队列的链表实现

下面来看一下双端队列的链表实现：

代码如下：

/*** 基于双向环形链表实现双端队列* */
public class L15_LinkedListDeque<E> implements L15_TwoQueue<E> {/**节点类的设计*/static class Node<E>{Node<E> prev;E value;Node<E> next;/**节点的构造函数*/public Node(Node<E> prev,E value,Node<E> next){this.prev = prev;this.value = value;this.next = next;}}int capacity;//容量int size;//有效元素个数Node<E> sentinel = new Node<>(null,null,null);//创建一个节点(哨兵)/**双端队列的构造函数*/public L15_LinkedListDeque(int capacity) {//构建成环this.capacity = capacity;sentinel.next = sentinel;sentinel.prev = sentinel;}/**头部插入* 核心逻辑就是找插入节点的上一个和下一个节点* */@Overridepublic boolean offerFirst(E e) {if (isFull())return false;Node<E> a = sentinel;Node<E> b = sentinel.next;Node<E> added = new Node<>(a,e,b);a.next = added;b.prev = added;size++;return true;}@Overridepublic boolean offerLast(E e) {if (isFull())return false;Node<E> a = sentinel.prev;Node<E> b = sentinel;Node<E> added = new Node<>(a,e,b);a.next = added;b.prev = added;size++;return true;}@Overridepublic E pollFirst() {if (isEmpty())return null;Node<E> a = sentinel;Node<E> removed = sentinel.next;Node<E> b = removed.next;a.next = b;b.prev = a;size--;return removed.value;}@Overridepublic E pollLast() {if (isEmpty())return null;Node<E> removed = sentinel.prev;Node<E> a = removed.prev ;Node<E> b = sentinel;a.next = b;b.prev = a;size--;return removed.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 == capacity;}@Overridepublic boolean isFull() {return size == 0;}
}

3.双端队列的数组实现

下面看一下双端队列的数组实现：

下面看一下具体的代码：

/**用数组来实现双端队列*/
public class L15_ArrayDeque<E> implements L15_TwoQueue<E>{E[] array;int head;//头指针int tail;//尾指针/**构造函数，创建出数组（也就是双端队列）*/public L15_ArrayDeque(int capacity) {array = (E[]) new Object[capacity+1];}/**处理索引越界的两个方法*//**处理索引加1时的*/static int inc(int i, int length){if (i+1 >= length){return 0;}return i+1;}/**处理索引减1时的*/static int dec(int i, int length){if (i-1 < 0){return length-1;}return i-1;}@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];head = inc(head,array.length);return e;}@Overridepublic E pollLast() {if (isEmpty())return null;tail = dec(tail,array.length);return array[tail];}@Overridepublic E peekFirst() {return array[head];}@Overridepublic E peekLast() {return array[tail];}@Overridepublic boolean isEmpty() {return head == tail;}@Overridepublic boolean isFull() {if (tail>head)return tail-head == array.length-1;if (tail<head)return head-tail == 1;if (tail == head)return false;return true;}
}

用数组实现双端队列不是太清楚，主要还是用链表来实现吧。

4.优先队列无序数组实现

优先队列，就是队列中的元素具有不同优先级的一种队列。入队的操作和普通队列一样，但是出队时是优先级高的元素先出队。

下面我们来看一下优先队列的具体实现：

下面看一下具体的代码：

/*** 用无序数组来实现优先队列* */
public class L16_PriorityQueue<E extends L16_Priority> implements L8_QueueInter<E>{L16_Priority[] array;int size;public L16_PriorityQueue(int capacity) {array = new L16_Priority[capacity];}@Overridepublic boolean offer(E value) {if(isFull())return false;array[size] = value;size++;return true;}/**返回优先级最高的索引*/private int selectMax(){int max = 0;for (int i = 0; i < size; i++) {if (array[i].priority() > array[max].priority())max = i;}return max;}@Overridepublic E poll() {if (isEmpty())return null;int max = selectMax();E e = (E)array[max];remove(max);return e;}private void remove(int index){if (index < size-1){System.arraycopy(array,index+1,array,index,size-1-index);}size--;}@Overridepublic E peek() {if (isEmpty())return null;int max = selectMax();return (E)array[max];}@Overridepublic boolean isEmpty() {return size == 0;}@Overridepublic boolean isFull() {return size == array.length;}
}

不算难，理清思路很简单的。

优先队列基于有序数组的实现和这个类似，并且比这个更简单，就是在入队操作时要找准位置而已。