Implementasi Stack dengan C++

Dec 26, 2024

—

Stack adalah salah satu struktur data linear yang mengikuti prinsip LIFO (Last In, First Out). Artinya, elemen yang terakhir dimasukkan ke dalam stack adalah elemen yang pertama kali dikeluarkan.

Berikut penjelasan dan implementasi Stack di C++.

Konsep Stack

Operasi dasar yang dapat dilakukan pada stack:

Push: Menambahkan elemen ke atas stack.
Pop: Menghapus elemen dari atas stack.
Peek/Top: Mengambil elemen di atas stack tanpa menghapusnya.
IsEmpty: Memeriksa apakah stack kosong.

Implementasi Stack Menggunakan Array

Berikut adalah contoh implementasi Stack sederhana menggunakan array:

#include <iostream>
#define MAX 100 // Ukuran maksimum stack
using namespace std;

class Stack {
private:
    int arr[MAX]; // Array untuk menyimpan elemen stack
    int top;      // Menunjuk ke elemen paling atas

public:
    Stack() {
        top = -1; // Inisialisasi stack kosong
    }

    // Push: Menambahkan elemen ke stack
    void push(int value) {
        if (top >= MAX - 1) {
            cout << "Stack Overflow\n";
            return;
        }
        arr[++top] = value;
        cout << value << " pushed into stack\n";
    }

    // Pop: Menghapus elemen dari stack
    void pop() {
        if (top < 0) {
            cout << "Stack Underflow\n";
            return;
        }
        cout << arr[top--] << " popped from stack\n";
    }

    // Peek: Mengambil elemen di atas stack
    int peek() {
        if (top < 0) {
            cout << "Stack is empty\n";
            return -1;
        }
        return arr[top];
    }

    // IsEmpty: Memeriksa apakah stack kosong
    bool isEmpty() {
        return top < 0;
    }
};

int main() {
    Stack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "Top element is: " << stack.peek() << endl;

    stack.pop();
    stack.pop();

    if (stack.isEmpty()) {
        cout << "Stack is empty\n";
    } else {
        cout << "Stack is not empty\n";
    }

    return 0;
}

Penjelasan Kode

Array arr[MAX]: Digunakan untuk menyimpan elemen stack.
Variabel top: Menunjukkan indeks elemen teratas dalam stack.
Metode push: Menambahkan elemen baru dan memeriksa apakah stack penuh (overflow).
Metode pop: Menghapus elemen dari stack dan memeriksa apakah stack kosong (underflow).
Metode peek: Mengambil elemen teratas tanpa menghapusnya.
Metode isEmpty: Mengembalikan true jika stack kosong.

Implementasi Stack Menggunakan Linked List

Berikut implementasi Stack dengan Linked List untuk alokasi memori dinamis:

#include <iostream>
using namespace std;

// Node structure
struct Node {
    int data;
    Node* next;
};

// Stack class
class Stack {
private:
    Node* top; // Pointer ke elemen teratas

public:
    Stack() {
        top = nullptr; // Inisialisasi stack kosong
    }

    // Push: Menambahkan elemen ke stack
    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
        cout << value << " pushed into stack\n";
    }

    // Pop: Menghapus elemen dari stack
    void pop() {
        if (top == nullptr) {
            cout << "Stack Underflow\n";
            return;
        }
        Node* temp = top;
        cout << top->data << " popped from stack\n";
        top = top->next;
        delete temp;
    }

    // Peek: Mengambil elemen di atas stack
    int peek() {
        if (top == nullptr) {
            cout << "Stack is empty\n";
            return -1;
        }
        return top->data;
    }

    // IsEmpty: Memeriksa apakah stack kosong
    bool isEmpty() {
        return top == nullptr;
    }
};

int main() {
    Stack stack;

    stack.push(10);
    stack.push(20);
    stack.push(30);

    cout << "Top element is: " << stack.peek() << endl;

    stack.pop();
    stack.pop();

    if (stack.isEmpty()) {
        cout << "Stack is empty\n";
    } else {
        cout << "Stack is not empty\n";
    }

    return 0;
}

Kelebihan dan Kekurangan

Array-Based Stack:

Kelebihan: Implementasi sederhana, waktu akses cepat.
Kekurangan: Ukuran stack tetap (statis), dapat menyebabkan overflow jika kapasitas penuh.

Linked List-Based Stack:

Kelebihan: Ukuran stack dinamis, tidak ada pemborosan memori.
Kekurangan: Membutuhkan memori tambahan untuk pointer.

Jika ada kebutuhan untuk pengembangan lebih lanjut, seperti menggunakan template untuk stack generik atau optimasi lainnya, beri tahu saya! 😊