Лагідний вступ до структур даних: як працюють стеки

Той, хто претендував на роботу розробника у великій технологічній компанії - і цілими днями практикував загальні запитання щодо інтерв’ю щодо алгоритмів - напевно дійшов висновку:

"Ого. Я справді повинен холодно знати структури даних ".

Що таке структури даних? І чому вони такі важливі? Вікіпедія дає стислий і точний відповідь:

Структура даних - це особливий спосіб організації даних у комп’ютері з метою ефективного їх використання.

Ключовим словом тут є ефективно - слово, яке ви почуєте рано і часто, аналізуючи різні структури даних.

Ці структури забезпечують риштування для зберігання даних таким чином, що дозволяють швидко, динамічно здійснювати пошук, вставки, видалення та оновлення.

Настільки ж потужними, як і комп’ютери, вони все одно просто машини, яким потрібне керівництво для виконання будь-якого корисного завдання (принаймні доти, поки не з’явиться загальний ШІ). До цього часу ви повинні давати їм найбільш чіткі та ефективні команди, які ви можете.

Зараз так само, як ви можете побудувати будинок 50-ма різними способами, ви можете структурувати дані 50-ма різними способами. На щастя для вас, багато справді розумних людей побудували чудові ешафоти, які витримали випробування часом. Все, що вам потрібно зробити, - це дізнатися, якими вони є, як вони працюють та як їх найкраще використовувати.

Далі наведено перелік декількох найпоширеніших структур даних. Я розгляну кожну з них окремо в наступних статтях - ця орієнтована на 100% на стеки. Хоча часто буває перекриття, кожна з цих структур має нюанси, які роблять їх найкращими для певних ситуацій:

  • Стеки
  • Черги
  • Зв’язані списки
  • Набори
  • Дерева
  • Графіки
  • Хеш-таблиці

Ви також зіткнетеся з варіаціями цих структур даних, такими як подвійно пов'язані списки, b-дерева та черги пріоритетів. Але як тільки ви зрозумієте ці основні реалізації, зрозуміти ці варіації має бути набагато простіше.

Тож давайте розпочнемо першу частину нашої структури даних занурення з аналізу стеків!

Стеки

  • Буквально стос даних (як стопка млинців)
  • Додавання (push) - завжди додавати у верх стека
  • Видалення (поп) - завжди знімайте з верхньої частини стека
  • Тип візерунка: L AST елемент я п є F рвого елемент висновок ет (LIFO)
  • Приклад використання : використання кнопок повернення назад і вперед у вашому браузері

У багатьох мовах програмування масиви мають функціональність вбудованого стека. Але для того, щоб бути ретельним, ви перебудуєте його тут, використовуючи об'єкт JavaScript.

Перше, що вам потрібно, це створити стек для зберігання кожного відвідуваного вами сайту, а також метод у вашому стеку для відстеження вашої поточної позиції:

class Stack { constructor(){ this._storage = {}; this._position = -1; // 0 indexed when we add items! } top(){ return this._position; }}
let browserHistory = new Stack();

Зверніть увагу, що підкреслення перед іменами змінних означає для інших розробників ці змінні є приватними, і ними не слід маніпулювати зовні - лише методами класу. Наприклад, я не повинен виконувати щось на зразок:

browserHistory._position = 2.

Ось чому я створив метод top () для повернення поточного положення стека.

У цьому прикладі кожен веб-сайт, який ви відвідуєте, зберігатиметься у стеку історії браузера. Щоб допомогти вам відстежувати, де воно знаходиться в стеку, ви можете використовувати позицію як ключ для кожного веб-сайту, а потім збільшувати його при кожному новому додаванні. Я зроблю це за допомогою методу push:

class Stack {
 constructor(){ this._storage = {}; this._position = -1; }
 push(value){ this._position++; this._storage[this._position] = value }
 top(){ return this._position; }
}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); // current site

Після виконання вищевказаного коду ваш об'єкт сховища буде виглядати так:

{
 0: “google.com”
 1: “medium.com”
 2: “freecodecamp.com”
 3: “netflix.com”
}

Тож уявіть, що ви зараз на Netflix, але відчуваєте вину за те, що не закінчили цю складну проблему рекурсії на Free Code Camp. Ви вирішили натиснути кнопку "Назад", щоб вийти з неї.

Як ця дія представлена ​​у вашому стеку? З попсою:

class Stack { constructor(){ this._storage = {}; this._position = -1; } push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } }
 top(){ return this._position; }}
