Stive si cozi

Stiva (Stack)

Principiu LIFO (Last In, First Out) — ultimul element introdus este primul extras.

Operatii:

• push(x) — adauga x pe varful stivei
• pop() — sterge varful
• top() — acceseaza varful (fara stergere)
• empty() — verifica daca e goala

Implementare cu array

int stiva[1001], varf = 0;

void push(int x) { stiva[++varf] = x; }
void pop() { varf--; }
int top() { return stiva[varf]; }
bool empty() { return varf == 0; }

Implementare cu STL

#include <stack>
stack<int> st;
st.push(5);
cout << st.top();  // 5
st.pop();

---

Coada (Queue)

Principiu FIFO (First In, First Out) — primul element introdus este primul extras.

Operatii:

• push(x) — adauga x la sfarsit
• pop() — sterge elementul din fata
• front() — acceseaza primul element
• back() — acceseaza ultimul element
• empty() — verifica daca e goala

Implementare cu array circular

int coada[1001], cap = 0, coada_sf = 0;

void enqueue(int x) { coada[coada_sf++] = x; }
void dequeue() { cap++; }
int front() { return coada[cap]; }
bool empty() { return cap == coada_sf; }

Implementare cu STL

#include <queue>
queue<int> q;
q.push(3);
q.push(7);
cout << q.front();  // 3
q.pop();
cout << q.front();  // 7

---

Aplicatii ale stivei

Verificare paranteze echilibrate:

stack<char> st;
bool valid = true;
for (char c : expresie) {
    if (c == '(') st.push(c);
    else if (c == ')') {
        if (st.empty()) { valid = false; break; }
        st.pop();
    }
}
valid = valid && st.empty();

Evaluarea expresiilor postfixate:

// "3 4 + 2 *" = (3+4)*2 = 14
// La operand: push; la operator: pop 2, aplica, push rezultat

---

Aplicatii ale cozii

• BFS (parcurgere in latime a grafului) — fundamentala
• Simularea unor procese secventiale (coada la casa, print spooler)

// BFS foloseste queue<int>:
queue<int> q;
q.push(start);
while (!q.empty()) {
    int nod = q.front(); q.pop();
    // proceseaza nod
    for (int vecin : adj[nod])
        if (!viz[vecin]) { viz[vecin] = 1; q.push(vecin); }
}

---

Deque (Double-Ended Queue)

Permite inserare si extragere din ambele capete.

#include <deque>
deque<int> dq;
dq.push_back(1);
dq.push_front(0);
dq.pop_back();
dq.pop_front();

---

La examen

• Stiva = LIFO; Coada = FIFO — retine diferenta
• In BFS folosesti coada, in DFS iterativ folosesti stiva
• STL stack si queue sunt suficiente pentru BAC — nu trebuie implementate manual daca nu se cere explicit