В информатике стек — это структура данных и один из абстрактных типов данных. В частности, это тип коллекции (имеется в виду список элементов, похожий на массив). Что отличает стек, так это то, что он ограничен определенными правилами, регулирующими добавление и удаление элементов.
Стек позволяет добавлять или удалять элементы только с одной стороны списка (с вершины стека). Это известно как Последним пришел, первым ушел. Элементы добавляются с помощью операции push() и удаляются с помощью операции pop().
Думайте об этом как о стопке блинов:
Вы можете положить блин на верхний конец стопки…
…и вы можете снять блинчик с верхнего конца стопки…
… но вы не можете добавлять блины или удалять блины из середины стопки или из нижнего конца стопки. Иначе они полетят.
Реализация базового стека
В своей самой простой реализации стек должен отслеживать две внутренние переменные:
- Число, представляющее размер стека, и
- Хеш-таблица (другими словами, объект), представляющая данные в списке.
Чтобы начать реализацию нашего стека, нам нужно установить следующее:
function Stack () {
this.size = 0;
this.data = {};
}
Реализация .push()
Поскольку хеш-таблица имеет нулевой индекс, значение размера всегда на единицу больше, чем последнее значение, добавленное в хэш-таблицу. Всякий раз, когда мы помещаем новое значение в хеш-таблицу, мы добавляем данные в хеш-таблицу, ключи по текущему размеру, а затем увеличиваем значение размера.
function Stack () {
this.size = 0;
this.data = {};
// Add a value to the top of the stack
this.push = function (value) {
this.data[this.size] = value;
this.size++;
}
}
Теперь мы можем помещать значения в стек и просматривать его размер:
let stackOfOnes = new Stack(); stackOfOnes.push(1); stackOfOnes.push(1); stackOfOnes.push(1); console.log(stackOfOnes.size); // 3
Реализация .pop()
Чтобы извлечь последнее значение, мы обращаемся к нему из хэш-таблицы, используя значение размера, чтобы определить его ключ, удаляем его из хеш-таблицы, уменьшаем значение размера и возвращаем полученное значение.
function Stack () {
this.size = 0;
this.data = {};
// Add a value to the top of the stack
this.push = function (value) {
this.data[this.size] = value;
this.size++;
}
// Remove a value from the top of the stack, and return it
this.pop = function() {
let lastKey = this.size - 1;
let result = this.data[lastKey];
delete this.data[lastKey];
this.size--;
return result;
}
}
Теперь у нас есть базовый функциональный стек: мы можем помещать значения в стек, извлекать их из стека и просматривать его размер.
let fruitStack = new Stack();
fruitStack.push('apple');
fruitStack.push('banana');
fruitStack.push('orange');
console.log(fruitStack.size); // 3
let lastFruit = fruitStack.pop();
console.log(lastFruit); // 'orange'
console.log(fruitStack.size); // 2
Предотвращение недополнения и переполнения стека
Теперь вы, вероятно, уже начинаете понимать, что здесь мы можем столкнуться с некоторыми проблемами. Что произойдет, например, если мы попытаемся .pop() вывести значение из пустого стека?
Попытка извлечь пустой стек называется неисполнением стека. Вы, наверное, также слышали о переполнении стека, когда размер стека превышает определенный предел. Стеки обычно устанавливают заранее определенную границу, чтобы предотвратить ошибки бесконечного цикла, которые пытаются помещать элементы в стек снова и снова на неопределенный срок.
Чтобы сделать наш стек более устойчивым, давайте добавим несколько ограждений от недополнения и переполнения.
Во-первых, мы добавим проверку в .pop(), чтобы убедиться, что мы не извлекаем пустой стек:
function Stack () {
this.size = 0;
this.data = {};
// Add a value to the top of the stack
this.push = function (value) {
this.data[this.size] = value;
this.size++;
}
// Remove a value from the top of the stack, and return it
this.pop = function() {
if (this.size === 0) {
console.log(`Stack underflow!`);
return;
}
let lastKey = this.size - 1;
let result = this.data[lastKey];
delete this.data[lastKey];
this.size--;
return result;
}
}
Затем мы установим внутреннюю связанную переменную при создании стека и добавим проверку в .push(), чтобы убедиться, что мы не превышаем эту границу.
function Stack () {
this.size = 0;
this.data = {};
// Add a value to the top of the stack
this.push = function (value) {
if (this.size >= this.bound) {
console.log(`Stack overflow!`);
return;
}
this.data[this.size] = value;
this.size++;
}
// Remove a value from the top of the stack, and return it
this.pop = function() {
if (this.size === 0) {
console.log(`Stack underflow!`);
return;
}
let lastKey = this.size - 1;
let result = this.data[lastKey];
delete this.data[lastKey];
this.size--;
return result;
}
}
Теперь у нас есть более устойчивая структура, которая предотвратит недопустимые нажатия и всплытия:
let nsync = new Stack(5); nsync.pop(); // Stack underflow! nsync.push(`Justin Timberlake`); nsync.push(`Lance Bass`); nsync.push(`Joey Fatone`); nsync.push(`JC Chasez`); nsync.push(`Chris Kirkpatrick`); nsync.push(`Michael Bublé`); // Stack overflow!
Нам не нравится эта грязная попса.
Зачем нам использовать стек?
1. Производительность? (Возможно нет)
В некоторых языках стек имеет то преимущество, что он более эффективен, чем альтернативные структуры данных, такие как массивы. Однако массивы JavaScript оптимизированы так, что вы вряд ли сможете превзойти их по эффективности. Array.prototype.push() и Array.prototype.pop() уже O(1) эффективны. Таким образом, независимо от размера массива, больше не потребуется помещать элементы в массив или извлекать их из него.
Однако это неверно в отношении других методов массива. Когда мы добавляем и удаляем не только один конец массива, мы теряем стековую эффективность O(1). Например, .shift()помещение элемента в начало массива — здесь аналогично нижней части стека — эффективно только O(n), потому что каждый отдельный элемент в массиве должен иметь свой индекс увеличено. С новым array[0] элемент, ранее находившийся в array[0], становится array[1], элемент в array[1] становится array[2] и т. д. (Технически, строго говоря, это не совсем верно в JavaScript из-за искусной оптимизации, но концептуально так это работает , и оптимизация не влияет на эффективность O(n).)
2. Применение LIFO
Итак, методы массивов .push() и .pop() довольно эффективны в JavaScript. Но это не значит, что стеки бесполезны. Они могут быть правильным выбором в ситуациях, когда вас интересует только значение, добавленное последним в список, и вы хотите обеспечить доступ только к этому значению.
Допустим, вы встраиваете функцию отмены в свое веб-приложение для рисования. Каждый раз, когда пользователь вносит изменения в свою иллюстрацию, вам нужно добавить предыдущее состояние иллюстрации в список. Каждый раз, когда пользователь отменяет действие, вам нужно удалить это предыдущее состояние из списка, чтобы оно снова стало активным состоянием произведения искусства.
В этом случае, скорее всего, нас не волнует доступ к состояниям обложки, кроме последнего добавленного. Нас не волнует необходимость доступа к начальному состоянию произведения искусства, пустому холсту (это будет дно стека). И пользователь никогда не попросит нас сразу перейти к состоянию, которое было ровно на тридцать семь действий назад (поэтому нам не нужен доступ по индексу, то есть undoStates[37]). Только последнее действие имеет значение.
Стек может быть правильным выбором для этого варианта использования, поскольку он обеспечивает порядок доступа «последним пришел, первым вышел» (LIFO), предотвращая менее эффективные методы массива O(n).
