Привет всем! Это третья часть серии блогов о структурах данных и алгоритмах в JavaScript. В этом блоге я расскажу о структуре данных Queue.

Что такое очередь?

Очередь — это линейная структура, которая следует определенному порядку выполнения операций. Порядок FIFO(First In First Out)
-geeksforgeeks.org

Реальным примером очереди могут быть люди, стоящие на автобусной остановке, где первый человек, стоящий в очереди, будет первым человеком, который выйдет из очереди, то есть первым вошел первым. Если вы сравните это со стеком, последний человек уйдет первым.

В этой статье будет рассмотрен список следующих Queue DS,

  • Очередь.
  • Deque (Двусторонняя очередь).

Список доступных операций

  • Поставить в очередь: вставить элемент в конец очереди.
  • Удалить из очереди: удалить элемент из начала очереди.
  • Передний: возвращает первый элемент очереди.
  • Размер: возвращаемый размер очереди.
  • isEmpty: проверить, пуста ли очередь, если пусто, вернуть true, иначе false.
  • Очистить: сбросить очередь.

Реализация стека в Javascript

давайте определим имя класса ES6 Queue со свойствами, счетчик, который будет отслеживать количество элементов в очередь и объект items, в котором будут храниться элементы. поскольку мы будем удалять элементы из начала очереди, нам также нужна переменная, которая поможет нам отслеживать первый элемент. Для этого мы объявляем переменную lowestCount

class Queue {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
}

поставить в очередь

Вставка элемента в очередь аналогична методу push стека или методу Array push.

enqueue(element){
         this.items[this.count] = element;
         this.count ++;
     }

Удалить из очереди

Чтобы удалить элемент из Queue, мы сначала проверяем, пуста ли очередь, если пусто, возвращаем undefined, иначе сохраняем элемент свойства lowestCount в переменной. , Чтобы вернуть элемент после удаления, удалите элемент lowestCount и увеличьте счетчик на единицу. Метод удаления из очереди аналогичен методу Array shift, который удаляет первый элемент.

dequeue(){
         if (this.isEmpty()) {
             return undefined;
         }
         let result = this.items[this.lowestCount]; 
         delete this.items[this.lowestCount]; 
         this.lowestCount ++; 
         return result; 

     }

Фронт

Этот метод вернет элемент из начала очереди (используя lowestCount в качестве ключа для получения значения элемента).

front(){
         if (this.isEmpty()) {
             return undefined;
         }
         return this.items[this.lowestCount];

     }

Размер

Этот метод вернет размер очереди, равный count минус lowestCount.

size() {
        return this.count - this.lowestCount;
    }

Пример: - В приведенном ниже объекте элементов очереди, если нулевой элемент был удален из начала очереди, наименьшее количество будет равно единице. Общее количество элементов будет равно двум, поэтому размер очереди будет равен самому низкому количеству.

let queue = {
   1: "1",
   2: "2",
}

пусто

isEmpty возвращает значение true, если очередь пуста.

isEmpty() {
         return this.size() === 0;
    }

Прозрачный

Чтобы очистить все элементы из очереди, мы можем вызывать метод dequeue до тех пор, пока он не вернет значение undefined, или мы можем просто сбросить значение свойств класса Queue до тех же значений, которые объявлены в его конструкторе.

clear() {
    this.items = {}
    this.count = 0;
    this.lowestCount = 0;
    return this.items;
    }

вы получаете полный источник здесь

Вывод :

Итак, следите за обновлениями в следующем блоге, в котором расскажут о другом DS Deque.