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

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

Метод 1: реализация на основе массива
Один из самых простых способов реализации циклической очереди — использование массива. Вот пример на Python:

class CircularQueue:
    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = self.tail = -1
    def enqueue(self, item):
        if (self.tail + 1) % self.k == self.head:
            print("Queue is full.")
        elif self.head == -1:  # First element
            self.head = self.tail = 0
            self.queue[self.tail] = item
        else:
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = item
    def dequeue(self):
        if self.head == -1:
            print("Queue is empty.")
            return None
        elif self.head == self.tail:  # Last element
            item = self.queue[self.head]
            self.head = self.tail = -1
            return item
        else:
            item = self.queue[self.head]
            self.head = (self.head + 1) % self.k
            return item

Метод 2: реализация на основе связанного списка
Другой подход заключается в реализации циклической очереди с использованием связанного списка. Вот пример на Java:

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
class CircularQueue {
    Node head, tail;
    int k;
    int size;

    public CircularQueue(int k) {
        this.k = k;
        this.size = 0;
    }

    public void enqueue(int item) {
        if (size == k) {
            System.out.println("Queue is full.");
            return;
        }

        Node newNode = new Node(item);

        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }

        tail.next = head;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            System.out.println("Queue is empty.");
            return -1;
        }

        int item = head.data;

        if (size == 1) {
            head = tail = null;
        } else {
            head = head.next;
            tail.next = head;
        }

        size--;
        return item;
    }
}

Круговые очереди — это мощная структура данных для эффективных операций с очередями. Независимо от того, решите ли вы реализовать их с использованием массива или связанного списка, циклический характер очереди обеспечивает постоянную сложность времени для операций постановки и удаления из очереди. Это делает циклические очереди подходящими для сценариев, в которых необходимо обрабатывать элементы в циклическом порядке. Понимая различные методы реализации циклической очереди, вы сможете использовать эту структуру данных для оптимизации своего кода.