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

Определение

Очередь — это структура данных, организованная по принципу "первым пришёл — первым вышел" (FIFO, от англ. First In, First Out). В ней элементы добавляются в конец очереди, а удаляются с начала.

---

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

1. Сетевые буферы. В телекоммуникациях очереди используются для временного хранения пакетов данных, прежде чем они будут обработаны и переданы дальше по сети. Например, роутеры используют очереди для управления трафиком и гарантии правильной последовательности передачи данных.
2. Игровые серверы. Очереди применяются в многопользовательских играх для управления подключениями и распределения нагрузки между серверами.

---

Операции

Очередь поддерживает следующие операции:

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

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

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

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

---

Добавление элемента

Пусть есть очередь:

При добавлении нового элемента в очередь, он помещается в конец очереди. Новым последним элементом очереди становится добавленный элемент.

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

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

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

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

    Размер = Размер + 1

---

Удаление элемента

Пусть есть очередь:

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

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

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

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

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

---

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

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

Пусть есть очередь:

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

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

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

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

---

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

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

Пусть есть очередь:

В очереди всего пять элементов, поэтому операция вернёт число $5$.

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

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

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

---

Псевдокод

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

Класс Очередь():
    Размер = 0
    Конец_очереди <- Узел()
    Начало_очереди <- Узел(следующий = конец)

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

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

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

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

---

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

Аннотация:
Node - узел
data - данные, хранящиеся в узле
next - указатель на следующий элемент в очереди
prev - указатель на предыдущий элемент в очереди
Queue - очередь
head - начало очереди
tail - конец очереди
_size - размер очереди
push - метод добавления элемента в очередь
new_element - добавляемый в очередь элемент
pop - метод удаления элемента из очереди
is_empty - метод проверки очереди на пустоту
removed_data - значение удаляемого узла
size - метод получения размера очереди

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
        self.prev = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def push(self, data):
        new_element = Node(data)
        
        if self.is_empty():
            self.head = self.tail = new_node
            
        else:
            new_element.prev = self.tail
            self.tail.next = new_element
            self.tail = new_element
        
        self._size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Попытка удаления элемента из пустой очереди")
            
        removed_data = self.head.data
        self.head = self.head.next
        
        if self.head is not None:
            self.head.prev = None
            
        else:
            self.tail = None
        
        self._size -= 1
        
        return removed_data
  
    def is_empty(self):
        return self.head is None
  
    def size(self):
        return self._size

---

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

Аннотация
template - шаблон функции
Node - узел
data - данные, хранящиеся в узле
next - указатель на следующий элемент в очереди
prev - указатель на предыдущий элемент в очереди
new_data - новое значение узла
Queue - очередь
size - размер очереди
head - начало очереди
tail - конец очереди
push - метод добавления элемента в очередь
pop - метод удаления элемента из очереди
is_empty - метод проверки очереди на пустоту
size - метод получения размера очереди
new_element - добавляемый в очередь элемент
old_head - удаляемый элемент
removed_data - значение удаляемого элемента

#include <stdexcept>

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 Queue {
private:
    int size = 0;
    Node<T>* head = nullptr;
    Node<T>* tail = nullptr;

public:
    void push(T data);
    T pop();
    bool is_empty();
    int size();
    ~Queue();
};

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

template <typename T>
void Queue<T>::push(T data) {
    Node<T>* new_element = new Node<T>(data);
    if (is_empty()) {
        head = tail = new_element;
    } else {
        new_element->prev = tail;
        tail->next = new_element;
        tail = new_element;
    }
    size++;
}

template <typename T>
T Queue<T>::pop() {
    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;
    size--;
    return removed_data;
}

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

template <typename T>
Queue<T>::~Queue() {
    while (!is_empty()) {
        pop();
    }
}