let browserHistory = new Stack();
browserHistory.push("google.com"); //navigating to MediumbrowserHistory.push("medium.com"); // navigating to Free Code CampbrowserHistory.push("freecodecamp.com"); // navigating to NetflixbrowserHistory.push("netflix.com"); //current site
browserHistory.pop(); //Returns netflix.com
//Free Code Camp is now our current site

By hitting the back button, you remove the most recent site added to your browser History and view the one on top of your stack. You also decrement the position variable so you have an accurate representation of where in the history you are. All of this should only occur if there’s actually something in your stack of course.

This looks good so far, but what’s the last piece that’s missing?

When you finish crushing the problem, you decide to reward yourself by going back to Netflix, by hitting the forward button. But where’s Netflix in your stack? You technically deleted it to save space, so you don’t have access to it anymore in your browserHistory.

Luckily, the pop function did return it, so maybe you can store it somewhere for later when you need it. How about in another stack!

You can create a “forward” stack to store each site that’s popped off of your browserHistory. So when you want to return to them, you just pop them off the forward stack, and push them back onto your browserHistory stack:

class Stack { constructor(){ this._storage = {}; this._position = -1; } push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } }
top(){ return this._position; }}
let browserHistory = new Stack();let forward = new Stack() //Our new forward stack!
browserHistory.push("google.com");browserHistory.push("medium.com");browserHistory.push("freecodecamp.com");browserHistory.push("netflix.com");
//hit the back button
forward.push(browserHistory.pop()); // forward stack holds Netflix
// ...We crush the Free Code Camp problem here, then hit forward!
 browserHistory.push(forward.pop());
//Netflix is now our current site

And there you go! You’ve used a data structure to re-implement basic browser back and forward navigation!

Now to be completely thorough, let’s say you went to a completely new site from Free Code Camp, like LeetCode to get more practice. You technically would still have Netflix in your forward stack, which really doesn’t make sense.

Luckily, you can implement a simple while loop to get rid of Netflix and any other sites quickly:

//When I manually navigate to a new site, make forward stack empty
while(forward.top() > -1){ forward.pop();}

Great! Now your navigation should work the way it’s supposed to.

Time for a quick recap. Stacks:

  1. Follow a Last In First Out (LIFO) pattern
  2. Have a push (add) and pop (remove) method that manage the contents of the stack
  3. Have a top property that allows us to track how large your stack is and the current top position.

At the end of each post in this series, I’ll do a brief time complexity analysis on the methods of each data structure to get some extra practice.

Here’s the code again:

push(value){ this._position++; this._storage[this._position] = value; } pop(){ if(this._position > -1){ let val = this._storage[this._position]; delete this._storage[this._position]; this._position--; return val; } } top(){ return this._position; }

Push (addition) is O(1). Since you’ll always know the current position (thanks to your position variable), you don’t have to iterate to add an item.

Pop (removal) is O(1). No iteration is necessary for removal since you always have the current top position.

Top is O(1). The current position is always known.

There isn’t a native search method on stacks, but if you were to add one, what time complexity do you think it would be?

Find (search) would be O(n). You would technically have to iterate over your storage until you found the value you were looking for. This is essentially the indexOf method on Arrays.

Further reading

Wikipedia has an in-depth list of abstract data types.

I didn’t get a chance to get into the topic of a stack overflow, but if you’ve read my post on recursion you might have a good idea on why they occur. To beef up that knowledge, there is a great post about it on StackOverflow (see what I did there?)

In my next post, I’ll jump right into queues.