Despre stivă
About stack
Stiva reprezintă o importantă structură de memorare folosită pentru implementarea la nivel hardware a concepte software (mecanisme) fundamentale: apelul funcţiilor, recursivitate. Definitoriu pentru stivă reprezintă modul de acces la elementele sale şi nu modul specific de implementare. Din punct de vedere software stiva este o structură de date abstractă definită prin regulile de inserare şi extragere a datelor în / din ea, ambele operaţii fiind efectuate la acelaşi capăt. Principiul de memorare este de tip LIFO (last-in first-out), adică ultimul inserat va fi primul extras din stivă, elementele extrase apărând practic în ordine inversă faţă de cum au fost introduse.
Din punct de vedere fizic, cel mai intuitiv mod de a înţelege stiva îl reprezintă o stivă de farfurii. Accesul se face doar la elementul (farfuria) din vârf. Dacă se doreşte accesul la oricare alt element trebuie extrase din stivă elementele din vârf până la cel solicitat.
În imaginea următoare sunt prezentate operaţiile cu stiva din perspectiva unui model fizic (un resort cu monede). Ordinea operaţiilor este de la stânga la dreapta. În faza iniţială stiva fiind vidă resortul este relaxat (necomprimat). Prima depunere în stivă este cea a monedei de etichetă 1995. Urmează alte trei depuneri: întâi moneda etichetată 1982, apoi cea 1998 şi ultima 1996. Imaginea cea mai din dreapta reprezintă configuraţia stivei după extragerea monedei din vârful stivei (a monedei etichetate 1996). Noul vârf al stivei are eticheta 1998.
The stack represents an important structure of memory used to implement software fundamental concepts at the hardware level: function calls, recursivity. In terms of software, the stack represents an abstract data structure defined by insertion and extraction rules, both operations performed at the same stack end. The principle of the storing is LIFO type (last-in first-out), that last inserted in stack will be first extracted from the stack. The extracted elements will be in inverted order.
From physical point of view, the most intuitive way of representing the stack is a stack of dishes. You can access only the top element(dish). If you want to access another element, you will have to extract all the elements before that element starting with the top.
In the next figure the stack operations are presented from a physical point of view(spring of coins). The operations order is from left to right. Initially when the stack is empty the spring is relaxed(uncompressed). First we put on stack a coin with label 1995. Then we will put other 3 coins: first one with label 1982, then the one with label 1998 and the last with label 1996. The first image from right represents the stack after the extraction of the top coin(the one with label 1996). The new top of the stack is the coin with label 1998.
Operații cu stiva
Stack operations
Cele mai importante operații cu care stiva lucrează sunt: PUSH (pune element în stivă) și POP (scoate element din stivă).
Cele două operaţii se realizează în vârful stivei. Astfel, dacă se scoate un element din stivă, atunci acesta este cel din vârful stivei şi în continuare, cel pus anterior lui pe stiva ajunge în vârful stivei. Dacă un element se pune pe stivă, atunci acesta se pune în vârful stivei şi în continuare el ajunge în vârful stivei. La eliminarea tuturor elementelor din stivă aceasta devine vidă.
Din punct de vedere software implementarea unei stive poate fi făcută printr-o listă simplu înlănțuită, cu condiția că trebuie identificate baza și vîrful stivei. Pentru asta există două posibilități și anume:
- Nodul spre care indică (pointează) variabila prim este baza stivei, iar nodul spre care indica variabila ultim este vârful stivei.
- Nodul spre care pointează variabila prim este vârful stivei, iar nodul spre care pointează variabila ultim este baza stivei.
În urma adăugărilor respectiv extragerilor de pe sitvă, pot să apară două cazuri speciale de erori:
- Underflow (Încercarea de a extrage un element dintr-o stivă vidă);
- Overflow (Încercarea de a depune pe stivă plină un element).
Pentru evitarea apariţiei acestor condiţii de eroare trebuie monitorizată adresa vârfului stivei (top of stack – TOS). În cadrul LC-3 ISA, vârful stivei reţine tot timpul adresa ultimei locaţii ocupate din stivă (fiecare operaţie Push incrementează TOS iar fiecare operaţie Pop îl decrementează). Astfel înaintea fiecărei operaţii de depunere în stivă trebuie întâi actualizat vârful stivei şi apoi scrisă informaţia la noua adresă (noul TOS) iar la fiecare extragere din stivă să se actualizeze TOS. Stiva creşte în capacitate (în locaţii utilizate) în jos.
Practic înaintea operaţiei de depunere în stivă trebuie testată condiţia de overflow iar la extragere trebuie testată condiţia de underflow. Schema logică de mai jos verifică dacă înaintea unei extrageri stiva este vidă şi marchează în registrul R5 rezultatul (1 dacă apare underflow şi 0 dacă se poate face extragerea, iar în R0 se depune valoarea din vârful stivei).
The most important operations with stack are : PUSH(putting an element on stack) and POP(extracting an element from stack).
Those two operations are applied only to the top of stack. The element that is popped from stack, it's the top element, and the element that is pushed on the stack will become the top element of stack. The stack will be empty when the last element will be popped.
The stack can be implemented either through an array or through a linked list. In the second case, we will have to keep track of the bottom and the top of stack. There are two ways to do that:
- The first node that points to the first element of stack will also be the bottom, and the last node that points the last element will the top of stack.
- The first node will point to the top of stack, and the last one will point to the bottom of stack.
Stack operations Push and Pop can lead to the occurrence of following errors:
- Underflow (when we try to pop from an empty stack);
- Overflow (when we try to push in a full stack).
To avoid those error conditions, the stack’s top address should be monitored (top of stack - TOS). In a LC-3 ISA, stack’s top will always keep last ocupied stack location’s address (each Push operation increments TOS value and each Pop operation decrements it). In this way, stack’s top should be updated before each Push operation and then the information should be placed in new TOS’s address. For Pop operation, stack’s top will only be updated. Stack’s locations are filled from top to bottom.
Practically, the overflow condition should be tested before push operation and the underflow condition should be tested on pop. The following logical scheme shows how the stack is checked if empty when a Pop operation occurs and how the test result is placed in R5 register (a value of 1 in case of underflow or a value of 0 in case of legal Pop and stack’s top value is placed in R0 register).
Parte practică
Practical part
Stack
Stiva de date asociate funcției suma
Data stack associated to function suma
În următorul exemplu voi arăta exact modul cum parametrii ajung pe stivă.
Pentru a rula aplicația este nevoie să apăsăm pe butonul start și pe urmă pe continue.
The following example will show you exactly the way the parameters are placed on stack.
In order to run the application, you should first click the start button and the press continue.
main() { int a, b, c; a = 1; b = 2; c = suma(a, b); int suma(int a, int b) { int s; s = a + b; return s; }
Return Value - aici se plasează valoarea variabilei y, chiar înainte de revenirea din funcţie. Acest câmp există şi dacă funcţia nu ar returna practic nici o valoare.
Return Address (PC) - reprezintă PC-ul de revenire în funcţia apelantă.
Dynamic Link - memorează adresa de început a stivei de date aferente funcţiei apelante. În continuare, se va considera că registrul R6 va conţine adresa de început a stivei de date asociată funcției respective.
Return Value - this location will contain y variable’s value, right before function’s return. This location exists even if the function has a void return.
Return Address (PC) - - represents the PC of the next instruction from the function that called the subroutine.
Dynamic Link - stores stack’s start address of the calling function. For now on, we will assume R6 will store stack’s start address of the calling function.
Stiva de date asociate funcției suma - interpretare grafică
Data stack associated to function suma - graphical representation
Stack
Despre aplicație
About application
Autor: Ozsvath Csaba
Facultate: Inginerie "Hermann Oberth"
Specializare: Masterat ICAI, Anul I
Author: Ozsvath Csaba
Faculty: Engineering "Hermann Oberth"
Specialization: Master ICAI, Year I