¡¾ÓÞ¹«ÏµÁС¿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(); // ¶ÓβԪËسö¶Ó
/* »ñÈ¡Ë«Ïò¶ÓÁеij¤¶È */
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; // Ë«Ïò¶ÓÁеij¤¶È
	public LinkedListDeque() {
		front = null;
		rear = null;
	}
	/* »ñÈ¡Ë«Ïò¶ÓÁеij¤¶È */
	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;
	}
	/* »ñÈ¡Ë«Ïò¶ÓÁеij¤¶È */
	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;
	}
}