Дек

Последнее обновление: 02.09.2016

Дек (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).

Дек в C#

Применение дека:

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
Помощь сайту
Юмани:
410011174743222
Перевод на карту
Номер карты:
4048415020898850