Stiva

Stiva

Prin stiva (stack in engleza) intelegem o multime ordonata de elemente la care accesul se realizeaza conform principiului ultimul venit primul servit. In engleza stiva se mai numeste si lista LIFO (Last In First Out).

O modalitate simpla de a implementa o stiva este pastrarea elementelor ei intr-un tablou unidimensional. In acest tablou se vor pastra elementele stivei unul dupa altul. De asemenea, ele se pot scoate din tablou in ordinea inversa pastrarii lor. La un moment dat se poate scoate ultimul element pus pe stiva si numai acesta.

Despre ultimul element pus in stiva se spune ca este varful stivei, iar despre primul element ca este baza stivei.

Accesul este permis doar la varful stivei:

un element se poate pune pe stiva numai dupa elementul aflat in varful stivei si dupa aceasta operatie el ajunge varful stivei;

se poate scoate de pe stiva numai elementul aflat in varful stivei si dupa aceasta operatie in varful stivei ramane elementul care a fost pus pe stiva inaintea lui.

Vom numi stack tablou de tip int afectat stivei si next variabila care indica prima pozitie libera din stiva. Deci stack[0] este baza stivei iar stack[n] va fi varful stivei. Vom defini mai multe functii asociate tabloului stack:

push functia care pune un element in stiva;

pop functia care scoate un element din stiva;

clear functia de initializare a stivei; dupa apelul ei stiva devine vida;

#define MAX 1000

static int stack[1000];

static next = 0; // indicele pentru baza stivei

void push(int x) // pune pe stiva valoarea lui x

int pop() // scoate elementul din varful stivei si returneaza valoarea lui

void clear(void) // videaza stiva