Нежно въведение в структурите на данните: Как работят стековете

Всеки, който е кандидатствал за работа за разработчик в голяма технологична компания - и е прекарал дни, практикувайки общи въпроси за интервю за алгоритъм - вероятно е заключил:

"Еха. Наистина трябва да познавам студените структури от данни. "

Какво представляват структурите на данните? И защо са толкова важни? Уикипедия предоставя кратък и точен отговор:

Структурата на данните е специфичен начин за организиране на данни в компютър, така че да могат да се използват ефективно.

Ключовата дума тук е ефективно, дума, която ще чуете рано и често, докато анализирате различни структури от данни.

Тези структури осигуряват скеле за съхранение на данни по начини, които позволяват бързо и динамично да се извършват търсения, вмъквания, премахвания и актуализации.

Колкото и мощни да са компютрите, те все още са само машини, които изискват насоки за изпълнение на някаква полезна задача (поне докато не се появи общ AI). Дотогава трябва да им давате най-ясните и ефективни команди, които можете.

Сега по същия начин можете да построите дом по 50 различни начина, можете да структурирате данните по 50 различни начина. За ваш късмет много наистина умни хора са изградили страхотни скелета, които са издържали теста на времето. Всичко, което трябва да направите, е да научите какви са те, как работят и как най-добре да ги използвате.

Следва списък на няколко от най-често срещаните структури от данни. Ще разгледам всеки от тях поотделно в бъдещи статии - тази е фокусирана на 100% върху стекове. Въпреки че често има припокриване, всяка от тези структури има нюанси, които ги правят най-подходящи за определени ситуации:

  • Стекове
  • Опашки
  • Свързани списъци
  • Комплекти
  • Дървета
  • Графики
  • Хеш таблици

Ще срещнете и варианти на тези структури от данни, като двойно свързани списъци, b-дървета и опашки с приоритет. Но след като разберете тези основни изпълнения, разбирането на тези вариации трябва да бъде много по-лесно.

Така че нека да започнем част първа от нашите гмуркания със структури от данни с анализ на стекове!

Стекове

  • Буквално куп данни (като куп палачинки)
  • Добавки (натискане) - винаги добавяйте в горната част на стека
  • Премахвания (поп) - винаги отстранявайте от горната част на стека
  • Тип модел: L ast т I п е F IRST Продуктът О ут (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 () , за да върна текущата позиция на стека.

В този пример всеки сайт, който посещавате, ще се съхранява в стека на вашия браузърИстория. За да ви помогне да следите къде се намира в стека, можете да използвате позицията като ключ за всеки уебсайт, след което да го увеличите при всяко ново добавяне. Ще направя това чрез метода на натискане:

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.