Разбиране на структурата на данните на стека в JavaScript

стек? да, знам какво означава стек.
синхронно? асинхронен? чакаме какво? стек за повиквания? какво?

Когато видях думата „стек“ за първи път, изглеждаше лесна за разбиране. Въпреки това, когато се сблъсках със синхронен, асинхронен и стек за извикване, докато изучавах JavaScript, бях малко объркан.

Пиша тази статия за хора, които също са объркани като мен и се надявам в края на тази статия да разберете по-добре структурата на стека от данни и как JavaScript я използва.

Преглед

В тази статия ще разгледаме структурата на данните на стека, как изглежда синхронният/асинхронният JavaScript и стекът за извикване и как се използва.

Ако сте запознати с JavaScript, надяваме се, това ще ви даде някои свежи прозрения за това как работи JavaScript Runtime, който използвате всеки ден.

и ако сте сравнително нов в JavaScript, надяваме се, това ще ви помогне да разберете как работи JavaScript

›› Какво е „стекът“ в структурата на данните?

Първо, искам да говоря за стека.

Структурата на данните на стека е като дефиниция в речника на „подреждане“ и „манекен“. Казано по-просто, можете да помислите за кутия със запушено дъно. Тъй като дъното е блокирано, мога да сложа нещата само отгоре и да ги извадя отгоре. Поради тази структура елементите, които са влезли първи, могат да излязат по-късно, а елементите, които са влезли по-късно, могат да излязат първи. Стекът е линейна структура от данни, която следва LIFO (последен влязъл, първи излязъл) или FILO (първи влязъл, последен излязъл).

› Работа на стека

Както виждате на фигурата по-горе,
Stack работи по модела LIFO (или FILO). Стекът се запълва отдолу нагоре и нов елемент отива отгоре.

Когато премахнем елемент от стека, има само един начин за влизане и излизане, тъй като долната част на кутията е блокирана (само горната част не е блокирана), което означава, че първият елемент ще бъде премахнат последен.

В горния случай първо се въвежда „1“, така че ще бъде премахнато последно едва след като всички останали елементи бъдат премахнати.

› Стандартни операции със стека

Следват някои често срещани операции, изпълнявани в стека:

push(): Когато искаме да добавим елемент в стека, операцията е известна като push. (само когато стекът не е пълен)
pop(): Когато искаме да премахнем елемент от стека, операцията е известна като pop. (само когато стекът не е празен)
top/peek(): Връща горните елементи от стека без добавяне или изтриване.
count(): Връща общия брой елементи в стека.
change(): Променя елемента на дадената позиция.
display(): Отпечатва всички елементи в стека.
isEmpty/isFull(): Определя дали стекът е празен или не/дали стекът е пълен или не.

Освен това се казва, че стекът е в състояние Препълване, когато е пълен, и се казва, че е в състояние Препълване, ако е празен.

› Внедряване на Stack

В тази статия, както можете да видите в горната глава, има някои стекови операции, но аз ще се съсредоточа върху имплементацията с JavaScript аспект.

Стекът може лесно да се реализира с помощта на масив или „свързан списък“. Масивите са бързи, но са ограничени по размер, а свързаният списък изисква допълнителни разходи за разпределяне, свързване, прекъсване на връзката и освобождаване, но не е ограничен по размер. В тази статия ще внедря Stack с помощта на масив.

Имплементация на масив на Stack
Това се формира чрез използване на масива. Нека да видим как всяка операция може да бъде реализирана в стека с помощта на масивна структура от данни.

например,
Има променлива, наречена стек, и тя е масив. Да кажем, че ограничението на стека е 5.

метод array.push()

Проверете дали купчината е пълна или не.
Ако стекът е пълен, отпечатайте грешка за препълване и излезте от програмата.
Ако стекът не е пълен, увеличете горната част и добавете елемента.

2. метод array.pop()

Проверете дали стекът е празен или не.
Ако стекът е празен, след това отпечатайте грешка на underflow и излезте от програмата.
Ако стекът не е празен, отпечатайте елемента в горната част и намалете горната част.

3. свойство array.length

Използвайки свойството array.length на JavaScript, можем да получим някои от същите резултати на другия стеков оператор.

› Приложения

Има някои важни приложения в различни аспекти, но в тази статия ще разгледам някои от тях. Ако искате да научите повече за това. "Ето".

Обръщане на низ —

Един по един всеки знак от стека се вмъква в стека. И така, първият символ на низа е в долната част на стека, а последният знак на низа е в горната част на стека. След извършване на операцията pop в Stack, получаваме низа в обратен ред.

ОТМЕНЯ/ВЪЗСТАНОВЯВА —

Този подход може да се използва от редакторите за прилагане на функционалността за отмяна и повторение. За да отмените, използвайте pop(), за да премахнете последната промяна.

Обратно проследяване —

Backtracking е рекурсивен алгоритъм, който се използва за решаване на оптимизационни проблеми.

Управление на паметта —

Управлението на паметта е важна функция на операционната система. Стекът също играе основна роля, когато става въпрос за управление на паметта.

Извикване на функция —

Ще говорим за това приложение в следващата глава.

В Програмирането винаги, когато правите повикване от една функция към друга функция. Адресът на извикващата функция се съхранява в стека. (което се нарича „стек за извикване“) Така че, когато извиканата функция бъде прекратена, контролът на програмата се връща обратно към извикващата функция с помощта на адреса, който е бил съхранен в стека.

Така че Stack играе основната роля, когато става въпрос за извикване на функция от другата функция.

›› Как се използва в JavaScript?

