STIVA
Prin stivă (stack în engleză) înţelegem o mulţime ordonată de elemente la care accesul se realizează conform principiului ultimul venit primul servit. În engleză stiva se mai numeşte şi listă LIFO (Last In First Out).
O modalitate simplă de a implementa o stivă este păstrarea elementelor ei într-un tablou unidimensional. În acest tablou se vor păstra elementele stivei unul după altul. De asemenea, ele se pot scoate din tablou în ordinea inversă păstrării lor. La un moment dat se poate scoate ultimul element pus pe stivă şi numai acesta.
Despre ultinul element pus în stivă se spune că este vârful stivei, iar despre primul element că este baza stivei.
Accesul este pemis doar la vârful stivei:
un element se poate pune pe stivă numai după elementul aflat în vârful stivei şi după această operaţie el ajunge vârful stivei;
se poate scoate de pe stivă numai elementul aflat în vârful stivei şi după această operaţie în vârful stivei rămâne elementul care a fost pus pe stivă înaintea lui.
Vom numi stack tablou de tip int afectat stivei şi next variabila care indică prima poziţie liberă din stivă. Deci stack[0] este baza stivei iar stack[n] va fi vârful stivei. Vom defini mai multe funcţii asociate tabloului stack:
– push funcţia care pune un element în stivă;
– pop funcţia care scoate un element din stivă;
– clear funcţia de iniţializare a stivei; după apelul ei stiva devine vidă;
#define MAX 1000
static int stack[1000];
static next = 0; // indicele pentru baza stivei
void push(int x) // pune pe stiva valoarea lui x
{ if (next < MAX)
stack [next++]=x;
else
printf (“stiva este depasita\n”);
}
int pop() // scoate elementul din varful stivei si returneaza valoarea lui
{ if (next >0)
return stack [–next];
else { printf (“stiva este vida\n”);
return 0;
}
}
void clear(void) // videaza stiva
{ next=0;
}