【愚公系列】2023年11月 数据结构(六)-双向队列

using System.Collections.Generic;

Deque<int> deque = new Deque<int>();
deque.EnqueueFront(1);
deque.EnqueueBack(2);
deque.EnqueueBack(3);
int count = deque.Count; // count为3
int front = deque.PeekFront(); // front为1
int back = deque.PeekBack(); // back为3
deque.DequeueFront(); // 队列变为2, 3
deque.DequeueBack(); // 队列变为2
bool contains = deque.Contains(2); // contains为true
int[] array = new int[3];
deque.CopyTo(array, 0); // 数组变为2
deque.Clear(); // 清空队列中的所有元素

/* 初始化双向队列 */
// 在 C# 中，将链表 LinkedList 看作双向队列来使用
LinkedList<int> deque = new LinkedList<int>();
/* 元素入队 */
deque.AddLast(2); // 添加至队尾
deque.AddLast(5);
deque.AddLast(4);
deque.AddFirst(3); // 添加至队首
deque.AddFirst(1);
/* 访问元素 */
int peekFirst = deque.First.Value; // 队首元素
int peekLast = deque.Last.Value; // 队尾元素
/* 元素出队 */
deque.RemoveFirst(); // 队首元素出队
deque.RemoveLast(); // 队尾元素出队
/* 获取双向队列的长度 */
int size = deque.Count;
/* 判断双向队列是否为空 */
bool isEmpty = deque.Count == 0;

/* 双向链表节点 */
class ListNode {
	public int val; // 节点值
	public ListNode? next; // 后继节点引用
	public ListNode? prev; // 前驱节点引用
	public ListNode(int val) {
		this.val = val;
		prev = null;
		next = null;
	}
}
/* 基于双向链表实现的双向队列 */
class LinkedListDeque {
	private ListNode? front, rear; // 头节点 front, 尾节点 rear
	private int queSize = 0; // 双向队列的长度
	public LinkedListDeque() {
		front = null;
		rear = null;
	}
	/* 获取双向队列的长度 */
	public int size() {
		return queSize;
	}
	/* 判断双向队列是否为空 */
	public bool isEmpty() {
		return size() == 0;
	}
	/* 入队操作 */
	private void push(int num, bool isFront) {
		ListNode node = new ListNode(num);
		// 若链表为空，则令 front, rear 都指向 node
		if (isEmpty()) {
			front = node;
			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++; // 更新队列长度
	}
	/* 队首入队 */
	public void pushFirst(int num) {
		push(num, true);
	}
	/* 队尾入队 */
	public void pushLast(int num) {
		push(num, false);
	}
	/* 出队操作 */
	private int? pop(bool isFront) {
		// 若队列为空，直接返回 null
		if (isEmpty()) {
			return null;
		}
		int val;
		// 队首出队操作
		if (isFront) {
			val = front.val; // 暂存头节点值
			// 删除头节点
			ListNode fNext = front.next;
			if (fNext != null) {
				fNext.prev = null;
				front.next = null;
			}
			front = fNext; // 更新头节点
		}
		// 队尾出队操作
		else {
			val = rear.val; // 暂存尾节点值
			// 删除尾节点
			ListNode 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() {
		return isEmpty() ? null : front.val;
	}
	/* 访问队尾元素 */
	public int? peekLast() {
		return isEmpty() ? null : rear.val;
	}
	/* 返回数组用于打印 */
	public int[] toArray() {
		ListNode 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 ArrayDeque {
	private readonly 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 bool isEmpty() {
		return queSize == 0;
	}
	/* 计算环形数组索引 */
	private int index(int i) {
		// 通过取余操作实现数组首尾相连
		// 当 i 越过数组尾部后，回到头部
		// 当 i 越过数组头部后，回到尾部
		return (i + capacity()) % capacity();
	}
	/* 队首入队 */
	public void pushFirst(int num) {
		if (queSize == capacity()) {
			Console.WriteLine(" 双向队列已满");
			return;
		}
		// 队首指针向左移动一位
		// 通过取余操作，实现 front 越过数组头部后回到尾部
		front = index(front - 1);
		// 将 num 添加至队首
		nums[front] = num;
		queSize++;
	}
	/* 队尾入队 */
	public void pushLast(int num) {
		if (queSize == capacity()) {
			Console.WriteLine(" 双向队列已满");
			return;
		}
		// 计算尾指针，指向队尾索引 + 1
		int rear = index(front + queSize);
		// 将 num 添加至队尾
		nums[rear] = num;
		queSize++;
	}
	/* 队首出队 */
	public int popFirst() {
		int num = peekFirst();
		// 队首指针向后移动一位
		front = index(front + 1);
		queSize--;
		return num;
	}
	/* 队尾出队 */
	public int popLast() {
		int num = peekLast();
		queSize--;
		return num;
	}
	/* 访问队首元素 */
	public int peekFirst() {
		if (isEmpty()) {
			throw new InvalidOperationException();
		}
		return nums[front];
	}
	/* 访问队尾元素 */
	public int peekLast() {
		if (isEmpty()) {
			throw new InvalidOperationException();
		}
		// 计算尾元素索引
		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;
	}
}