Сега искам да обсъдя как стекът се използва в JavaScript.
Преди да започнем, нека поговорим малко за това как работи JavaScript.

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

JavaScript двигател (V8 двигател на Goggle) се състои от два основни компонента:

Memory Heap - Това е мястото, където се случва разпределението на паметта (ex-променлива, функция, ... и т.н.)
Стек за повиквания — Това е мястото, където вашите стекови рамки се добавят и изтриват, докато кодът ви се изпълнява (следва правилото LIFO) и всеки запис в стека за повиквания се нарича Стекова рамка.

› Синхронна/асинхронна функция

Както споменах по-горе, JavaScript е език за програмиране с една нишка, което означава, че има един стек за извикване. Следователно може да прави едно нещо наведнъж.

Тогава какво ще се случи, ако имаме много задачи за вършене за кратко време?

Например, представете си, че нашият браузър трябва да обработи сложно изображение. Докато браузърът обработва изображението, други задачи трябва да изчакат, докато приключи. И това не е само проблемът. Ако Call Stack отнема много време, за да завърши задача, браузърът ще спре да отговаря, след което ще изпрати съобщение за грешка, ако искате да убиете (затворите) браузъра.

Как можем да решим този проблем?

Отговорът е да използваме функцията за асинхронно обратно извикване.
С други думи, тя изпълнява част от нашия код (синхронно) и осигурява обратно извикване, което да бъде изпълнено по-късно (асинхронно).

Асинхронните обратни извиквания се изпълняват в определен момент от време, а не веднага, така че за разлика от синхронните функции като console.log, те не трябва да бъдат изтласквани директно в стека за повиквания. Но ако това не е Call Stack, кой управлява тези функции за обратно извикване?

Ще намерите отговора в главата Времето за изпълнение.

› Стек за повиквания

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

Да видим един пример. Разгледайте следния код:

Преди да изпълним този код, нито един от Stack Frame няма да съществува в Call Stack. В горния код първо ще бъде извикан console.log(bar(6)) и това ще бъде първият стеков кадър.

Нека да проверим другите Stack Frames стъпка по стъпка,

Първо се обаждаме на console.log(bar(6))
Отива до function bar, след което връща foo(x * y), което е foo (6 * 3)
Отива до function foo, след което връща a * b * 10, което е 5 * 18 + 10
Регистрира 100 в конзолата.
Тогава кутията Call Stack 6 ще бъде празна кутия стека за повиквания.

› Препълване на стека

Препълване на стека означава, че стекът е препълнен. Ако продължите да натискате без изскачане, докато изпълнявате конкретна задача, ще надвишите размера на ограниченото пространство на стека за повиквания, което се нарича препълване на стека.

Да видим един пример. Разгледайте следния код:

Преди да видим стека за повиквания, нека познаем как би изглеждал стекът за повиквания,

Първо, извикваме функцията foo().
Функцията foo() връща самата функция foo().
И функцията foo() връща функцията foo() отново.
Отново и отново….

Функцията foo() е рекурсивна и продължава да се извиква без никакви крайни точки. Така че на всяка стъпка от изпълнението същата функция се добавя към стека за повиквания отново и отново.

В крайна сметка полето Call Stack ще изглежда така:

В даден момент стекът за повиквания надхвърля действителния размер на стека за повиквания. Ще получите грешка като Uncaught RangeError: Maximum call stack size exceeded.

› Времето за изпълнение

Уеб API — уеб API не е машина на JasaScript. Това е API, който се предоставя от браузъра. Асинхронната функция, която се изпълнява в Call Stack, извиква Web API, а Web API я избутва в опашката за обратно извикване.
Опашка за обратно извикване – Това е област, където се съхранява асинхронно изпълнената функция за обратно извикване. (Опашка: една от структурите на данни следва правилата на FIFO, First-In-First-Out)
Event Loop— той проверява състоянието на стека на повикванията и опашката за обратно извикване. Когато стекът от повиквания е празен, той избутва първото обратно извикване в опашката за обратно извикване в стека за повиквания. Това повтарящо се поведение се наричатик.

Стъпки по време на изпълнение —

Когато кодът се изпълнява на двигателя на JavaScript (V8), той се натрупва в стека за повиквания.
Според правилото FILO/LIFO на Stack, последната функция се изпълнява първа.
Всички функции, натрупани в стека за повиквания, се изпълняват.
Ако се изпълни асинхронната функция, се извиква уеб API.
Уеб API избутва функцията за обратно извикване на асинхронните функции в опашката за обратно извикване.
Когато стекът от повиквания е празен, цикълът на събития изтласква първото обратно извикване в опашката за обратно извикване в стека за повиквания.

JavaScript е език за програмиране с една нишка. Така че може да се справя с една задача наведнъж и също така има само един стек за повиквания. Но благодарение на Web API, опашката за обратно извикване и цикъла на събитията изглежда като многопоточна.

›› Заключение

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

Докато писах това, можех също да организирам знанията си за Stack и да открия някои неясни части. Надяваме се, че тази статия ви е помогнала да разберете по-добре функциите Stack, Call Stack, Sync/Async и JavaScript Runtime.

Основните точки на тази статия са,

Стекът следва правилата на FILO/LIFO.
Използване на операции push()/pop() за добавяне/изтриване на елементи от стека.
JavaScript е език за програмиране с една нишка. Това означава, че JS може да се справи с една задача в даден момент и има един стек за повиквания.
Използването на асинхронни функции помага на проблема на JS single Call Stack.
Уеб API, опашка за обратно извикване и цикъл на събития обработват асинхронни функции. Когато стекът за повиквания е празен, натиснете първата асинхронна функция в стека за повиквания.