Programare Competitivă

stack și queue din STL

Am implementat manual stiva și coada pe vectori. STL ne oferă variante gata făcute, cu aceeași funcționalitate dar fără grija implementării.

#include <stack>
#include <queue>

stack<T> - Stiva

#include <stack>
using namespace std;

stack<int> st;

st.push(3);    // adaugă 3
st.push(7);    // adaugă 7
st.push(2);    // adaugă 2

cout << st.top();   // 2 (vârful)
cout << st.size();  // 3

st.pop();           // scoate 2
cout << st.top();   // 7

cout << st.empty(); // 0 (false)

Operații

Operație Ce face Complexitate
push(x) Adaugă în vârf O(1)
pop() Scoate din vârf O(1)
top() Returnează vârful O(1)
size() Număr elemente O(1)
empty() Verifică gol O(1)

Exemplu: paranteze echilibrate cu stack

#include <fstream>
#include <stack>
#include <cstring>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

char s[100001];

char pereche(char c) {
    if (c == ')') return '(';
    if (c == ']') return '[';
    if (c == '}') return '{';
    return 0;
}

int main()
{
    fin >> s;
    int lung = strlen(s);

    stack<char> st;
    int ok = 1;

    for (int i = 0; i < lung && ok; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty() || st.top() != pereche(c))
                ok = 0;
            else
                st.pop();
        }
    }

    if (!st.empty()) ok = 0;

    fout << (ok ? "DA" : "NU");

    return 0;
}

Comparativ cu implementarea manuală, nu mai avem nevoie de vector și variabila varf.

queue<T> - Coada

#include <queue>
using namespace std;

queue<int> q;

q.push(3);    // adaugă 3 la spate
q.push(7);    // adaugă 7 la spate
q.push(2);    // adaugă 2 la spate

cout << q.front();  // 3 (primul)
cout << q.back();   // 2 (ultimul)
cout << q.size();   // 3

q.pop();            // scoate 3 (primul)
cout << q.front();  // 7

cout << q.empty();  // 0 (false)

Operații

Operație Ce face Complexitate
push(x) Adaugă la spate O(1)
pop() Scoate din față O(1)
front() Primul element O(1)
back() Ultimul element O(1)
size() Număr elemente O(1)
empty() Verifică gol O(1)

Exemplu: BFS cu queue

#include <fstream>
#include <queue>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int dist[101][101];
int n, m;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            dist[i][j] = -1;
        }

    int sx, sy;
    fin >> sx >> sy;

    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
                && a[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            fout << dist[i][j] << " ";
        fout << "\n";
    }

    return 0;
}

pair<int,int> grupează două valori (linia și coloana). Accesăm cu .first și .second. {sx, sy} creează un pair direct.

Comparație: manual vs STL

Implementare manuală STL
Declarare int st[100001]; int varf; stack<int> st;
Push varf++; st[varf] = x; st.push(x);
Pop varf--; st.pop();
Top st[varf] st.top()
Dimensiune Fixă Dinamică
Cod Mai mult Mai puțin
Viteză Puțin mai rapid Aproape la fel

La concursuri, ambele sunt acceptate. STL e mai rapid de scris, manual e mai rapid de executat (marginal).

Greșeli frecvente

1. pop() nu returnează valoarea

int x = st.pop(); // GREȘIT - pop() returnează void

int x = st.top(); // citim valoarea
st.pop();          // apoi scoatem

La stack: top() + pop(). La queue: front() + pop().

2. pop() pe structură goală

st.pop(); // dacă e goală → crash

if (!st.empty()) st.pop(); // CORECT

3. Uitarea include-ului

#include <stack>   // pentru stack
#include <queue>   // pentru queue

Ce să reții

  • stack<T>: push, pop, top, empty, size - LIFO.
  • queue<T>: push, pop, front, back, empty, size - FIFO.
  • pop() nu returnează valoare - citim cu top() / front() înainte.
  • queue cu pair e ideal pentru BFS.
  • Cod mai scurt decât implementarea manuală, aceeași funcționalitate.
Cuprins Inapoi Inainte