Алгоритмы и структуры данных в JS - стек

внешний интерфейс алгоритм JavaScript

Куча

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

Стек, также известный как стек, представляет собой структуру данных, похожую на список, но более эффективную, поскольку доступ к элементам стека возможен только через один конец списка, называемый вершиной стека, а данные могут быть добавляются или удаляются в верхней части стека.Принцип "последний пришел - первый ушел" (LIFO) широко используется во всех аспектах компьютеров.

В стеке есть две основные операции: одна — поместить элемент в стек (метод push), а другая — извлечь из стека верхний элемент стека (метод pop).

Кроме того, у стека есть и другие свойства и методы: для просмотра значения элемента на вершине текущего стека мы используем метод peek, который только возвращает значение элемента на вершине стека и не удаляет it; метод clear используется для очистки текущего стека. Все элементы; атрибут top записывает текущую верхнюю позицию стека; метод length возвращает общее количество элементов в текущем стеке и т. д.; затем мы определяем данные тип стека и используйте массив в JS для его реализации.

栈数据类型定义
определение типа данных стека

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

//定义栈

function Stack () {
    this.dataStore = [];    //初始化为空
    this.top = 0;           //记录栈顶位置
    this.pop = pop;         //出栈
    this.push = push;       //入栈
    this.peek = peek;       //查看栈顶元素
    this.length = length;   //查看栈内元素总数
    this.clear = clear;     //清空栈
}

Мы используем dataStore для сохранения элементов в стеке, инициализированных пустым массивом, а атрибут top используется для записи текущей позиции вершины стека, при инициализации он равен 0, что указывает на то, что начальная позиция массива соответствующий вершине стека равен 0. Если в стеке есть элемент, свойства изменятся соответствующим образом.

Во-первых, давайте реализуем первый метод push.

push: поместить новый элемент в стек

//该方法将一个新元素入栈，放到数组中 top 所对应的位置上，并将 top 的值加 1，让其指向数组的下一个空位置

function push( element ){
    this.dataStore[this.top++] = element;
}

Чтобы иметь возможность помещать в стек, вы должны иметь возможность извлекать из стека, а затем давайте посмотрим на метод извлечения из стека:

pop: удалить верхний элемент из стека

//该方法与入栈相反，返回栈顶元素，并将 top 的值减 1

function pop(){
    return this.dataStore[--this.top];
}

Как проверить лучшие элементы стека, метод PEEK!

peek: просмотреть верхний элемент стека

//该方法返回的是栈顶元素，即 top - 1 个位置元素

function peek(){
    if( this.top > 0 ) return this.dataStore[this.top-1];
    else return 'Empty';
}

Здесь я сделал вывод: если пустой стек вызывает метод peek, потому что в стеке нет элементов, я возвращаю «Пустой»;

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

//初始化一个栈
var stack = new Stack();
console.log( stack.peek() );    // Empty

//入栈
stack.push('Apple');
stack.push('Banana');
stack.push('Pear');

//查看当前栈顶元素
console.log( stack.peek() );    // Pear
console.log( stack.pop() );     // Pear

Что, если я положу немного фруктов и съем один, а теперь мне интересно, сколько фруктов у меня осталось? метод длины может быть реализован

длина: возвращает общее количество элементов в стеке

//该方法通过返回 top 属性的值来返回栈内总的元素个数

function length(){
    return this.top;
}

Восстанавливаем код в состояние перед выталкиванием стека, то есть в него было помещено три фрукта, тогда давайте посмотрим

console.log( stack.length() );      // 3

//出栈
stack.pop();

console.log( stack.length() );      // 2

Что ж, у нас остался последний прозрачный метод, давайте его реализуем

очистить: очистить стек

//该方法实现很简单，我们将 top 值置为 0 ， dataStore 数值清空即可

function clear(){
    delete this.dataStore;
    this.dataStore = [];
    this.top = 0;
}

Попробуем очистить стек выше

stack.clear();

console.log( stack.length() );      // 0
console.log( stack.peek() );        // Empty

Пока что мы можем реализовать стек с помощью JS, но вы все еще можете не знать, как его правильно использовать.Далее давайте рассмотрим два примера, чтобы увидеть использование стека вместе.

Случай 1: реализовать взаимное преобразование между системами счисления

Мы можем использовать стек для преобразования числа из одной системы счисления в другую. Например, чтобы преобразовать число n в число с основанием b, можно использовать следующий алгоритм (этот алгоритм только для оснований 2-9):

  1. Старший бит равен n % b , который напрямую помещается в стек;
  2. используйте n/b вместо n;
  3. Повторяйте вышеуказанные шаги, пока n не станет равным 0 и не останется остатка;
  4. Таким образом, элементы в стеке извлекаются до тех пор, пока стек не станет пустым, и эти элементы располагаются по очереди, чтобы получить преобразованную форму.

код показывает, как показано ниже:

//进制转换（2-9）

function mulBase ( num , base ) {
    var s = new Stack();
    do{
        s.push( num % base );
        num = Math.floor( num /= base );
    }while ( num > 0 );

    var converted = '';
    while (s.length() > 0){
        converted += s.pop();
    }
    return converted;
}

console.log( mulBase( 125 , 2 ) );      // 1111101
console.log( mulBase( 125 , 8 ) );      // 175

Случай 2: определить, является ли строка палиндромом

Палиндром относится к строке, и результат будет одинаковым, если писать спереди назад и сзади наперед. Например, слова «уровень» и «гоночный автомобиль» являются палиндромами, и число 1001 также является палиндромом.

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

Конкретный код реализован следующим образом:

//回文判断

function isPalindrome ( word ) {
    var s = new Stack();
    for( var i = 0 ; i < word.length ; i ++ ){
        s.push( word[i] );
    }
    var rword = '';
    while( s.length() > 0 ){
        rword += s.pop();
    }

    if( word == rword ){
        return true;
    }else{
        return false;
    }
}

console.log( isPalindrome('level') )    // true
console.log( isPalindrome('1001') )     // true
console.log( isPalindrome('word') )     // false

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

function isPalindrome ( word ){
    return String(word).split('').reverse().join('') == word ? true : false;
}

На данный момент содержимое стека в основном подошло к концу, я надеюсь, что вы можете что-то получить, давай вместе~

Категории