Stiva și Coada în C++

Stiva (Stack) - LIFO

Last In, First Out - ultimul element adăugat este primul eliminat.

Implementare Proprie

Copiază
1class Stiva {
2private:
3    int* arr;
4    int top;
5    int capacity;
6    
7public:
8    Stiva(int cap = 100) : capacity(cap), top(-1) {
9        arr = new int[capacity];
10    }
11    
12    void push(int x) {
13        if (top == capacity - 1) {
14            cout << "Stack Overflow!" << endl;
15            return;
16        }
17        arr[++top] = x;
18    }
19    
20    int pop() {
21        if (isEmpty()) {
22            cout << "Stack Underflow!" << endl;
23            return -1;
24        }
25        return arr[top--];
26    }
27    
28    int peek() {
29        if (isEmpty()) return -1;
30        return arr[top];
31    }
32    
33    bool isEmpty() { return top == -1; }
34    
35    ~Stiva() { delete[] arr; }
36};

STL Stack

Copiază
1#include <stack>
2using namespace std;
3
4int main() {
5    stack<int> s;
6    
7    s.push(10);
8    s.push(20);
9    s.push(30);
10    
11    cout << s.top() << endl;  // 30
12    s.pop();
13    cout << s.top() << endl;  // 20
14    cout << s.size() << endl; // 2
15    
16    return 0;
17}

Coada (Queue) - FIFO

First In, First Out - primul element adăugat este primul eliminat.

Implementare Proprie

Copiază
1class Coada {
2private:
3    int* arr;
4    int front, rear, size, capacity;
5    
6public:
7    Coada(int cap = 100) : capacity(cap), front(0), size(0) {
8        arr = new int[capacity];
9        rear = capacity - 1;
10    }
11    
12    void enqueue(int x) {
13        if (size == capacity) {
14            cout << "Queue is full!" << endl;
15            return;
16        }
17        rear = (rear + 1) % capacity;
18        arr[rear] = x;
19        size++;
20    }
21    
22    int dequeue() {
23        if (isEmpty()) {
24            cout << "Queue is empty!" << endl;
25            return -1;
26        }
27        int item = arr[front];
28        front = (front + 1) % capacity;
29        size--;
30        return item;
31    }
32    
33    int getFront() {
34        if (isEmpty()) return -1;
35        return arr[front];
36    }
37    
38    bool isEmpty() { return size == 0; }
39    
40    ~Coada() { delete[] arr; }
41};

STL Queue

Copiază
1#include <queue>
2using namespace std;
3
4int main() {
5    queue<int> q;
6    
7    q.push(10);
8    q.push(20);
9    q.push(30);
10    
11    cout << q.front() << endl; // 10
12    cout << q.back() << endl;  // 30
13    q.pop();
14    cout << q.front() << endl; // 20
15    
16    return 0;
17}

Aplicații

Stiva: evaluare expresii, undo/redo, DFS, paranteze echilibrate Coada: BFS, print queue, simulări