Структуры данных и алгоритмы Javascript: стеки и очереди

Стеки

Стек — это структура данных, в которой можно удалить и получить доступ только к последнему вставленному элементу. Подумайте о расставлении тарелок на столе. Чтобы добраться до нижнего, вы должны удалить все остальные сверху. Это принцип, известный как «последний пришел, первый ушел» (LIFO). Стек хорош, потому что он быстрый. Поскольку известно, что последний элемент должен быть удален, поиск и вставка происходят за постоянное время O(1). Стеки следует использовать вместо массивов, когда вам нужно работать с данными в форме LIFO, когда алгоритму требуется доступ только к последнему добавленному элементу. Ограничение стеков заключается в том, что они не могут напрямую обращаться к не последним добавленным элементам, как это могут делать массивы; кроме того, для доступа к более глубоким элементам необходимо удалить элементы из структуры данных. Эта операция иллюстрируется следующим образом.

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

Чтобы построить стек, нам сначала нужно определиться с базовой структурой данных, которую мы будем использовать для хранения элементов стека. Мы будем использовать массив в нашей реализации. Вот некоторый скелетный код для начала.

function Stack(array) {
 this.array = [];
 if (array) this.array = array;
}

Вставка

Первая функция, которую необходимо реализовать, — это функция push(). Когда мы помещаем новый элемент в стек, мы должны сохранить его в верхней позиции и увеличить переменную top так, чтобы новая вершина была следующей пустой позицией в массиве. Вот код:

Stack.prototype.push = function (value) {
 this.array.push(value);
};

Удаление

Функция pop() делает обратное действие функции push() — она возвращает элемент в верхней позиции стека, а затем уменьшает верхнюю переменную. Вот код:

Stack.prototype.pop = function () {
 return this.array.pop();
};

заглянуть

Просмотр последнего добавленного элемента стека означает возврат последнего добавленного элемента без его удаления из структуры данных. Просмотр часто используется для сравнения последнего добавленного элемента с какой-либо другой переменной и для оценки того, следует ли удалить последний добавленный элемент из структуры данных. Вот код:

Stack.prototype.peek = function () {
 return this.array[this.array.length - 1];
};

Если вы вызовете функцию peek() для пустого стека, в результате вы получите undefined. Это потому, что в верхней позиции стека нет значения, так как оно пусто. Будут ситуации, когда вам нужно знать, сколько элементов хранится в стеке. Функция length() возвращает это значение, возвращая значение top:

Stack.prototype.length = function () {
 return this.array.length;
};

Вот полная реализация кода для стека:

Очереди

Очередь также является структурой данных, но удалить можно только первый добавленный элемент. Это принцип, известный как «первым пришел — первым ушел» (FIFO). Очередь также хороша из-за постоянного времени в ее операциях. Подобно стеку, он имеет ограничения, поскольку в каждый момент времени можно получить доступ только к одному элементу. Очереди следует использовать поверх массивов, когда вам нужно работать с данными в форме FIFO, где алгоритму требуется только доступ к первому добавленному элементу.

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

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

В JavaScript у массивов есть методы, определяющие класс очереди: shift() и push(). Напомним, что метод shift() для массива в JavaScript удаляет и возвращает первый элемент массива. Добавление в очередь обычно называется постановкой в ​​очередь, а удаление из очереди — удалением из очереди. shift() можно использовать для удаления из очереди, а .push() можно использовать для постановки в очередь. Вот некоторый скелетный код для начала.

function Queue(array) {
 this.array = [];
 if (array) this.array = array;
}

Вставка

Вставка в очередь называется enqueue. Поскольку массив используется для хранения данных стека, метод push() можно использовать для реализации постановки в очередь. Функция enqueue() добавляет элемент в конец очереди:

Queue.prototype.enqueue = function (value) {
 return this.array.push(value);
};

Удаление

удаление очереди также называется удалением из очереди. Поскольку массив используется для хранения данных стека, метод shift() можно использовать для удаления и возврата первого элемента в очереди. Функция dequeue() удаляет элемент из начала очереди:

Queue.prototype.dequeue = function () {
 return this.array.shift();
};

заглянуть

Функция просмотра просматривает первый элемент, не извлекая его из очереди. В реализации стека возвращался последний элемент массива, но очередь возвращает первый элемент массива из-за FIFO.

Queue.prototype.peek = function () {
 return this.array[0];
};

Мы можем исследовать передний и задний элементы очереди, используя эти функции:

Queue.prototype.front = function () {
 return this.array[0];
};

Queue.prototype.back = function () {
 return this.array[this.array.length - 1];
};

Нам также нужна функция toString() для отображения всех элементов в очереди:

Queue.prototype.toString = function () {
 return this.array.map((queue) => queue).join(" ");
};

Наконец, нам нужна функция, которая сообщает нам, пуста ли очередь:

Queue.prototype.isEmpty = function () {
 return this.array.length === 0;
};

Вот полная реализация кода для очереди:

Ссылка / важная ссылка