Очереди — это фундаментальная структура данных в информатике, основанная на принципе «первым пришел — первым обслужен» (FIFO). Они широко используются в различных приложениях, включая планирование процессов, управление сетевыми пакетами и обработку событий. В этой статье мы рассмотрим различные типы очередей и приведем примеры кода для их реализации.

1. Очередь на основе массива:
   Очередь на основе массива — одна из простейших реализаций очереди. Он использует массив для хранения элементов и два указателя, передний и задний, для отслеживания границ очереди. Вот пример реализации очереди на основе массива в Python:

class ArrayQueue:
    def __init__(self):
        self.queue = []
    def enqueue(self, item):
        self.queue.append(item)
    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
    def is_empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self.queue)

2. Очередь на основе связанного списка.
   Очередь на основе связанного списка использует структуру данных связанного списка для реализации очереди. Он поддерживает ссылки как на передние, так и на задние элементы очереди. Очереди на основе связанных списков обеспечивают динамическое изменение размера и эффективные операции постановки и удаления из очереди. Вот пример реализации очереди на основе связанного списка в Java:

class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
class LinkedListQueue {
    private Node front, rear;
    public LinkedListQueue() {
        this.front = this.rear = null;
    }
    public void enqueue(int item) {
        Node newNode = new Node(item);
        if (this.rear == null) {
            this.front = this.rear = newNode;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
        }
    }
    public int dequeue() {
        if (this.front == null)
            return Integer.MIN_VALUE;
        int item = this.front.data;
        this.front = this.front.next;
        if (this.front == null)
            this.rear = null;
        return item;
    }
    public boolean isEmpty() {
        return this.front == null;
    }
    public int size() {
        int count = 0;
        Node current = this.front;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

3. Очередь приоритетов.
   Очередь приоритетов присваивает значение приоритета каждому элементу и удаляет элементы из очереди в зависимости от их приоритета. Элементы с более высоким приоритетом удаляются из очереди раньше элементов с более низким приоритетом. Очереди с приоритетами могут быть реализованы с использованием куч, двоичных деревьев поиска или массивов. Вот пример приоритетной очереди, реализованной с помощью модуля heapqв Python:

import heapq
class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.index = 0
    def enqueue(self, item, priority):
        heapq.heappush(self.queue, (priority, self.index, item))
        self.index += 1
    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.queue)[-1]
    def is_empty(self):
        return len(self.queue) == 0
    def size(self):
        return len(self.queue)

Очереди — это важные структуры данных, которые играют жизненно важную роль в различных приложениях. В этой статье мы рассмотрели три различных типа очередей: очередь на основе массива, очередь на основе связанного списка и очередь с приоритетами. Мы предоставили примеры кода для каждого типа, чтобы помочь вам понять их реализацию. Эффективно используя очереди, вы можете оптимизировать свои алгоритмы и повысить эффективность своих программ.