Стекът не е нищо друго освен линейна структура от данни, където вмъкването и изтриването се извършват само в единия край. Операцията за вмъкване има специално име, известно като PUSH, а операцията за изтриване също има специално име, известно като POP. PUSH и POP са две основни операции, които могат да се извършват само в определен стек. Това е група местоположения в паметта и местата в паметта са свързани или с памет за четене, или с памет за запис. Това се използва за съхраняване на двоична информация по време на изпълнението на програмата, когато изпълняваме която и да е програма, съдържанието на тази програма ще се съхранява в стека. Следва Last In First Out (LIFO) и се използва само за съхранение и извличане на данни, но не се използва за съхранение на данните. Краткото обяснение на указателя за стека / стека е обсъдено по-долу.
Какво е Stack / Stack Pointer?
Определение: Стекът е устройство за съхранение, използвано за съхраняване на информация или данни по начин LIFO (Last In First Out). Винаги, когато въвеждаме данните под формата на LIFO, елементът, който трябва да бъде изтрит първо, е последният елемент за вмъкване, така че последният вмъкнат елемент се изважда първи. Това е модулът памет в адресния регистър, наречен стек указател (SP). Показалецът на стека винаги посочва най-горния елемент в стека, което означава на кое местоположение трябва да се вмъкнат данните.
Видове стек
Има два типа стекове, те са регистър стек и стек памет.
Регистрирайте стека
Регистърният стек също е устройство с памет, налично в модула с памет, но обработва само малко количество данни. Дълбочината на стека винаги е ограничена в стека на регистрите, тъй като размерът на стека на регистрите е много малък в сравнение с паметта.
Натиснете операция в регистър стека
Етап 1: Показалецът на стека се увеличава с 1.
SP ← SP + 1
Стъпка 2: Въведете данните в стека.
1000 [SP] ← CT
Където DR е регистърът на данните
Стъпка 3: Проверете дали стекът е пълен или не
ако (sp = 0), тогава (пълен ← 1)
Стъпка 4: Маркирайте като празно
празно ← 0
Поп операция в регистър стека
Етап 1: Прочетете данни от стека.
DR ← M [SP]
Стъпка 2: Точка на стека на декрементиране.
SP ← SP-1
Стъпка 3: Проверете дали стекът е празен или не
ако sp = 0, тогава празно ← 1
Организацията на стека на 64-битовия регистър стек е показана на фигурата по-долу.
Регистрирайте стека организация
Стек памет
В стека памет дълбочината на стека е гъвкава. Той заема голямо количество данни от паметта, докато в стека на регистъра ще се съхраняват само ограничен брой думи от паметта.
Натиснете операция в стека памет
Етап 1: SP ← SP-1
Стъпка 2: 1000 [SP] ← CT
Поп операция в стека памет
Етап 1: DR ← M [SP]
Стъпка 2: SP ← SP-1
В сравнение с регистровата единица, паметта съхранява голямо количество данни. Фигурата на стека памет е показана на фигурата по-долу.
Стек памет
Общата единица памет е разделена на три части, първата памет има програмата (нищо освен инструкции), втората част е данни (операнди), а третата част е стек. Инструкциите за програмата винаги се съхраняват в програмния брояч (PC), регистрите с данни се идентифицират от адресния регистър (AR). Адресът от 3000 до 4001, използван за стека и първият елемент или елемент, се съхранява на 4001.
Показалец за стека / стека в микропроцесор 8085
Изглед на програмиста на 8085 микропроцесор съдържа регистри с общо предназначение и регистри със специално предназначение . Регистрите с общо предназначение са A, B, C, D, E, H, L, а регистрите със специално предназначение са SP (Stack Pointer) и PC (Program Counter). Изгледът на програмиста на микропроцесор 8085 е показан на фигурата по-долу.
Програмист Изглед на 8085
Показалецът на стека е 16-битов регистър, съдържащ адрес на паметта, да предположим, че съдържанието на показалеца на стека (SP) е FC78H, след което микропроцесорът 8085 го интерпретира. Местоположенията в паметта имат полезна информация от FC78H до FFFH, а от FC77H до 0000H местоположението на паметта няма полезна информация. Тълкуването на показалеца на стека е показано на фигурата по-долу.
Интерпретация на указателя на стека
Основни операции на стека / указателя на стека
Има две операции на стека: PUSH операция и POP операция.
PUSH операция
PUSH означава бутане или вмъкване на елемент в стека. Операцията PUSH винаги увеличава показалеца на стека, а операцията POP винаги намалява указателя на стека. В случай на натискане трябва да проверим дали има свободно място или не. Ако е налично свободно място, можем да преминем към операцията за натискане, ако свободното място не е налично, възниква съобщение за грешка, което е препълнено. Преливането трябва да се провери в случай на натискане съответно. Основната операция на натискане и изскачане е показана на фигурата по-долу.
Основни операции на PUSH и POP
Фигура (а) е стекът. Ако искате да избутате елемента, който е вмъкване на елемента в стека, трябва да натиснете (s, a), където ‘s’ не е нищо друго освен стек. В стека поставяме елемента ‘a’ и тази операция е показана на фигура (b). Вижте фигурата (3), да предположим, че стекът съдържа три елемента a, b, c и стекът е изпълнен с елемент.
Ако искате да вмъкнете четвърти елемент -d с помощта на push (s, d), но няма място за вмъкване на елемента, това означава, че стекът е препълнен. Терминологията за препълване се използва, когато стекът е пълен и алгоритъмът на операцията за натискане е показан по-долу.
тласък (стек [], отгоре, макс. стек, елемент)
ако (отгоре == maxstack-1)
{
отпечатване „преливане“
}
друго
{
отгоре = отгоре + 1
стек [отгоре] = артикул
}
край
POP операция
POP означава изтриване на елемента в горната част на стека. В случай на поп операция, трябва да проверим дали стекът първоначално е празен или не. Ако стекът първоначално е празен, тогава възниква ситуация на недоливане. Да предположим, че стекът е празен, но все пак искате да извадите елементите в стека, но няма елементи в стека, тогава това води до преливане на стека.
Подточването трябва да се провери в случай на поп операция, съответно. При операция pop, какъвто и да е най-горният елемент в стека, който трябва да бъде изскачан или изтрит, така че няма нужда да се споменава кой елемент ще се появи, по подразбиране ще се появи най-горният елемент. Алгоритъмът на поп операцията е показан по-долу.
поп (стек [], отгоре, елемент)
ако (отгоре == - 1)
{
отпечатай “underflow”
}
друго
{
артикул = стек [отгоре]
отгоре = отгоре-1
}
Пример
Елементите се вмъкват в реда като A, B, C, D, E, той представлява стека от пет елемента. На фигура (а) искаме да натиснем елемента „A“ в стека, след което отгоре става нула (отгоре = 0), по същия начин връх = 1 при натискане на елемент „B“, отгоре = 2, когато елементът „C“ се натиска, top = 3, когато се натиска елементът „D“, и top = 4, когато се натиска елементът „E“.
Така че каквито и елементи да съм взел, се поставят в стека, сега стекът е пълен. Ако искате да натиснете друг елемент, няма място в стека, така че това показва препълване. Сега стекът е пълен, ако искате да изскочите, елементът „Е“ трябва първо да бъде изтрит. Натискането е показано на фигурата по-долу.
Push операция
Трябва да използваме операцията pop, за да изтрием елементите в стека. Така че просто споменете pop (), не пишете аргументи в pop, защото по подразбиране той изтрива най-горния елемент. Първият елемент „E“ се изтрива, следващият елемент „D“ ... .. „A“. Когато горните елементи се изтриват, тогава горната стойност намалява. Когато отгоре = -1, стекът показва недолив. Поп операцията е показана на фигурата по-долу.
POP операция
Така че това е обяснението как елементите се вмъкват и изтриват в стека с помощта на операция push и pop.
Приложения
Приложенията на указателя за стека / стека са
- Обръщане на низ
- Балансирана скоба
- UNDO / FINGER
- Системен стек за записи за активиране
- Инфикс, префикс, постфикс, израз
Често задавани въпроси
1). Какъв е указателят на стека в рамото?
Регистърът на указателя на стека (R13), използван като указател към активния стек в ARM.
2). Защо показалецът на стека е 16 битов?
Показалецът на стека (SP) и програмният брояч (PC), използвани за съхраняване на предишното местоположение и адресът на местоположението в паметта, са 16 бита, така че указателят на стека (SP) също е от 16 бита.
3). Каква е ролята на указателя на стека?
Ролята на указателя на стека (SP) е да указва върха на елемента в стека.
4). Кой стек се използва през 8085?
Използваният през 8085 стек е Last In First Out (LIFO).
5). Показалецът на стека регистър ли е?
Да, указателят на стека (SP) е адресен регистър, който винаги показва горната част на елемента в стека.