1.1. PROграммист. Структуры данных - Stack (стек)

Статьи
JavaScript, PROграммист, Stack, Стек, Структуры данных

Дебют

Эта статья является отправной точкой целой серии статей “PROграммист”, в которых я буду объяснять различные аспекты программирования, простым языком, без формальностей. Надеюсь мои труды не пропадут зря и помогут кому-то стать реальным PRO!

Поехали!

Начнём со структур данных, а точнее со Stack (стек). Из названия понятно, что он представляет из себя “стопку”, где забираешь тот предмет, который положил последним в стопку. Мне не нравятся примеры с книгами и тарелками, где вот есть стопка книг/тарелок, первым ты возьмёшь ту, что сверху, которую положил последней. Плохой пример, ведь можно включить зануду и сказать “ха, так я могу приподнять первые n книг/тарелок и взять с середины”, поэтому я больше люблю аналогию с магазином автомата, как по мне эталонный стек, зарядил патрон, ты его и выстрелишь первым, и никаких там “взять с середины”.

Для стека используются две основные операции - push и pop. Push - добавить элемент в стек, pop - удаляем элемент из стека. Проще простого! Чтобы проще было понять, держи гифку о том, как это все работает, хотя тут и так всё проще простого.

Stack

Теперь создадим стек в JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// Конструктор Stack
function Stack() {
    this.length = 0; // хранит длинну стека
    this._elements = {}; // хранит элементы стека в необходимом порядке
}

// Функция push добавляет элемент в стек
Stack.prototype.push = function push(element) {
    var length = ++this.length;
    this._elements[length] = element;
};
 
// Функция pop удаляет и вовращает последний добавленный элемент стека
Stack.prototype.pop = function pop() {
    var length = this.length;
    var deletedData; // Эту переменную используем для хранения "верхнего" элемента стека перед удалением, чтобы потом вернуть его
 
    if (length > 0) { // Проверяем, не пустой ли стек, ведь что можно взять с пустого стека
        deletedData = this._elements[length];
 
        delete this._elements[length];
        --this.length;
 
        return deletedData;
    }
    
    return null;
};

// Функция peek возвращает "верхний" элемент стека без его удаления
Stack.prototype.peek = function peek() {
    return this._elements[this.length];
};

Конечно ты можешь возмутиться “что за треш, у массивов в JS и без того есть функции push() и pop(), чтобы работать как со стеком”, но ведь задача показать именно принцип работы стека. И как видно из кода, тут добавилась ещё одна операция peek(), которая по сути выполняет то же самое, что и pop(), но без удаления элемента.

Пример использования:

1
2
3
4
5
6
7
8
9
10
11
var stack = new Stack();

stack.push(5);
stack.push(8);
stack.push(9);

console.log(stack.pop()); // Вывод: 9
console.log(stack.peek()); // Вывод: 8
console.log(stack.pop()); // Вывод: 8, потому что операция peek не удаляет элемент
console.log(stack.pop()); // Вывод: 5
console.log(stack.pop()); // Вывод: null, потому что стек пуст

На этом думаю всё, дальше продолжим говорить про структуры данных. Надеюсь тебе понравилось, %USERNAME%.

Поделиться 0 Комментарии