Дек (deque) представляет двустороннюю очередь, в которой элементы можно добавлять как в начало, так и в конец. Удаление также может идти как с начала, так и с конца.
Поскольку реализовать добавление и удаление нужно с двух сторон, то за основу реализации можно взять организацию двусвязного список. Так, каждый элемент в деке будет представлен следующим классом:
public class DoublyNode<T> { public DoublyNode(T data) { Data = data; } public T Data { get; set; } public DoublyNode<T> Previous { get; set; } public DoublyNode<T> Next { get; set; } }
Класс дека будет следующим:
using System; using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp { public class Deque<T> : IEnumerable<T> // двусвязный список { DoublyNode<T> head; // головной/первый элемент DoublyNode<T> tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void AddLast(T data) { DoublyNode<T> node = new DoublyNode<T>(data); if (head == null) head = node; else { tail.Next = node; node.Previous = tail; } tail = node; count++; } public void AddFirst(T data) { DoublyNode<T> node = new DoublyNode<T>(data); DoublyNode<T> temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; } public T RemoveFirst() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) { head = tail = null; } else { head = head.Next; head.Previous = null; } count--; return output; } public T RemoveLast() { if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) { head = tail = null; } else { tail = tail.Previous; tail.Next = null; } count--; return output; } public T First { get { if (IsEmpty) throw new InvalidOperationException(); return head.Data; } } public T Last { get { if (IsEmpty) throw new InvalidOperationException(); return tail.Data; } } public int Count { get { return count; } } public bool IsEmpty { get { return count == 0; } } public void Clear() { head = null; tail = null; count = 0; } public bool Contains(T data) { DoublyNode<T> current = head; while (current != null) { if (current.Data.Equals(data)) return true; current = current.Next; } return false; } IEnumerator IEnumerable.GetEnumerator() { return ((IEnumerable)this).GetEnumerator(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { DoublyNode<T> current = head; while (current != null) { yield return current.Data; current = current.Next; } } } }
В отличие от класса очереди здесь определены два метода для добавления и два для удаления.
Для добавления в начало очереди переустанавливаем ссылку на переменную head:
public void AddFirst(T data) { DoublyNode<T> node = new DoublyNode<T>(data); DoublyNode<T> temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; }
Добавление элемента в конец дека вызывает аналогичную переустановку переменной tail:
public void AddLast(T data) { DoublyNode<T> node = new DoublyNode<T>(data); if (head == null) head = node; else { tail.Next = node; node.Previous = tail; } tail = node; count++; }
При удалении из начала дека надо переустановить ссылку на первый элемент:
public T RemoveFirst() { if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) { head = tail = null; } else { head = head.Next; head.Previous = null; } count--; return output; }
При удалении последнего элемента переустанавливается переменная tail на предпоследний элемент:
public T RemoveLast() { if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) { head = tail = null; } else { tail = tail.Previous; tail.Next = null; } count--; return output; }
Сложность алгоритмов всех методов добавления и удаления из дека составляет O(1).
Применение дека:
Deque<string> usersDeck = new Deque<string>(); usersDeck.AddFirst("Alice"); usersDeck.AddLast("Kate"); usersDeck.AddLast("Tom"); foreach(string s in usersDeck) Console.WriteLine(s); string removedItem = usersDeck.RemoveFirst(); Console.WriteLine("\n Удален: {0} \n", removedItem); foreach (string s in usersDeck) Console.WriteLine(s);
Консольный вывод:
Alice Kate Tom Удален: Alice Kate Tom