Круговая очередь

В этой статье вы познакомитесь с очередями и узнаете, как их реализовывать в C, C++, Java и Python.

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

Как видите, после нескольких операций enqueue и dequeue образуются пустые пространства. 

Места в очереди с индексом 0 и 1 использовать повторно можно только после сброса очередей в исходное состояние. То есть, после удаления всех элементов.

Как работает круговой список

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

Ниже — пример кода, в котором реализовано циклическое инкрементирование. Оно происходит путем деления по модулю REAR + 1 на длину очереди: 

if REAR + 1 == 5 (переполнение), REAR = (REAR + 1)%5 = 0 (начало очереди)

Принцип работы круговой очереди

Круговая очередь работает следующим образом:

• Объявляем два указателя — REAR и FRONT.
• FRONT указывает на первый элемент очереди.
• REAR указывает на последний элемент очереди.
• При инициализации круговой очереди присваиваем REAR и FRONT значение -1.

1. Операция enqueue

• Проверяем, не заполнена ли очередь.
• После добавления первого элемента присваиваем указателю FRONT значение 0.
• Циклически инкрементируем значение REAR на 1. Когда указатель окажется в конце очереди, он должен переместится в ее начало.
• Добавляем новый элемент на ту позицию, куда указывает REAR.

2. Операция dequeue

• Проверяем, не пуста ли очередь.
• Получаем значение, на которое указывает FRONT.
• Циклически инкрементируем значение FRONT на 1.
• После добавления последнего элемента сбрасываем значения FRONT и REAR — присваиваем им -1.

Проверка на заполненность

• Вариант 1: FRONT = 0 && REAR == SIZE - 1
• Вариант 2: FRONT = REAR + 1

Рассмотрим второй вариант. Если указатель REAR перемещается в начало очереди и позже его значение становится на 1 меньше, чем FRONT, значит, очередь заполнена.

 

Реализация круговых очередей

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

Python

# Реализация круговых очередей в  Python

class MyCircularQueue():

    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = self.tail = -1

    # Добавляем элемент в круговую очередь
    def enqueue(self, data):

        if ((self.tail + 1) % self.k == self.head):
            print("Круговая очередь заполнена\n")

        elif (self.head == -1):
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = data

    # Удаляем элемент из очереди
    def dequeue(self):
        if (self.head == -1):
            print("Круговая очередь пуста\n")

        elif (self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.k
            return temp

    def printCQueue(self):
        if(self.head == -1):
            print("В круговой очереди нет элементов")

        elif (self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.head, self.k):
                print(self.queue[i], end=" ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end=" ")
            print()


# Инициализируется и вызывается объект MyCircularQueue следующим образом:
obj = MyCircularQueue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("Исходная очеред")
obj.printCQueue()

obj.dequeue()
print("После удаления элемента из очереди")
obj.printCQueue()

Java

// Реализация круговых очередей в  Java

public class CQueue {
  int SIZE = 5; // Размер круговой очереди
  int front, rear;
  int items[] = new int[SIZE];

  CQueue() {
    front = -1;
    rear = -1;
  }

  // Проверяем, не заполнена ли очередь
  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }

  // Проверяем, не пуста ли очередь
  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  // Добавляем новый элемент
  void enQueue(int element) {
    if (isFull()) {
      System.out.println("Очередь заполнена");
    } else {
      if (front == -1)
        front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      System.out.println("Добавлено значение " + element);
    }
  }

  // Удаление элемента
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("Очередь пуста");
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      } /*  Внутри Q только один элемент, поэтому очередь сбрасывается
           в начальное состояние после удаления последнего элемента */
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    /* Функция выводит консоль статус кругового списка*/
    int i;
    if (isEmpty()) {
      System.out.println("Очередь пуста");
    } else {
      System.out.println("Указатель FRONT-> " + front);
      System.out.println("Элементы -> ");
      for (i = front; i != rear; i = (i + 1) % SIZE)
        System.out.print(items[i] + " ");
      System.out.println(items[i]);
      System.out.println("Rear -> " + rear);
    }
  }

  public static void main(String[] args) {

    CQueue q = new CQueue();

    // Ошибка, потому что FRONT = -1
    q.deQueue();

    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // Ошибка при добавлении элемента, потому что FRONT == 0 && REAR == SIZE - 1
    q.enQueue(6);

    q.display();

    int elem = q.deQueue();

    if (elem != -1) {
      System.out.println("Удаленный элемент: " + elem);
    }
    q.display();

    q.enQueue(7);

    q.display();

    // Ошибка при добавлении элемента, потому что FRONT == REAR + 1
    q.enQueue(8);
  }

}

C

// Реализация круговых очередей в  C

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// Проверяем, не заполнена ли очередь
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}

// Проверяем, не пуста ли очередь
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// Добавляем элемент
void enQueue(int element) {
  if (isFull())
    printf("\n Очередь заполнена \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\n Добавлен элемент -> %d", element);
  }
}

// Удаляем элемент
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Очередь пуста \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Внутри Q только один элемент, поэтому очередь сбрасывается в начальное  
    // cостояние после удаления последнего элемента
    else {
      front = (front + 1) % SIZE;
    }
    printf("\n Удаленный элемент -> %d \n", element);
    return (element);
  }
}

// Выводим очередь в консоль
void display() {
  int i;
  if (isEmpty())
    printf(" \n Пустая очередь\n");
  else {
    printf("\n Указатель FRONT -> %d ", front);
    printf("\n Элементы -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}

int main() {
  // Ошибка, потому что front = -1
  deQueue();

  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // Ошибка, потому что front == 0 && rear == SIZE - 1
  enQueue(6);

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  // Ошибка, потому что front == rear + 1
  enQueue(8);

  return 0;
}

C++

// Реализация круговых очередей в  C++

#include <iostream>
#define SIZE 5 /* Размер круговой очереди */

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }
  // Проверяем, не заполнена ли очередь
  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }
  // Проверяем, не пуста ли очередь
  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }
  // Добавляем элемент
  void enQueue(int element) {
    if (isFull()) {
      cout << "Очередь заполнена";
    } else {
      if (front == -1) front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      cout << endl
         << "Добавлен элемент " << element << endl;
    }
  }
  // Удаляем элемент
  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "Очередь пуста" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      }
    // Внутри Q только один элемент, поэтому очередь сбрасывается в начальное  
    // cостояние после удаления последнего элемента
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    // Функция, выводящая в консоль статус круговой очереди
    int i;
    if (isEmpty()) {
      cout << endl
         << "Пустая очередь" << endl;
    } else {
      cout << "Указатель FRONT -> " << front;
      cout << endl
         << "Элементы -> ";
      for (i = front; i != rear; i = (i + 1) % SIZE)
        cout << items[i];
      cout << items[i];
      cout << endl
         << "Указатель REAR-> " << rear;
    }
  }
};

int main() {
  Queue q;

  // Ошибка, потому что front = -1
  q.deQueue();

  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // Ошибка, потому что front == 0 && rear == SIZE - 1
  q.enQueue(6);

  q.display();

  int elem = q.deQueue();

  if (elem != -1)
    cout << endl
       << "Удаленный элемент " << elem;

  q.display();

  q.enQueue(7);

  q.display();

  // Ошибка, потому что front == rear + 1
  q.enQueue(8);

  return 0;
}

Временная сложность кругового списка

Сложность операций enqueue и dequeue круговой очереди, реализованной с помощью массивов — O(1).

Где применяются круговые списки

• Планирование процессов.
• Управление памятью.
• Управление трафиком.