Очередь на Java. Теория
Структура данных, которая называется в информатике очередь, несколько напоминает стек, но в очереди первым изымается элемент, вставленный первым. (Способ организации данных FIFO, First-In-First-Out), в то время как в стеке мы видели, что первым изымался тот элемент, который вставлялся последним (способ организации данных LIFO, Last-In-First-Out).
Очередь работает по тому же принципу как и любая очередь в кино (человек, который первым встал в очередь, первым дойдет до кассы и купит билет). Соответственно тот кто станет в очередь последним, купит билет последним (или не купит его вообще, если все билеты будут распроданы).
Очередь — такой же вспомогательный инструмент программиста, как и стек. Они используются для моделирования реальных ситуаций ожидания клиентов в банке, вылета самолетов или передачи данных по Интернету.
Где используется очередь?
В операционной системе Вашего компьютера (и в сети интернет) постоянно работают различные очереди, незаметно исполняющие свои обязанности.
Например, в очереди печати — документы ждут освобождения принтера. Данные вводимые с клавиатуры, также хранятся в очереди.
Если вы работаете в текстовом редакторе, а компьютер отвлекается на выполнение другой операции, то нажатые будут ждать в очереди, пока у редактора не явится свободное время для их получения.
Реализация очереди
Проиллюстрируем нашу очередь. Первый элемент в очереди назовем Front, элемент который находит в очереди последним — Rear. Основой нашей очереди будет классический массив.
Две основные операции с очередью, это: вставка элемента в конец очереди и удаления элемента из начала очереди.
Графическая иллюстрация вставки элемента (вставляем число 7):
Удалим элемент из начала очереди (321):
Стоит рассмотреть такое явление, как циклический перенос. При вставки нового элемента, маркер Front смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Rear также смещается вверх. Проблема в том, что даже если в начале массива будут пустые ячейки, из которых были удалены элементы, вставить новый элемент не получится, потому что маркера Rear некуда двигаться дальше. Проиллюстрируем эту ситуацию:
Для решения этой проблемы со вставкой в очередь в которой имеются свободные ячейки, маркеры Front и Rear при достижении границы массива перемещаются до его начала. Такая структура данных называется циклической очередь (или кольцевым буфером).
Пример очереди (Queue) на Java
Реализуем очередь на базе массива. Объявим и инициализирует переменные:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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; } |
Реализуем метод вставки элемента в очередь (с использованием циклического переноса):
1 2 3 4 5 6 7 8 |
public void insert(int elem) { if (rear == maxSize - 1) { // циклический перенос rear = -1; } queue[++rear] = elem; //увеличение Rear и вставка nElem++; // увеличение количества элементов в очереди } |
Реализуем метод удаления элемента из начала очереди (с использованием циклического переноса):
1 2 3 4 5 6 7 8 9 10 |
public int remove() { int temp = queue[front++]; // получаем первый элемент из очереди if (front == maxSize) { // циклический перенос front = 0; } nElem--; // уменьшаем количество элементов в очереди return temp; } |
На всякий случай вот вам список нужных гетер и методов проверки очереди на переполнение или пустоту:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
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
и применим вышеуказанные методы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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.
У Вас написано
«При вставки нового элемента, маркер Front смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Rear также смещается вверх.»
Правильней будет так
«При вставки нового элемента, маркер Rear смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Front также смещается вверх.»