为校园网站建设提供,深圳建设人力资源网,项目开发的五个阶段,百度浏览器在线打开这篇文章主要讲一下双端队列#xff0c;优先队列#xff0c;阻塞队列等队列的拓展内容。
目录
1.队列拓展概述
2.双端队列的链表实现
3.双端队列的数组实现
4.优先队列无序数组实现
5.阻塞队列
6.总结 1.队列拓展概述
首先来看一张图#xff0c;来大致了解一下他们的…这篇文章主要讲一下双端队列优先队列阻塞队列等队列的拓展内容。
目录
1.队列拓展概述
2.双端队列的链表实现
3.双端队列的数组实现
4.优先队列无序数组实现
5.阻塞队列
6.总结 1.队列拓展概述
首先来看一张图来大致了解一下他们的区别。
双端队列即两端都可以删除和添加的队列并且满足队列FIFO的特点。 2.双端队列的链表实现
下面来看一下双端队列的链表实现 代码如下
/*** 基于双向环形链表实现双端队列* */
public class L15_LinkedListDequeE implements L15_TwoQueueE {/**节点类的设计*/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;}}int capacity;//容量int size;//有效元素个数NodeE 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;NodeE a sentinel;NodeE b sentinel.next;NodeE added new Node(a,e,b);a.next added;b.prev added;size;return true;}Overridepublic boolean offerLast(E e) {if (isFull())return false;NodeE a sentinel.prev;NodeE b sentinel;NodeE added new Node(a,e,b);a.next added;b.prev added;size;return true;}Overridepublic E pollFirst() {if (isEmpty())return null;NodeE a sentinel;NodeE removed sentinel.next;NodeE b removed.next;a.next b;b.prev a;size--;return removed.value;}Overridepublic E pollLast() {if (isEmpty())return null;NodeE removed sentinel.prev;NodeE a removed.prev ;NodeE 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_ArrayDequeE implements L15_TwoQueueE{E[] array;int head;//头指针int tail;//尾指针/**构造函数创建出数组也就是双端队列*/public L15_ArrayDeque(int capacity) {array (E[]) new Object[capacity1];}/**处理索引越界的两个方法*//**处理索引加1时的*/static int inc(int i, int length){if (i1 length){return 0;}return i1;}/**处理索引减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 (tailhead)return tail-head array.length-1;if (tailhead)return head-tail 1;if (tail head)return false;return true;}
}
用数组实现双端队列不是太清楚主要还是用链表来实现吧。
4.优先队列无序数组实现
优先队列就是队列中的元素具有不同优先级的一种队列。入队的操作和普通队列一样但是出队时是优先级高的元素先出队。
下面我们来看一下优先队列的具体实现 下面看一下具体的代码
/*** 用无序数组来实现优先队列* */
public class L16_PriorityQueueE extends L16_Priority implements L8_QueueInterE{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,index1,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;}
}不算难理清思路很简单的。
优先队列基于有序数组的实现和这个类似并且比这个更简单就是在入队操作时要找准位置而已。
5.阻塞队列
阻塞队列涉及的其他方面的内容当我那部分的内容更新完毕后再回来更新这个阻塞队列的实现。
6.总结
总的来说队列不难关键就是抓住链表和数组的特点掌握链表和数组的相关操作就行
