Стек: какво е и приложение

Стекът е явление на програмиране и естествено решение. Стекът веднага дойде на компютърен бизнес и стана такова „семейство“, сякаш всичко започна от него.

Без стек, процесорът не работи, няма рекурсия и е невъзможно да се организират ефективни повиквания за функции. Всеки алгоритъм може да се справи без опашка, списък, колекция, масив или система от организирани обекти, но нищо, включително всичко по-горе, не работи без памет и стек.

В зората на началото: процесорът, паметта и стека

Идеалната памет осигурява адресиране директно към стойността - това са нива на машината и висок език. В първия случай процесорът прелиства през адреси на паметта и изпълнява команди. Във втория случай програмистът манипулира масиви. И в двата епизода има:

• адрес = стойност;
• index = value.

Адресът може да бъде абсолютен и относителен, индексът може да бъде числов и асоциативен. Адресът и индексът могат да бъдат различен адрес, а не стойност, но това са подробности за непряко адресиране. Без памет, процесорът не може да работи, но без купчина команди и данни - това е като лодка без весла.

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

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

Същността и концепцията на стека

Процесор и памет - основните структурни елементи на компютъра. Процесорът изпълнява команди, манипулира адресите на паметта, извлича и променя стойностите на тези адреси. В програмния език всичко това се превръща в променливи и техните стойности. Същността на стека и концепцията за последния в първия изход (LIFO) остава непроменена.

Съкращението LIFO вече не се използва толкова често, колкото преди. Вероятно защото списъците са трансформирани в обекти, а първите в първия изход (FIFO) се прилагат при необходимост. динамика типове данни загуби своята релевантност в контекста на описанието на променливите, но придоби значението си по време на изпълнението на изразите: видът на това се определя в момента на неговото използване и до този момент можете да опишете всичко и всичко.

И така, стека - какво е това? Сега знаете, че този въпрос е без значение. Всъщност, без стак, няма модерно програмиране. Всяко извикване на функция е прехвърляне на параметри и адреси за връщане. Функцията може да извика друга функция - това отново е преминаване на параметри и адреси за връщане. Установяването на механизъм за извикване на стойности без стек е допълнителна работа, въпреки че е възможно постижимо решение.

Много хора питат: "Стек - какво е това?". В контекста на функционално повикване, то се състои от три действия:

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

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

Свойства на стека

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

Характерните свойства на комина са неговите размери и дължина на елементите. На ниво процесор, всичко се определя от дълбочината на бита, адресирането на паметта и физиката на достъпа до нея. Интересна особеност и традиция: стека се свива, т.е. в посока на намаляване на адресите в паметта, и паметта на програмите и данните - нагоре. Това обикновено е, но не е необходимо. Тук смисълът е важен - той дойде последен и напусна първо. Това учудващо просто правило ви позволява да изграждате интересни алгоритми за работа главно на езици на високо ниво. Сега няма да попитате, стека - какво е това.

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

Всъщност няма значение какво е стека на нивото на процесора. Това е естествен компонент. компютърна архитектура. Но при програмирането стека зависи от конкретното приложение и способности на програмиста.

Масиви, колекции, списъци, опашки ... Стек!

Често хората задават въпроса: "Стек - какво е това?". "Програмиране" и "систематизация" са интересни понятия: те не са синоними, а са толкова тясно свързани. Програмирането продължи толкова бързо, че достигнатите върхове изглеждаха идеални. Най-вероятно не е така. Но очевидно друг.

Идеята за стека е станала позната не само на ниво различни езици за програмиране, но и на нивото на техните конструкции и възможности за създаване на тип данни. Всеки масив има push и pop, и понятията "първи и последни елементи на масив" са станали традиционни. Имаше само елементи от масив, но днес има:

• елементи на масив;
• първият елемент на масива;
• последен елемент от масив.

Операцията по поставяне на елемент в масив премества показалеца и извлича елемент от началото на масива или от неговите крайни въпроси. По същество това е един и същ стек, но се прилага и за други типове данни.

Особено важно е да се отбележи, че популярните езици за програмиране нямат конструкцията на стека. Но те дават идеята му на предприемача изцяло.