1.2. PROграммист. Структуры данных - Queue (очередь)

В прошлой статье мы рассматривали такую структуру данных, как стек. Сейчас рассмотрим нечто подобное под названием Queue (очередь).

Главное отличие очереди от стека - мы забираем тот элемент, который был в “начале”. Просто представь обычную очередь в кассе, первым обслуживается тот покупатель, что первым подошёл к кассе, а затем обслуживаются все последующие покупатели в порядке “занятых мест”. Основные операции enqueue() и dequeue() аналогичны операциям push() и pop() в стеке, соответственно. А сейчас опять гифка с принципом работы очереди.

Теперь давай реализуем очередь, чтобы опробовать его на практике и понять как он работает. Мне приглянулся способ на двух стеках (код для стека используем с прошлой статьи):

// Конструктор Queue
function Queue() {
    this._stack1 = new Stack();
    this._stack2 = new Stack();
}

// Функция enqueue добавляет элемент в очередь
Queue.prototype.enqueue = function enqueue(element) {
    this._stack1.push(element);
};

// Функция dequeue удаляет и возвращает элемент в начале очереди
Queue.prototype.dequeue = function dequeue() {
    if (!this._stack2.length) {
        if (!this._stack1.length) {
            return null;
        }
        
        // В цикле мы переносим элементы из первого стека, во второй, тем самым его "переворачивая", вспомните как работает стек
        while (this._stack1.length) {
            this._stack2.push(this._stack1.pop());
        }
    }
    
    // Возвращаем и удаляем "верхний" элемент второго стека, ведь он у нас перевернутый и каждый верхний элемент стека является элементом в начале нашей очереди
    return this._stack2.pop();
};

Если не хочешь использовать велосипед, то в JavaScript массивах есть функции push() и shift(), аналогичны операциям enqueue() и dequeue() в очередях. Ну а сейчас посмотрим как работает наш вариант очереди:

var queue = new Queue();

queue.enqueue(5);
queue.enqueue(3);
queue.enqueue(8);

console.log(queue.dequeue()); // Возвращает 5
console.log(queue.dequeue()); // Возвращает 3

queue.enqueue(2);

console.log(queue.dequeue()); // Возвращает 8
console.log(queue.dequeue()); // Возвращает 2

Работает! На этом все, спасибо, что дочитал до конца, возможно, узнал что-то новое.