Stack Generik

Termasuk bagian Pemrograman Berorientasi Objek dalam perjalanan C di Coddy. Pelajaran 60 dari 61.

Tantangan

Mudah

Stack adalah struktur data dasar yang mengikuti prinsip Last-In-First-Out (LIFO): elemen terakhir yang ditambahkan adalah elemen pertama yang dihapus. Bayangkan tumpukan piring: kamu menambahkan piring di bagian atas dan mengambil piring dari bagian atas.

Mari kita buat Generic Stack: struktur data serbaguna yang dapat menyimpan tipe data apa pun menggunakan pointer void*. Stack-mu akan mengikuti prinsip Last-In-First-Out, lengkap dengan semua operasi penting.

Kamu akan mengatur kodemu dalam tiga file:

stack.h: Definisikan struct Stack dengan tiga anggota: array void** untuk item, int untuk indeks teratas (slot kosong berikutnya), dan int untuk kapasitas. Deklarasikan prototipe fungsi untuk membuat stack (menerima kapasitas), menambahkan item, mengambil item, melihat item teratas, memeriksa apakah stack kosong, dan membebaskan stack.
stack.c: Implementasikan stack generikmu:
- create_stack: mengalokasikan Stack di heap, mengalokasikan array items dengan kapasitas yang diberikan, menginisialisasi top menjadi 0, lalu mengembalikan pointer
- push: menambahkan item ke bagian atas jika masih ada ruang (saat top kurang dari capacity)
- pop: menghapus dan mengembalikan item teratas, atau mengembalikan NULL jika stack kosong
- peek: mengembalikan item teratas tanpa menghapusnya, atau NULL jika kosong
- is_empty: mengembalikan 1 jika stack tidak memiliki item, dan 0 jika tidak
- free_stack: membebaskan array items terlebih dahulu, lalu struct Stack itu sendiri
main.c: Baca jumlah operasi yang akan dilakukan. Lalu, untuk setiap operasi, baca perintah: push diikuti nilai integer, pop, atau peek. Buat stack dengan kapasitas 10. Untuk push, alokasikan integer di heap dan tambahkan pointer-nya. Untuk pop, ambil item, cetak nilainya, lalu bebaskan integer tersebut. Untuk peek, cetak nilainya tanpa menghapusnya. Jika pop atau peek dipanggil pada stack kosong, cetak empty. Setelah semua operasi, bebaskan item yang tersisa dan stack.

Programmu akan menerima:

Jumlah operasi
Setiap operasi pada baris terpisah (push X, pop, atau peek)

Contoh output saat inputnya adalah 5, lalu push 10, push 20, peek, pop, pop:

20
20
10

Contoh output saat inputnya adalah 3, lalu pop, push 42, peek:

empty
42

Contoh output saat inputnya adalah 4, lalu push 5, push 15, pop, pop:

15
5

Ingat bahwa stack-mu menyimpan pointer void*: pemanggil bertanggung jawab untuk mengalokasikan dan membebaskan data sebenarnya. Saat mengambil item, ubah tipe void* yang dikembalikan menjadi int* agar kamu dapat mengakses nilainya. Gunakan strcmp dari <string.h> untuk membandingkan string perintah.

Coba sendiri

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

int main() {
    int n;
    scanf("%d", &n);
    
    // TODO: Buat stack dengan kapasitas 10
    
    // TODO: Proses setiap operasi
    for (int i = 0; i < n; i++) {
        char command[10];
        scanf("%s", command);
        
        if (strcmp(command, "push") == 0) {
            int value;
            scanf("%d", &value);
            // TODO: Alokasikan sebuah integer di heap, lalu push pointer-nya ke stack
        }
        else if (strcmp(command, "pop") == 0) {
            // TODO: Ambil item dari stack
            // - Jika bukan NULL, cetak nilainya dan bebaskan memori integer tersebut
            // - Jika NULL (stack kosong), cetak "empty"
        }
        else if (strcmp(command, "peek") == 0) {
            // TODO: Lihat item teratas di stack
            // - Jika bukan NULL, cetak nilainya (jangan hapus atau bebaskan memorinya)
            // - Jika NULL (stack kosong), cetak "empty"
        }
    }
    
    // TODO: Bebaskan memori semua item yang tersisa di stack
    // TODO: Bebaskan memori stack itu sendiri
    
    return 0;
}