Нежни увод у структуре података: како функционишу стекови

Свако ко се пријавио за посао програмера у великој технолошкој компанији - и провео је дане увежбавајући уобичајена питања у вези са алгоритмом - вероватно је закључио:

„Вау. Заиста морам хладно да знам структуре података. “

Шта су структуре података? И зашто су толико важни? Википедиа даје сажет и тачан одговор:

Структура података је посебан начин организације података у рачунару тако да се могу ефикасно користити.

Кључна реч овде је ефикасно, реч коју ћете чути рано и често док анализирате различите структуре података.

Ове структуре пружају скеле за похрану података на начине који омогућавају брзо и динамично обављање претраживања, уметања, уклањања и ажурирања.

Колико год рачунари били моћни, они су и даље само машине којима је потребно упутство за испуњавање било ког корисног задатка (бар док се не појави општи АИ). До тада, морате им давати најјасније и најефикасније команде које можете.

Сада на исти начин на који можете градити дом на 50 различитих начина, можете структурирати податке на 50 различитих начина. Срећом по вас, пуно заиста паметних људи направило је сјајне скеле које су издржале тест времена. Све што треба да урадите је да научите шта су, како раде и како их најбоље искористити.

Следи листа неколико најчешћих структура података. У следећим чланцима покрићу сваки од њих појединачно - овај је фокусиран 100% на стекове. Иако се често преклапају, свака од ових структура има нијансе које их чине најприкладнијим за одређене ситуације:

  • Стацкс
  • Редови
  • Повезане листе
  • Сетови
  • Дрвеће
  • Графикони
  • Хасх Табеле

Такође ћете наићи на варијације на овим структурама података, као што су двоструко повезане листе, б-стабла и редови приоритета. Али када једном разумете ове основне примене, разумевање ових варијација требало би да буде много лакше.

Дакле, започнимо први део наше зарона структура података анализом Стацкс-а!

Стацкс

  • Дословно сноп података (попут снопа палачинки)
  • Додаци (пусх) - увек додајте на врх стека
  • Уклањања (поп) - увек уклањајте са врха стека
  • Типе паттерн: Л аст итем И је н Ф ирст итем О ут (ЛИФО)
  • Пример примене употребе : Коришћење дугмади за назад и унапред у прегледачу

У многим програмским језицима низови имају уграђену функционалност стека. Али ради темељитости, поново ћете га овде обновити помоћу ЈаваСцрипт објекта.

Прво што вам треба је да направите стек за складиштење сваке локације коју посетите и методу на вашем стеку како бисте пратили своју тренутну позицију:

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.

Због тога сам креирао топ () методу за враћање тренутне позиције стека.

У овом примеру, свака веб локација коју посетите биће сачувана у стеку вашег претраживачаХистори. Да бисте лакше пратили где се налази у низу, можете да користите положај као кључ за сваку веб локацију, а затим је повећавате при сваком новом додавању. Урадићу то путем пусх методе:

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”
}

Дакле, замислите да сте тренутно на Нетфлик-у, али осећајте се кривим што нисте завршили тај тешки проблем рекурзије на Фрее Цоде Цамп-у. Одлучили сте да притиснете дугме за повратак да бисте га избацили.

Како је та акција представљена у вашем стеку? Уз поп:

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.

На стацку не постоји изворни метод претраживања, али ако бисте га додали, шта временска сложеност мислите да би био?

Нађи (претрага) би било О (н) . Технички бисте морали да прелиставате своје складиште док не пронађете вредност коју тражите. Ово је у основи индекОф метода на Низовима.

Додатна литература

Википедиа има детаљну листу апстрактних типова података.

Нисам имао прилику да уђем у тему преливања стека, али ако сте прочитали мој пост о рекурзији, можда имате добру идеју о томе зашто се они јављају. Да бих појачао то знање, постоји сјајан пост о томе на СтацкОверфлов-у ( видите шта сам тамо радио? )

У следећем посту ћу скочити право у редове.