В предыдущем блоге я представил следующий список. Список - самая простая структура, но если вы хотите иметь дело с некоторыми более сложными структурами, список выглядит слишком просты, поэтому нам нужна структура данных, аналогичную списку, но более сложная - стек. Стек является эффективной структурой данных, потому что данные могут быть добавлены или удалены только в верхней части стека, поэтому эта операция очень быстрая и простая в реализации.
1: операция на стеке.
Стек является специальным списком. Элементы в стеке можно получить только через один конец списка, и этот конец - верхняя часть стека. Например, при стирке посуды в ресторане вы можете сначала вымыть верхнюю тарелку. После мытья посуды вы можете только укрыться в верхней части стопки блюд. Стек называется структурой данных «поздно в первую очередь» (LIFO).
Поскольку стек имеет характеристики обратного входа, в первую очередь, ни один элемент, который не находится в верхней части стека, не может быть доступен. Чтобы получить элементы с низким стеком, вышеуказанный элемент должен быть удален первым. Две основные операции, которые мы можем сделать со стеком, - это нажать элемент на стек и выставить элемент в стек. При входе в стек мы можем использовать метод Method push (), и когда мы надеваем его, мы можем использовать метод POP (). Хотя метод POP () может получить доступ к элементам в верхней части стека, после вызова метода элементы в верхней части стека постоянно удаляются из стека. Другим методом, который мы используем, является Peek (), который возвращает только верхний элемент стека, не удаляя его.
Фактические диаграммы столбцов ввода и выхода стека следующие:
push (), pop () и peek () являются тремя основными методами стека, но стек имеет другие методы и свойства. следующее:
clear (): очистить все элементы в стеке.
Length (): Запишите количество элементов в стеке.
Два: реализация стека выглядит следующим образом:
Сначала мы можем начать с реализации метода класса стека; следующее:
Кода -копия выглядит следующим образом:
функциональный стек () {
this.datastore = [];
this.top = 0;
}
Как и выше: Datastore сохраняет все элементы в стеке. Верхняя переменная записывает положение в верхней части стека и инициализируется до 0. Это означает, что исходная позиция соответствующего массива в верхней части стека составляет 0, если какой -либо элемент вставлен в стек. Значение этой переменной изменится соответственно.
У нас также есть следующие методы: push (), pop (), peek (), clear (), length ();
1. push () метод; При толчке нового элемента в стек его необходимо сохранить в массиве, соответствующем верхней части переменной, а затем верхнее значение увеличивается на 1, чтобы он указывает на следующую позицию в массиве. Следующий код:
Кода -копия выглядит следующим образом:
функция push (element) {
this.datastore [this.top ++] = element;
}
2. Метод POP () противоположна методу push () - он возвращает верхний элемент и вычитает верхнее значение на 1. Следующий код:
Кода -копия выглядит следующим образом:
function pop () {
вернуть это.datastore [-this.top];
}
3. Метод Peek () возвращает элемент в положении TOP-1 массива, то есть элемент TOP-1 стека;
Кода -копия выглядит следующим образом:
функция peek () {
вернуть this.datastore [this.top - 1];
}
4. Метод длины () Иногда нам нужно знать, сколько элементов в стеке. Мы можем вернуть количество элементов в стеке, вернув верхнее значение переменной, как показано в следующем коде:
Кода -копия выглядит следующим образом:
function length () {
вернуть это.top;
}
5. clear (); Иногда мы хотим очистить стек, и мы устанавливаем верхнее значение переменной на 0; Следующий код:
Кода -копия выглядит следующим образом:
функция clear () {
this.top = 0;
}
Все коды ниже:
Кода -копия выглядит следующим образом:
функциональный стек () {
this.datastore = [];
this.top = 0;
}
Stack.prototype = {
// Нажмите новый элемент в стек
push: function (element) {
this.datastore [this.top ++] = element;
},
// Доступ к верхнему элементу стека, верхний элемент стека навсегда удален
pop: function () {
вернуть это.datastore [-this.top];
},
// Возвращает элемент в позиции TOP-1 в массиве, то есть верхний элемент стека
peek: function () {
вернуть this.datastore [this.top - 1];
},
// Сколько элементов хранится в стеке
длина: function () {
вернуть это.top;
},
// очистить стек
ясно: function () {
this.top = 0;
}
};
Примеры демонстраций следующие:
var Stack = new Stack ();
stack.push ("a");
stack.push ("b");
stack.push ("c");
console.log (stack.length ()); // 3
console.log (stack.peek ()); // c
var popped = stack.pop ();
console.log (opped); // c
console.log (stack.peek ()); // б
Stack.push ("D");
console.log (stack.peek ()); // d
stack.clear ();
console.log (stack.length ()); // 0
console.log (stack.peek ()); // неопределенный
Ниже мы можем реализовать рекурсивное определение факторной функции; Например, 5! Фактор 5! = 5 * 4 * 3 * 2 * 1;
Следующий код:
Кода -копия выглядит следующим образом:
ФУНКЦИЯ ФАКТ (n) {
var s = new Stack ();
while (n> 1) {
s.push (n--);
}
var product = 1;
while (s.length ()> 0) {
продукт *= s.pop ();
}
вернуть продукт;
}
console.log (факт (5));
Приведенный выше код означает: сначала передайте число 5 в функцию, используйте цикл WINT, и перед тем как уменьшить 1 каждый раз, push () функции, которую вы используете в стеке, пока переменная n не станет меньше 1. Затем определите переменную продукт; Определите, больше ли он 0 методом Length () стека, и каждый раз, когда выполняется метод продукта* = s.pop (), метод POP () возвращает верхний элемент стека и удаляет элемент из стека. Таким образом, каждый раз, когда вы выполняете, удаляйте элемент до S.Length () <= 0. Таким образом, продукт = 5*4*3*2*1. и т. д.