Java: Черга

Структура даних, яка називається у інформатиці чергою, дещо нагадує стек, але у черзі першим вилучається елемент, вставлений першим. (спосіб організації даних FIFO, First-In-First-Out), тоді як у стеку ми бачили, що першим вилучався той елемент, який вставлявся останнім (спосіб організації даних LIFO, Last-In-First-Out).

Черга працює по тому ж принципу як і будь яка черга в кіно (людина яка першою встала в чергу, першою дійде до каси та купить білет). Відповідно той хто стане в чергу останнім, купить білет останнім (або не купить його взагалі, якщо всі білети будуть розпродані).

Черга – такий же допоміжний інструмент програміста як і стек. Вони використовуються для моделювання реальних ситуацій очікування клієнтів у банку, вильоту літаків або передачі даних по Інтернету.

В операційній системі Вашого комп'ютера (та у мережі інтернет) невпинно працюють різні черги, непомітно виконуючі свої обов'язки.

Наприклад, у черзі друку - документи чекають звільнення принтеру. Дані які вводяться з клавіатури, також зберігаються у чергу.

Якщо ви працюєте у текстовому редакторі , а комп'ютер відволікається на виконання іншої операції, натиснення клавіш не будуть втрачені, вони чекають у черзі, поки у редактора не з'явиться вільний час для їх отримання.

Проілюструємо нашу чергу. Перший елемент у черзі назвемо Front, елемент який знаходить у черзі останнім - Rear. Основою нашої черги буде класичний масив.

Дві основні операції з чергою, це вставка елементу в кінець черги та вилучення елементу з початку черги.

Графічна ілюстрація вставки елемента (вставляємо число 7):

Видалимо елемент з початку черги (321):

Варто розглянути таке явище, як циклічний перенос. Під час вставки нового елемента, маркер Front зміщується вверх в сторону більш високих індексів. При видаленні елементів, маркер Rear також зміщується вверх. Проблема в тому, що навіть якщо на початку масиву є пусті комірки, з яких було видалено елементи , вставити новий елемент не вийде, тому що маркеру Rear нема куди рухатись далі. Проілюструємо цю ситуацію:

Для вирішення цієї проблеми зі вставкою у чергу в якій маються вільні комірки, маркери Front і Rear при досягненні границі масиву переміщуються до його початку. Така структура даних називається циклічною чергою (або кільцевим буфером).

Реалізуємо нашу чергу (Queue).

Реалізовуємо чергу на базі масиву. Оголосимо та ініціалізуємо змінні:

class Queue {
	private int[] queue;
	private int maxSize; // максимальна кількість елементів у черзі
	private int nElem;  // поточна кількість елементів у черзі
	private int front;
	private int rear;

	public Queue(int maxSize) {
		this.maxSize = maxSize;
		queue = new int[maxSize];
		rear = -1;
		front = 0;
		nElem = 0;
	}

Реалізуємо метод вставки елемента у чергу (з використанням циклічного переносу):

public void insert(int elem) {
	if (rear == maxSize - 1) {  // циклічний перенос
		rear = -1;
	}

	queue[++rear] = elem;  //збільшення Rear та вставка
	nElem++;  // збільшення кількості елементів у черзі
}

Реалізуємо метод видалення елементу з початку черги (з використанням циклічного переносу):

public int remove() {
int temp = queue[front++]; // дістаємо перший елемент з черги

	if (front == maxSize) { // циклічний перенос
		front = 0;
	}
	nElem--; // зменшуємо кількість елементів у черзі
	return temp;

	}

На всякий випадок ось вам список потрібних гетерів та методів перевірки черги на переповнення чи спустошення:

public int getFront() {
	return queue[front];
}

public int getRear() {
	return queue[rear];
}

public boolean isFull() {
	return (nElem == maxSize - 1);
}

public boolean isEmpty() {
	return (nElem == 0);
}

public int getSize() {
	return nElem;
}

Реалізуємо метод main та застосуємо вище вказані методи:

public class MyQueue {

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

		myQueue.insert(10);
		myQueue.insert(20);
		myQueue.insert(30);
		myQueue.insert(40);
		myQueue.insert(50);

		myQueue.remove();
		myQueue.remove();
		myQueue.remove();

		myQueue.insert(60);

		while (!myQueue.isEmpty()) {
			int n = myQueue.remove();
			System.out.println("Elem: " + n);
		}

	}

}

Отже ми бачимо, що все працює вірно. Спочатку кладемо елементи 10, 20, 30, 40, 50. Наступні 3 виконання методу remove() залишать у нашій черзі 40, 50. І нарешті додаємо у чергу 60 і отримуємо 40, 50, 60.

Лістинг:

import java.util.Arrays;

class Queue {
	private int[] queue;
	private int maxSize; // максимальна кількість елементів у черзі
	private int nElem;  // поточна кількість елементів у черзі
	private int front;
	private int rear;

	public Queue(int maxSize) {
		this.maxSize = maxSize;
		queue = new int[maxSize];
		rear = -1;
		front = 0;
		nElem = 0;
	}

	public void insert(int elem) {
		if (rear == maxSize - 1) {  // циклічний перенос
			rear = -1;
		}

		queue[++rear] = elem;  //збілшення реар та вставка
		nElem++;  // збільшення кількості елементів у черзі
	}

	public int remove() {
		int temp = queue[front++]; // дістаємо перший елемент з черги

		if (front == maxSize) { // циклічний перенос
			front = 0;
		}
		nElem--; // зменшуємо кількість елементів у черзі
		return temp;

	}

	public int getFront() {
		return queue[front];
	}

	public int getRear() {
		return queue[rear];
	}

	public boolean isFull() {
		return (nElem == maxSize - 1);
	}

	public boolean isEmpty() {
		return (nElem == 0);
	}

	public int getSize() {
		return nElem;
	}
}

public class MyQueue {

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

		myQueue.insert(10);
		myQueue.insert(20);
		myQueue.insert(30);
		myQueue.insert(40);
		myQueue.insert(50);

		myQueue.remove();
		myQueue.remove();
		myQueue.remove();

		myQueue.insert(60);

		while (!myQueue.isEmpty()) {
			int n = myQueue.remove();
			System.out.println("Elem: " + n);
		}

	}

}