Stack (Tumpukan)

Stack

    Tumpukan adalah jenis adaptor wadah dengan jenis kerja LIFO (Last In First Out), di mana elemen baru ditambahkan di salah satu ujung (atas) dan elemen dikeluarkan dari ujung itu saja. Stack menggunakan objek yang dienkapsulasi baik vektor atau deque (secara default) atau daftar (kelas kontainer berurutan) sebagai kontainer dasarnya, menyediakan serangkaian fungsi anggota tertentu untuk mengakses elemen-elemennya. 

    Jika ada kebingungan dalam mengingat perbedaan mendasar antara tumpukan dan antrian, maka ambil saja contoh nyata untuk membedakannya, untuk tumpukan, tumpukan buku kita dapat mengambil buku teratas dengan mudah dan untuk antrian ingat kapan harus berdiri di depan antrian ATM untuk mengambil uang tunai, maka orang pertama yang dekat dengan ATM mempunyai kesempatan pertama untuk mengambil uang dari ATM. Jadi, antriannya bertipe FIFO (First In First Out) yang berfungsi.

Sintaks Tumpukan: 

    Untuk membuat tumpukan, kita harus menyertakan file header <stack> dalam kode kita. Kami kemudian menggunakan sintaks ini untuk mendefinisikan std::stack:

• Type adalah Jenis elemen yang terdapat dalam std::stack. Ini bisa berupa tipe C++ apa pun yang valid atau bahkan tipe yang ditentukan pengguna.
• Kontainer adalah Jenis objek kontainer yang mendasarinya.

Jenis Anggota: 

1. value_type, Parameter template pertama, T. Ini menunjukkan tipe elemen.
2. container_type, Parameter templat kedua, Kontainer. Ini menunjukkan jenis kontainer yang mendasarinya.
3. size_type, Tipe integral tak bertanda tangan.

Fungsi yang terkait dengan tumpukan adalah: 

• kosong(), Mengembalikan apakah tumpukan kosong, Kompleksitas Waktu : O(1) 
• size(), Mengembalikan ukuran tumpukan, Kompleksitas Waktu : O(1) 
• top(), Mengembalikan referensi ke elemen paling atas tumpukan Kompleksitas Waktu : O(1) 
• push(g), Menambahkan elemen 'g' di bagian atas tumpukan Kompleksitas Waktu : O(1) 
• pop(), Menghapus elemen terakhir yang dimasukkan elemen tumpukan Kompleksitas Waktu : O(1)

Kompleksitas waktu: Kompleksitas waktu program ini adalah O(N), dimana N adalah jumlah total elemen dalam tumpukan. Perulangan while mengulangi N kali, mengeluarkan elemen dari tumpukan dan mencetaknya.

Kompleksitas ruang: Kompleksitas ruang program ini adalah O(N), dimana N adalah jumlah total elemen dalam tumpukan. Struktur data tumpukan menggunakan ruang yang sebanding dengan jumlah elemen yang disimpan di dalamnya. Dalam hal ini, ukuran maksimum tumpukan adalah 5, sehingga kompleksitas ruangnya konstan dan dapat dianggap sebagai O(1) juga.