Очередь

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

Представьте себе очередь в кассу кинотеатра. Кто раньше пришел, тот раньше получит билет. Так и в программировании.

Очередь подчиняется принципу FIFO — Firts In First Out («первый пришел — первый вышел»). Первый элемент в очереди выходит первым. 

Как видите, элемент 1 поступил в очередь до 2 и удалился первым — это и есть принцип FIFO.

Enqueue — метод, который добавляет элемент в очередь. Dequeue, наоборот, удаляет его. 

Реализовать очередь можно в любом языке — С, С++, Java, Python или C#. Во всех языках очереди очень похожи.

Как работает очередь

Очередь работает следующим образом:

• Реализуется два указателя — FRONT и REAR.
• FRONT — указатель на первый элемент очереди.
• REAR — указатель на последний элемент очереди. 
• Значения FRONT и REAR изначально должны быть равны -1.

Базовые операции с очередями

Очередь — объект (абстрактный тип данных. Он поддерживает такие операции:

• Enqueue — позволяет добавить элемент в конец очереди. 
• Pop — позволяет удалить элемент из начала очереди.
• IsEmpty — проверяет, пуста ли очередь.
• IsFull — проверяет, заполнена ли очередь.
• Peek — позволяет получить элемент в начале очереди без его удаления.

Операция enqueue

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

Операция dequeue

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

Реализация очередей

В Java и С++ очереди реализуются с помощью массивов. В Python — с помощью списков.

Python

# Реализация очередей в Python

class Queue:

    def __init__(self):
        self.queue = []

    # Добавляем элемент
    def enqueue(self, item):
        self.queue.append(item)

    # Удаляем элемент
    def dequeue(self):
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)

    # Выводим очередь в консоль
    def display(self):
        print(self.queue)

    def size(self):
        return len(self.queue)

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)

q.display()

q.dequeue()

print("После удаления элемента")
q.display()

Java

// Реализация очередей в Java

public class Queue {
  int SIZE = 5;
  int items[] = new int[SIZE];
  int front, rear;

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

  boolean isFull() {
    if (front == 0 && rear == SIZE - 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++;
      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++;
      }
      System.out.println("Удален элемент -> " + element);
      return (element);
    }
  }

  void display() {
    /* Функция выводит элементы очереди в консоль */
    int i;
    if (isEmpty()) {
      System.out.println("Пустая очередь");
    } else {
      System.out.println("\nИндекс FRONT-> " + front);
      System.out.println("Элементы -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      System.out.println("\nИндекс REAR-> " + rear);
    }
  }

  public static void main(String[] args) {
    Queue q = new Queue();

    // функцию deQueue нельзя применять к пустой очереди
    q.deQueue();

    // Добавляем в очередь 5 элементов
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);

    // Шестой элемент добавить нельзя — очередь заполнена
    q.enQueue(6);

    q.display();

    // Функция deQueue удаляет первый элемент — 1
    q.deQueue();

    // Теперь внутри очереди 4 элемента
    q.display();

  }
}

C

// Реализация очередей в C

#include <stdio.h>
#define SIZE 5

void enQueue(int);
void deQueue();
void display();

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

int main() {
  //функцию deQueue нельзя применять к пустой очереди
  deQueue();

  // Добавляем в очередь 5 элементов
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // Шестой элемент добавить нельзя — очередь заполнена
  enQueue(6);

  display();

  // Функция deQueue удаляет первый элемент — 1
  deQueue();

  // Теперь внутри очереди 4 элемента
  display();

  return 0;
}

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

void deQueue() {
  if (front == -1)
    printf("\nОчередь пуста");
  else {
    printf("\nУдален элемент: %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}

// Функция выводит очередь в консоль
void display() {
  if (rear == -1)
    printf("\nОчередь пуста");
  else {
    int i;
    printf("\nЭлементы очереди:\n");
    for (i = front; i <= rear; i++)
      printf("%d  ", items[i]);
  }
  printf("\n");
}

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;
    }
    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++;
      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 только один элемент, поэтому очередь сбрасывается
        в начальное состояние после удаления последнего элемента */
      else {
        front++;
      }
      cout << endl
         << "Удален элемент -> " << element << endl;
      return (element);
    }
  }

  void display() {
    /* Функция выводит в консоль элементы очереди */
    int i;
    if (isEmpty()) {
      cout << endl
         << "Пустая очередь" << endl;
    } else {
      cout << endl
         << "Индекс FRONT -> " << front;
      cout << endl
         << "Элементы -> ";
      for (i = front; i <= rear; i++)
        cout << items[i] << "  ";
      cout << endl
         << "Индекс REAR-> " << rear << endl;
    }
  }
};

int main() {
  Queue q;

  // функцию deQueue нельзя применять к пустой очереди
  q.deQueue();

  // Добавляем 5 элементов
  q.enQueue(1);
  q.enQueue(2);
  q.enQueue(3);
  q.enQueue(4);
  q.enQueue(5);

  // Шестой элемент добавить нельзя — очередь заполнена
  q.enQueue(6);

  q.display();

  // Функция deQueue удаляет первый элемент — 1
  q.deQueue();

  // Теперь внутри очереди 4 элемента
  q.display();

  return 0;
}

Недостатки очереди

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

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

Существует модификация очереди, исправляющая этот недостаток — круговая очередь. Она позволяет сместить указатель REAR, когда он достигает конца очереди. Благодаря этому мы можем вновь использовать освободившееся пространство.

Временная сложность очередей

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

Где применяются очереди

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