赞
踩
package com.datastructure; import java.util.Deque; import java.util.LinkedList; /** * 双向队列(Double-ended queue):允许在头部和尾部执行元素的添加或删除操作 * * 双向队列常用操作: * 方法名 描述 时间复杂度 * push_first() 将元素添加到队首 O(1) * push_last() 将元素添加到队尾 O(1) * pop_first() 删除队首元素 O(1) * pop_last() 删除队尾元素 O(1) * peek_first() 访问队首元素 O(1) * peek_last() 访问队尾元素 O(1) * * * 双向队列应用场景: * 撤销功能的实现 * * */ public class Deque1 { public static void main(String[] args) { /** * 初始化双向队列 */ Deque<Integer> deque = new LinkedList<>(); /** * 元素入队 */ deque.offerLast(2);//添加到队尾 deque.offerLast(5); deque.offerLast(4); deque.offerFirst(3);//添加队首 deque.offerFirst(1); /** * 访问元素 */ int peekFirst = deque.peekFirst();//队首元素 System.out.println("peekFirst = " + peekFirst); int peekLast = deque.peekLast(); System.out.println("peekLast = " + peekLast); /** * 元素出队 */ int popFirst = deque.pollFirst();//队首元素出队 System.out.println(popFirst); int popLast = deque.pollLast();//队尾元素出队 System.out.println("popLast = " + popLast); /** * 获取双向队列的长度 */ int size = deque.size(); System.out.println("size = " + size); /** * 判断双向队列是否为空 */ boolean isEmpty = deque.isEmpty(); System.out.println("isEmpty = " + isEmpty); } } /** * 双向队列的实现,可基于链表或数组作为底层数据结构 */ /** * 双向队列的实现: 1.基于双向链表的实现 */ class LinkedListDeque { private DListNode front;//头节点front private DListNode rear;//尾结点 private int queSize = 0;//双向队列长度 public LinkedListDeque() { front = rear = null; } /** * 获取双向队列的长度 */ public int size() { return queSize; } /** * 判断双向队列是否为空 */ public boolean isEmpty() { return size() == 0; } /** * 入队操作 */ private void push(int num, boolean isFront) { DListNode node = new DListNode(num); //链表为空,则令front和rear指向node if (isEmpty()) { front = rear = node; } else if (isFront) {//队首入队操作 //将node添加至链表头部 front.prev = node; node.next = front; front = node;//更新头节点 } else {//将node添加到链表尾部 rear.next = node; node.prev = rear; rear = node;//更新尾结点 } queSize++;//更新队列长度 } /** * 队首入队 * * @param num */ public void pushFirst(int num) { push(num, true); } /** * 队尾入队 * * @param num */ public void pushLast(int num) { push(num, false); } /** * 出队操作 * * @param isFront * @return */ private int pop(boolean isFront) { if (isEmpty()) { throw new IndexOutOfBoundsException(); } int val; //队首出队操作 if (isFront) { val = front.val;//暂存头节点值 //删除头节点 DListNode fNext = front.next; if (fNext != null) { fNext.prev = null; front.next = null; } front = fNext;//更新头节点 } else {//队尾出队操作 val = rear.val;//暂存尾结点 //删除尾结点 DListNode rPrev = rear.prev; if (rPrev != null) { rPrev.next = null; rear.prev = null; } rear = rPrev;//更新尾结点 } queSize--;//更新队列长度 return val; } /** * 队首出队 */ public int popFirst() { return pop(true); } /** * 队尾出队 */ public int popLast() { return pop(false); } /** * 访问队首元素 */ public int peekFirst() { if (isEmpty()) { throw new IndexOutOfBoundsException(); } return front.val; } /** * 访问队尾元素 */ public int peekLast() { if (isEmpty()) throw new IndexOutOfBoundsException(); return rear.val; } /** * 返回数组用于打印 */ public int[] toArray() { DListNode node = front; int[] res = new int[size()]; for (int i = 0; i < res.length; i++) { res[i] = node.val; node = node.next; } return res; } } /** * 双向链表节点实现 */ class DListNode { int val;//节点值 DListNode next;//后继节点引用 DListNode prev;//前驱节点引用 DListNode(int val) { this.val = val; prev = next = null; } } /** * 双向队列基于环形数组实现 */ class ArrayDeque { private int[] nums;//用于存储双向队列元素的数组 private int front;//队首指针,指向队首元素 private int queSize;//双向队列长度 public ArrayDeque(int capacity) { this.nums = new int[capacity]; front = queSize = 0; } /** * 获取双向队列的容量 */ public int capacity() { return nums.length; } /** * 获取双向队列的长度 */ public int size() { return queSize; } /** * 判断双向队列是否为空 */ public boolean isEmpty() { return this.size() == 0; } /** * 计算环形数组索引 */ private int index(int i) { //通过取余操作实现数组首尾相连 //当i越过数组尾部后,回到头部 //当i越过数组头部后,回到尾部 return (i + capacity()) % capacity(); } /** * 队首入队 */ public void pushFirst(int num) { if (queSize == capacity()) { System.out.println("双向队列已满"); return; } //队首指针向左移动一位 //通过取余操作实现front越过数组头部后回到尾部 front = index(front - 1); //将num添加到队首 nums[front] = num; queSize++; } /** * 队尾入队 */ public void pushLast(int num) { if (queSize == capacity()) { System.out.println("双向队列已满"); return; } //计算队尾指针,指向队尾索引+1 int rear = index(front + queSize); //将num添加到队尾 nums[rear] = num; queSize++; } /** * 队首出队 * * @return */ public int popFirst() { int num = peekFirst(); //队首指针向后移动一位 front = index(front + 1); queSize--; return num; } /** * 队尾出队 */ public int popLast() { int num = peekLast(); queSize--; return num; } /** * 访问队首元素 * * @return */ public int peekFirst() { if (isEmpty()) throw new IndexOutOfBoundsException(); return nums[front]; } /** * 访问队尾元素 */ public int peekLast() { if (isEmpty()) throw new IndexOutOfBoundsException(); //计算尾元素索引 int last = index(front + queSize - 1); return nums[last]; } /** * 返回数组用于打印 */ public int[] toArray() { //仅转换有效长度范围内的列表元素 int[] res = new int[queSize]; for (int i = 0, j = front; i < queSize; i++, j++) { res[i] = nums[index(j)]; } return res; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。