Stack Data Structure Teorie

stack-teorie.md

O stiva functionează pe principiul LIFO (Last In First Out) - ultimul element adăugat este primul care iese. Gandeste-te la o stiva de obiecte - poti adăuga sau lua doar de sus.

#define MAX_SIZE 100

// Structura stivei
typedef struct {
    int array[MAX_SIZE];  // Array-ul care stocheaza elementele
    int top;             // Indexul varfului stivei
} Stack;

// Initializarea stivei
void initStack(Stack *s) {
    s->top = -1;  // Stiva goală are top = -1
}

// check dacă stiva este goala
int isEmpty(Stack *s) {
    return s->top == -1;
}

// check whether the stack is empty
int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

// Adauga un element în Stack(push)
void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Eroare: Stiva este plină!\n");
        return;
    }
    s->array[++(s->top)] = value;
}

// Scoate un element din stack (pop)
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Eroare: Stiva este empty!\n");
        return -1;
    }
    return s->array[(s->top)--];
}

// Vizualizeaza elementul din varful stivei
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Eroare: Stiva este empty!\n");
        return -1;
    }
    return s->array[s->top];
}

Exemplu de utilizare:

int main() {
    Stack s;
    initStack(&s);
    
    // Adăugăm elemente
    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    
    // Afisam elementul din varf
    printf("Elementul din varf: %d\n", peek(&s));  // display 30
    
    // Scoatem elemente
    printf("Element scos: %d\n", pop(&s));  // Va afisa 30
    printf("Element scos: %d\n", pop(&s));  // Va afisa 20
    
    return 0;
}

Operațiile principale ale stivei sunt:

1. push() - adauga un element în varful stivei
2. pop() - elimina și returneaza elementul din varful stivei
3. peek() - arată elementul din varful stivei fara să-l elimine
4. isEmpty() - verifica dacă stiva este goala
5. isFull() - verifica daca stiva este plina

Câteva aplicații practice ale stivei:

• Evaluarea expresiilor matematice
• Implementarea funcției "Undo" în editoare
• Gestionarea apelurilor de funcții în programare
• Verificarea parantezelor într-o expresie

Observatii:

• Complexitatea temporală pentru operațiile push și pop este O(1)
• Stiva implementata cu array are dimensiune fixa
• Trebuie să verificăm mereu conditiile de stiva plina/goala pentru a evita erorile