Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Дек (очередь с двумя концами, двухсторонняя очередь, от англ. deque — double-ended queue) — это структура данных, которая позволяет добавлять и удалять элементы как с начала, так и с конца.

---

Сферы применения

1. Обработка данных в реальном времени. Дек полезен для обработки данных с обеих сторон, когда данные поступают и уходят одновременно. Например, очереди событий, обработка сообщений или данных с сенсоров, где важно контролировать порядок поступления данных.

2. Игровая логика (например, карточные игры). Дек может быть использован для моделирования игры с колодой карт, где карты вытягиваются с одного конца и добавляются в другой.

---

Операции

Дек поддерживает следующие операции:

1. Добавление в начало ($push\_front$) — добавляет элемент в начало дека. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

2. Добавление в конец ($push\_back$) — добавляет элемент в конец дека. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

3. Удаление из начала ($pop\_front$) — удаляет элемент из начала дека. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

4. Удаление из конца ($pop\_back$) — удаляет элемент из конца дека. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

5. Проверка на пустоту ($is\_empty$) — проверка, пуст ли дек. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

6. Получение размера ($size$) — показывает, сколько элементов сейчас в деке. Вычислительная сложность - $O(1)$ Пространственная сложность - $O(1)$

---

Добавление в начало

Эта операция добавляет новый элемент в начало дека.

Пусть есть дек:

При добавлении элемента в начало, он становится новым началом дека:

После выполнения операции дек будет выглядеть следующим образом:

• Вычислительная сложность: $O(1)$
  Элемент добавляется в начало дека, при этом изменяются указатели на начало и предыдущий элемент, что выполняется за постоянное время.
• Пространственная сложность: $O(1)$
  Не требуется выделение дополнительной памяти, кроме новой ячейки для узла.

Добавить_в_начало(элемент):
    Новый_узел = Узел(элемент)
    Если Дек_пуст():
        Начало_дека = Новый_узел
        Конец_дека = Новый_узел
        
    Иначе:
        Новый_узел.следующий_элемент = Начало_дека
        Начало_дека.предыдущий_элемент = Новый_узел
        Начало_дека = Новый_узел
        
    Размер = Размер + 1

---

Добавление в конец

Эта операция добавляет новый элемент в конец дека.

Пусть есть дек:

При добавлении элемента в конец, он становится новым концом дека:

После выполнения операции дек будет выглядеть следующим образом:

• Вычислительная сложность: $O(1)$
  Добавление элемента в конец происходит за постоянное время, изменяются указатели на конец и следующий элемент.
• Пространственная сложность: $O(1)$
  Память выделяется только для нового узла, остальные данные остаются неизменными.

Добавить_в_конец(элемент):
    Новый_узел = Узел(элемент)
    Если Дек_пуст():
        Начало_дека = Новый_узел
        Конец_дека = Новый_узел
        
    Иначе:
        Новый_узел.предыдущий_элемент = Конец_дека
        Конец_дека.следующий_элемент = Новый_узел
        Конец_дека = Новый_узел
        
    Размер = Размер + 1

---

Удаление из начала

Эта операция удаляет элемент из начала дека.

Пусть есть дек:

При удалении элемента из начала, следующий элемент после удалённого становится новым началом дека:

После выполнения операции дек будет выглядеть следующим образом:

• Вычислительная сложность: $O(1)$ Удаление первого элемента из дека требует только изменения указателя на новый первый элемент, что выполняется за постоянное время.
• Пространственная сложность: $O(1)$ Освобождается память, занимаемая удалённым узлом, дополнительные ресурсы не требуются.

Удалить_из_начала():
    Если Дек_пуст():
        Вернуть пустота

    Удаляемый_элемент = Начало_дека
    Начало_дека = Начало_дека.следующий_элемент
    
    Если Начало_дека != пустота:
        Начало_дека.предыдущий_элемент = пустота
        
    Иначе:
        Конец_дека = пустота
        
    Размер = Размер - 1
    Вернуть Удаляемый_элемент

---

Удаление из конца

Эта операция удаляет элемент из конца дека.

Пусть есть дек:

При удалении элемента из конца, предыдущий элемент после удалённого становится новым концом дека:

После выполнения операции дек будет выглядеть следующим образом:

• Вычислительная сложность: $O(1)$
  Удаление последнего элемента из дека требует только изменения указателя на новый последний элемент, операция выполняется за постоянное время.
