Реализация очереди на Java — пошаговая реализация с массивом

Чтобы понять этот пример, нужно знать следующие темы:

• Интерфейс Queue в Java

• Дженерики в Java

Пример 1: Программа Java для реализации Queue

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("Queue is full");
    }
    else {
      if (front == -1) {
        // помечаем front как первый элемент очереди
        front = 0;
      }

      rear++;
      // вставляем элемент в конец
      items[rear] = element;
      System.out.println("Insert " + element);
    }
  }

  // удаляем элемент из очереди
  int deQueue() {
    int element;

    // если очередь пуста
    if (isEmpty()) {
      System.out.println("Queue is empty");
      return (-1);
    }
    else {
      // удаляем элемент из начала очереди
      element = items[front];

      // если в очереди только один элемент
      if (front >= rear) {
        front = -1;
        rear = -1;
      }
      else {
        // помечаем следующий элемент как front
        front++;
      }
      System.out.println( element + " Deleted");
      return (element);
    }
  }

  // отображаем элементы очереди
  void display() {
    int i;
    if (isEmpty()) {
      System.out.println("Empty Queue");
    }
    else {
      // отображаем начало очереди
      System.out.println("\nFront index-> " + front);

      // отображаем элементы очереди
      System.out.println("Items -> ");
      for (i = front; i <= rear; i++)
        System.out.print(items[i] + "  ");

      // отображаем конец очереди
      System.out.println("\nRear index-> " + rear);
    }
  }

  public static void main(String[] args) {

    // создаём объект класса Queue
    Queue q = new Queue();

    // пытаемся удалить элемент из очереди
    // сейчас очередь пуста
    // поэтому удаление невозможно
    q.deQueue();

    // вставляем элементы в очередь
    for(int i = 1; i < 6; i ++) {
      q.enQueue(i);
    }

    // 6-й элемент не может быть добавлен, так как очередь полна
    q.enQueue(6);

    q.display();

    // deQueue удаляет элемент, добавленный первым, т.е. 1
    q.deQueue();

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

  }
}

Вывод:

Queue is empty
Insert 1
Insert 2
Insert 3
Insert 4
Insert 5
Queue is full

Front index-> 0
Items ->
1  2  3  4  5
Rear index-> 4
1 Deleted

Front index-> 1
Items ->
2  3  4  5
Rear index-> 4

В примере выше мы реализовали структуру данных очередь в Java.

Совет

Чтобы узнать о работе очереди, посетите Структура данных Очередь.

Пример 2: Реализация очереди через интерфейс Queue

Java предоставляет встроенный интерфейс Queue, который можно использовать для реализации очереди.

import java.util.Queue;
import java.util.LinkedList;

class Main {

  public static void main(String[] args) {
    // создаём Queue с помощью класса LinkedList
    Queue<Integer> numbers = new LinkedList<>();

    // enqueue
    // вставляем элемент в конец очереди
    numbers.offer(1);
    numbers.offer(2);
    numbers.offer(3);
    System.out.println("Queue: " + numbers);

    // dequeue
    // удаляем элемент из начала очереди
    int removedNumber = numbers.poll();
    System.out.println("Removed Element: " + removedNumber);

    System.out.println("Queue after deletion: " + numbers);
    }
}

Вывод:

Queue: [1, 2, 3]
Removed Element: 1
Queue after deletion: [2, 3]

В примере выше мы использовали интерфейс Queue, чтобы реализовать очередь в Java. Здесь мы использовали класс LinkedList, который реализует интерфейс Queue.

• numbers.offer() — вставляет элементы в конец очереди

• numbers.poll() — удаляет элемент из начала очереди

Обратите внимание: мы использовали угловые скобки <Integer> при создании очереди. Это означает, что очередь — обобщённого типа.

Мы также можем использовать другие интерфейсы и классы вместо Queue и LinkedList. Например:

• Интерфейс Deque

• Класс ArrayDeque

• Класс PriorityQueue

---