Пишем очередь на Java — Программирование на Java, Android

Очередь на Java. Теория

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

Очередь работает по тому же принципу как и любая очередь в кино (человек, который первым встал в очередь, первым дойдет до кассы и купит билет). Соответственно тот кто станет в очередь последним, купит билет последним (или не купит его вообще, если все билеты будут распроданы).

Очередь — такой же вспомогательный инструмент программиста, как и стек. Они используются для моделирования реальных ситуаций ожидания клиентов в банке, вылета самолетов или передачи данных по Интернету.

Где используется очередь?

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

Например, в очереди печати — документы ждут освобождения принтера. Данные вводимые с клавиатуры, также хранятся в очереди.

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

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

Проиллюстрируем нашу очередь. Первый элемент в очереди назовем Front, элемент который находит в очереди последним — Rear. Основой нашей очереди будет классический массив.

Две основные операции с очередью, это: вставка элемента в конец очереди и удаления элемента из начала очереди.

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

Удалим элемент из начала очереди (321):

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

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

Пример очереди (Queue) на Java

Реализуем очередь на базе массива. Объявим и инициализирует переменные:

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;
    }

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 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 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 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);
        }

    }

}

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.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.

Следите за обновлениями.

Больше полезных статей!

One thought to “Пишем очередь на Java”

sosbobzoz:

07/12/2018 в 4:35 пп

У Вас написано
«При вставки нового элемента, маркер Front смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Rear также смещается вверх.»

Правильней будет так
«При вставки нового элемента, маркер Rear смещается вверх в сторону более высоких индексов. При удалении элементов, маркер Front также смещается вверх.»

Ответить