• Пространственная сложность: $O(1)$
  Освобождается память удалённого узла, новых затрат памяти не требуется.

Удалить_из_конца():
    Если Дек_пуст():
        Вернуть пустота

    Удаляемый_элемент = Конец_дека
    Конец_дека = Конец_дека.предыдущий_элемент
    
    Если Конец_дека != пустота:
        Конец_дека.следующий_элемент = пустота
        
    Иначе:
        Начало_дека = пустота
        
    Размер = Размер - 1
    Вернуть Удаляемый_элемент

---

Проверка на пустоту

Эта операции проверяет дек на пустоту. Если в деке нет элементов, то эта операция возвращает "Правда", иначе операция вернёт "Ложь".

Пусть есть дек:

В деке есть элементы, поэтому операция вернёт "Ложь".

• Вычислительная сложность: $O(1)$
  Проверка на пустоту заключается в проверке указателей на начало и конец дека, выполняется за постоянное время.
• Пространственная сложность: $O(1)$
  Не требует выделения дополнительной памяти, используется только текущая информация о деке.

Дек_пуст():
    Если Начало_дека = пустота:
        Вернуть Правда
        
    Иначе:
        Вернуть Ложь

---

Получение размера

Эта операция возвращает количество элементов в деке.

Пусть есть дек:

В деке всего четыре элемента, поэтому операция вернёт число $4$

• Вычислительная сложность: $O(1)$
  Хранение размера дека в отдельной переменной позволяет возвращать его значение за постоянное время.
• Пространственная сложность: $O(1)$
  Дополнительная память используется только для хранения переменной размера, что не зависит от числа элементов.

Получить_размер():
    Вернуть Размер

---

Псевдокод

Класс Узел (значение = пустота, ссылка на следующий элемент = пустота, ссылка на предыдущий элемент = пустота):
    Значение
    Ссылка на следующий элемент
    Ссылка на предыдущий элемент

Класс Дек():

    Размер = 0
    Начало_дека ← Узел()
    Конец_дека ← Узел(предыдущий = начало)

    Добавить_в_начало(элемент):

        Новый_узел = Узел(элемент)
        Если Дек_пуст():
            Начало_дека = Новый_узел
            Конец_дека = Новый_узел
        Иначе:
            Новый_узел.следующий_элемент = Начало_дека
            Начало_дека.предыдущий_элемент = Новый_узел
            Начало_дека = Новый_узел
        Размер = Размер + 1

    Добавить_в_конец(элемент):
        Новый_узел = Узел(элемент)
        Если Дек_пуст():
            Начало_дека = Новый_узел
            Конец_дека = Новый_узел
            
        Иначе:
            Новый_узел.предыдущий_элемент = Конец_дека
            Конец_дека.следующий_элемент = Новый_узел
            Конец_дека = Новый_узел
            
        Размер = Размер + 1

    Удалить_из_начала():
        Если Дек_пуст():
            Вернуть пустота
            
        Удаляемый_элемент = Начало_дека
        Начало_дека = Начало_дека.следующий_элемент
        Если Начало_дека != пустота:
            Начало_дека.предыдущий_элемент = пустота
            
        Иначе:
            Конец_дека = пустота
            
        Размер = Размер - 1
        Вернуть Удаляемый_элемент

    Удалить_из_конца():
        Если Дек_пуст():
            Вернуть пустота
            
        Удаляемый_элемент = Конец_дека
        Конец_дека = Конец_дека.предыдущий_элемент
        Если Конец_дека != пустота:
            Конец_дека.следующий_элемент = пустота
            
        Иначе:
            Начало_дека = пустота
            
        Размер = Размер - 1
        Вернуть Удаляемый_элемент

    Дек_пуст():
        Если Начало_дека = пустота:
            Вернуть Правда
        Иначе:
            Вернуть Ложь

    Получить_размер():
        Вернуть Размер

---

Реализация на Python

Аннотация:
Node - узел
data - данные, хранящиеся в узле
next - указатель на следующий элемент
prev - указатель на предыдущий элемент
Deque - двусторонняя очередь
head - начало дека
tail - конец дека
size - размер дека
is_empty - метод проверки дека на пустоту
push_front - метод добавления элемента в начало дека
new_node - добавляемый узел
push_back - метод добавления элемента в конец дека
pop_front - метод удаления элемента из начала дека
pop_back - метод удаления элемента из конца дека
front - метод просмотра элемента из начала дека
back - метод просмотра элемента из конца дека
get_size - метод, который возвращает размер дека

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None
  
