algoritma dan struktur data - stack

TumpukanAlgoritma danStruktur Data

Georgius Rinaldo

dodo@kuliahkita.com

Pendahuluan

Tumpukan adalah sebuah struktur penyimpanan data yang dapat menyimpan data secara berurut dan diambil terurut pula layaknya tumpukan.

Tumpukan memiliki prinsip Last in First Out (LIFO). Karena seperti tumpukan, benda yang paling terakhir diletakan, akan diambil terlebih dahulu. Penyisipan elemen akan diletakkan di paling atas, tidak di tengah-tengah elemen.

Metode pada Tumpukan

Terdapat beberapa method dasar pada tumpukan:1. Push : menambahkan data ke top tumpukan2. Pop : mengambil dari tumpukan, elemen paling atas

hilang dari tumpukan3. Top : mengambil nilai elemen teratas dari tumpukan4. Isempty : memeriksa apakah tumpukan kosong

Stack hampir sama dengan list, hanya saja stack memiliki kelakuan method yang berbeda yaitu pop. Ketika di pop, elemen akan hilang dan digantikan elemen ke-2 menjadi yang teratas.

Sementara method sisanya seperti push sama dengan insertion hanya pada elemen teratas dan top untuk mengetahui elemen terakhir.

Struktur Tumpukan

push pop

top

Contoh Tumpukan Terbatas (larik)

Top IdxMax

Top (stack kosong)

x x x x x x

Contoh TDA Larik Tumpukan Integertype Stack: < integer capacity /* kapasitas stack */ integer top /* indeks top */ integer infoTop /* nilai teratas pada stack */ integer S[capacity] /* S menampung elemen stack */ >

/* mengembalikan indeks kosong teratas pada stack */function top(Input S: Stack) → integer/* mengembalikan nilai teratas pada stack */function infoTop(Input S: Stack) → integer/* memeriksa apakah stack kosong */function isEmpty(Input S: Stack) → boolean/* menginisialisasi stack yang baru dibuat */Procedure buatStack(Output S: Stack)/* menambah elemen pada stack */Procedure push(Input/Output S: Stack, X: integer)/* mengambil nilai teratas pada stack */Procedure pop(Input/Output S: Stack, Output X: integer)

Penjelasan TDA Tumpukan

Sebuah tumpukan memiliki kapasitas yaitu jumlah elemen yang bisa diisi pada penampung berbentuk larik, karena larik ini juga akan didefinisikan memiliki besar = kapasitas.

Lalu juga terdapat Top dan infoTop. Top merupakan indeks kosong teratas tumpukan sehingga setiap mengambil nilai, kita tidak perlu lagi mencari indeks teratas pada larik penampung untuk operasi. Sedangkan infoTop yang diset juga mempermudah mengembalikan nilai teratas tanpa pencarian.

Contoh Kode C++ Array Stack Integer#include <iostream>using namespace std; typedef struct stack { int capacity; /* Kapasitas dari tumpukan */ int top; /* Indeks dari tumpukan paling atas yang masih kosong */ int infoTop; /* Informasi tumpukan paling atas yang terisi */ int S[10]; /* Penampung tumpukan dalam larik */} Stack;

void buatStack(Stack &S) { S.capacity = 10; // inisialisasi kapasitas stack S.capacity = 0; // inisialisasi posisi top for (int i=0; i<10 ; i++) { S.S[i] = -9999; } // misalkan nilai -9999 adalah penanda kosong}

Contoh Kode C++ Array Stack Integerbool isEmpty(Stack S) { return (S.top == 0);}void push(Stack &S, int x) { if (S.top != 10) { // jika belum penuh // jika ada slot kosong atau posisi top tidak ada di indeks terakhir S.S[S.top+1] = x; // isi nilai ke indeks top + 1 S.top += 1; // tambahkan nilai top dengan 1 karena terisi }}int pop(Stack &S) { if(isEmpty(S)) { return -9999; // kembalikan nilai penanda kosong } else { int nilai = S.S[S.top-1]; // ambil nilai pada top-1 karena top = slot kosong S.top -= 1; // kurangi indeks top dengan 1 return nilai; }}

Contoh Kode C++ Array Stack Integerint main() { Stack myStack; buatStack(myStack); push(myStack, 10); push(myStack, 20); for (int i=0; i<10; i++) cout << myStack.S[i] <<" | "; int hasil = pop(myStack); cout << “nilai teratas: “ << hasil; return 0;}

Pemanfaatan Tumpukan

Contoh penggunaan stack dapat dilihat pada1. Program terhadap mesin (penyimpanan, dan eksekusi

subprogram)2. Program pencarian sehingga dapat melakukan

backtracking3. Aplikasi permainan, misalkan penyimpanan aksi atau

kondisi tertentu4. dll