class Deque:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def push_front(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = self.tail = new_node
            
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

        self.size += 1

    def push_back(self, data):
        new_node = Node(data)
        if self.is_empty():
            self.head = self.tail = new_node

        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
            
        self.size += 1

    def pop_front(self):
        if self.is_empty():
            raise IndexError("pop from empty deque")
            
        data = self.head.data
        self.head = self.head.next
        if self.head:
            self.head.prev = None

        else:
            self.tail = None

        self.size -= 1
        return data

    def pop_back(self):
        if self.is_empty():
            raise IndexError("pop from empty deque")

        data = self.tail.data
        self.tail = self.tail.prev
        if self.tail:
            self.tail.next = None

        else:
            self.head = None

        self.size -= 1
        return data
        
    def front(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        return self.head.data

    def back(self):
        if self.is_empty():
            raise IndexError("deque is empty")
        return self.tail.data

    def get_size(self):
        return self.size

---

Реализация на C++

Аннотация:
template - шаблон функции
Node - узел
data - данные, хранящиеся в узле
next - указатель на следующий элемент
prev - указатель на предыдущий элемент
Deque - двусторонняя очередь
deque_size - размер дека
head - начало дека
tail - конец дека
is_empty - метод проверки дека на пустоту
push_front - метод добавления элемента в начало дека
new_node - добавляемый узел
push_back - метод добавления элемента в конец дека
pop_front - метод удаления элемента из начала дека
pop_back - метод удаления элемента из конца дека
front - метод просмотра элемента из начала дека
back - метод просмотра элемента из конца дека
get_size - метод, который возвращает размер дека

#include <stdexcept>
#include <iostream>
using namespace std;
template <typename T>

struct Node {
    T data;
    Node* next = nullptr;
    Node* prev = nullptr;
    Node(T new_data = T()) : data(new_data), next(nullptr), prev(nullptr) {}

};

template <typename T>
class Deque {
private:
    int deque_size = 0;
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;
  
public:
    void push_front(T data);
    void push_back(T data);
    T pop_front();
    T pop_back();
    bool is_empty();
    int size();
    T front();
    T back();
    ~Deque();
};

template <typename T>
bool Deque<T>::is_empty() {
    return head == nullptr;
}

template <typename T>
void Deque<T>::push_front(T data) {
    Node<T>* new_node = new Node<T>(data);
    if (is_empty()) {
        head = tail = new_node;

    } else {
        new_node->next = head;
        head->prev = new_node;
        head = new_node;
    }
    deque_size++;

}

template <typename T>
void Deque<T>::push_back(T data) {
    Node<T>* new_node = new Node<T>(data);
    if (is_empty()) {
        head = tail = new_node;

    } else {
        new_node->prev = tail;
        tail->next = new_node;
        tail = new_node;
    }
    deque_size++;

}

template <typename T>
T Deque<T>::pop_front() {
    if (is_empty()) {
        throw std::out_of_range("Попытка удаления элемента из пустого дека");
    }
    Node<T>* old_head = head;
    T removed_data = old_head->data;
    head = head->next;
    if (head != nullptr) {
        head->prev = nullptr;

    } else {
        tail = nullptr;
    }
    delete old_head;
    deque_size--;
    return removed_data;
}

template <typename T>
T Deque<T>::pop_back() {
    if (is_empty()) {
        throw std::out_of_range("Попытка удаления элемента из пустого дека");
    }
    
    Node<T>* old_tail = tail;
    T removed_data = old_tail->data;
    tail = tail->prev;
    if (tail != nullptr) {
        tail->next = nullptr;

    } else {
        head = nullptr;
    }

    delete old_tail;
    deque_size--;
    return removed_data;
}

template <typename T>
int Deque<T>::size() {
    return deque_size;
}

template <typename T>
T Deque<T>::front() {
    if (is_empty()) {
        throw std::out_of_range("Дек пуст");
    }

    return head->data;
}

template <typename T>
T Deque<T>::back() {
    if (is_empty()) {
        throw std::out_of_range("Дек пуст");
    }

    return tail->data;
}

template <typename T>
Deque<T>::~Deque() {
    while (!is_empty()) {
        pop_front();
    }
}