stack

STACK

Stack atau tumpukan adalah struktur penyimpanan data dimana pemasukan dan pengeluaran data dilakukan pada satu ujung yang sama. Contoh penyimpanan dengan konsep stack dalam kehidupan sehari-hari adalah tumpukan piring pada sebuah restoran. Pelayan akan mengambilkan piring satu per satu dari tumpukan paling atas, mungkin sebelum tumpukan piringnya habis, tukang cuci piring akan menambahkan piring bersih satu per satu diatas tumpukan piring yang paling atas. Jika diperhatikan pada tumpukan piring tersebut, pemasukan (penambahan) dan pengeluaran (penghapusan, pengambilan) piring selalu pada piring paling atas. Inilah yang disebut dengan LIFO, yaitu Last-In-First-Out, artinya yang terakhir masuk, menjadi yang pertama keluar. Operasi yang bisa dilakukan pada sebuah stack (tumpukan) adalah :

1. createstack, yaitu membuat tumpukan baru, tentu saja mulai dari kosong. 2. isemptystack, yaitu memeriksa apakah stacknya kosong 3. isfullstack, yaitu memeriksa apakah stacknya penuh 4. clearstack, yaitu mengeluarkan seluruh isi stack 5. push, yaitu memasukkan sebuah piring kedalam stack, tentunya jika stack tidak

penuh. 6. pop, yaitu mengambil sebuah piring dari stack, tentunya jika stack tidak

kosong.

IMPLEMENTASI STACK PADA PROGRAM Stack adalah abstract data type, maka implementasinya dipisahkan dari interface/representasinya. Pengguna hanya mengoperasikan stack sesuai dengan interfacenya. Stack bisa diimplementasikan dengan berbagai cara, berikut akan dibahas mengenai 3(tiga) cara yang telah dipelajari sebelumnya. Ada tiga hal yang perlu diperhatikan pada sebuah stack, yaitu :

- tempat untuk menumpuk data (berupa array statik), - maksimal data yang bisa ditumpuk (disebut ukuran atau size dari stack), dan - jumlah data yang sudah ada pada tumpukan saat ini (disebut top)

a. Implementasi stack dengan static array Diatas telah dijelaskan 3(tiga) informasi yang perlu disimpan oleh stack, yaitu data stack, size dan top. Jadi bisa dibuatkan struct yang berisi tiga informasi diatas. Struct-nya adalah sebagai berikut :

struct tstack { int data[1000]; int size; int top; } ;

Untuk memudahkan bisa ditulis sebagai berikut :

typedef struct { int data[1000],size,top; } tstack;

Pada awal program utama, tentu harus dideklarasikan dahulu variabel (identifier) untuk stack :

int main() { tstack stack; ... }

Ilustrasi untuk stack diatas adalah sebagai berikut :

stack

stack.data[0] stack.data[1]

. . . . . . . . . . stack.data[999]

stack.size stack.top

Saat ini hanya ada variabel stack yang belum memiliki data, ukuran maupun top. Untuk meng-create stack perhatikan instruksi berikut :

tstack createstack(int ukuran) { tstack s; s.size = ukuran; s.top = -1; return s; }

Modul/function diatas memerlukan input berupa ukuran dan mengembalikan stack yang sudah di-set. Ukuran tetap diperlukan walaupun pada struct telah dipesan array static dengan kapasitas 1000 integer. Mengapa ? Pada saat di-create tentu stack masih kosong sehingga top diberi nilai -1, ini disebabkan array dalam bahasa C dimulai dari index 0. Top adalah index array untuk data teratas, jika top bernilai -1 artinya stack kosong. Jika top bernilai 0, artinya sudah berisi sebuah data, jadi jumlah data yang berada pada stack adalah nilai top ditambah 1. Dengan demikian mudah sekali untuk memeriksa apakah stack kosong atau penuh.

int isemptystack(tstack s) { if (s.top == -1) return 1; return 0; } int isfullstack(tstack s) { if ((s.top + 1) == s.size) return 1; return 0; }

Kedua modul diatas memerlukan input berupa stack yang akan diperiksa penuh atau kosong, dan mengembalikan nilai 1 atau 0. Jika hasil pemeriksaan adalah 1, artinya benar dan 0 adalah sebaliknya. Maksudnya jika isemptystack mengembalikan nilai 1 artinya kosong, jika 0 tidak kosong. Jika isfullstack mengembalikan nilai 1 artinya penuh, jika 0 artinya tidak penuh. Operasi untuk memasukkan data pada sebuah stack sering disebut dengan push. Operasi push hanya bisa dilakukan jika stack tidak penuh. Jika operasi push berhasil dilakukan, maka akan dikembalikan nilai 1, selain itu dikembalikan nilai 0. Operasi ini membutuhkan dua input, yaitu data yang akan dimasukkan dan stack yang dituju (dikirimkan alamatnya, sehingga perubahan pada stack langsung ter-update). Maka instruksi programnya adalah sebagai berikut.

int push(tstack *s, int data) { if (isfullstack(*s)) return 0; (*s).top++; (*s).data[(*s).top] = data; return 1; }

Operasi untuk mengeluarkan data dari stack disebut pop. Operasi pop bisa dilakukan jika stack tidak kosong. Jika pop berhasil dikembalikan nilai 1, selain itu dikembalikan nilai 0. Operasi ini membutuhkan dua input, yaitu indentifier (variabel) untuk menampung data yang dikeluarkan dan stack yang dituju (dikirimkan alamatnya, sehingga perubahan pada stack langsung ter-update). Maka instruksi programnya adalah sebagai berikut.

int pop(tstack *s, int *hasil) { if (!isemptystack(*s)) { *hasil = (*s).data[(*s).top]; (*s).top--; return 1; } return 0; }

Jika penggunaan stack telah selesai, sebaiknya stack dikosongkan kembali. Jika stack diimplementasi menggunakan array static, tentunya tidak perlu membebaskan memori yang dipakai. Dengan demikian yang perlu dilakukan hanya mengubah nilai top menjadi -1.

void clearstack(tstack *s) { (*s).top = -1; }

Diatas telah dijelaskan mengenai 6 (enam) operasi dasar pada stack. Selain operasi dasar tersebut, ada operasi lain seperti print stack, print top, print size, dan lain-lain. Dengan adanya operasi-operasi tersebut, program utama tinggal memakai atau memanggil operasi-operasi tersebut sesuai kebutuhan. Berikut ini adalah contoh program sederhana beserta ilustrasinya. Isi file stacksa.h (stack dengan static array)

# include typedef struct { int data[1000],size,top; } tstack; tstack createstack(int ukuran) { tstack s; s.size=ukuran; s.top = -1; return s; } int isemptystack(tstack s) { if (s.top == -1) return 1; return 0; }

int isfullstack(tstack s) { if ((s.top + 1) == s.size) return 1; return 0; } int push(tstack *s, int data) { if (isfullstack(*s)) return 0; (*s).top++; (*s).data[(*s).top] = data; return 1; } int pop(tstack *s, int *hasil) { if (!isemptystack(*s)) { *hasil = (*s).data[(*s).top]; (*s).top--; return 1; } return 0; } void clearstack(tstack *s) { //pada array statik tidak diperlukan free, hanya menset top ke -1 (*s).top = -1; }

Isi file stack1.cpp 1 #include stacksa.h

2 int main() { 3 tstack stack; 4 int tampung; 5 6 stack = createstack(10); 7 if(!isemptystack(stack)) 8 printf(tidak kosong); 9 else 10 printf(kosong); 11 12 if(isfullstack(stack)) 13 printf(penuh); 14 else 15 printf(tidak penuh); 16 17 push(&stack, 43); 18 push(&stack, 81); 19 push(&stack, 79); 20 21 pop(&stack,&tampung); printf("%d",tampung); 22 23 clearstack(&stack); 24 return 0; 25}

Ilustrasi : Kondisi stack setelah baris 6

stack


. . . . . . . . . . stack.data[999]

stack.size 10 stack.top -1

tampung Kondisi stack setelah baris 17

stack

stack.data[0] 43 stack.data[1]

. . . . . . . . . . stack.data[999]

stack.size 10 stack.top 0


stack

stack.data[0] 43 stack.data[1] 81

. . . . . . . . . . stack.data[999]



stack

stack.data[0] 43 stack.data[1] 81 stack.data[2] 79

. . . . . . . . . . stack.data[999]



stack

stack.data[0] 43 stack.data[1] 81 stack.data[2]

. . . . . . . . . . stack.data[999]


tampung 79

Kondisi stack setelah baris 23

stack


. . . . . . . . . . stack.data[999]

stack.size 10 stack.top -1

tampung

b. Implementasi stack dengan dynamic array

Struct untuk stack menggunakan dynamic array adalah sebagai berikut. Disini data berupa pointer ke variabel integer. Dengan demikian bisa dialokasikan memori sesuai kebutuhan yaitu size. typedef struct { int *data, size, top; } tstack; Berikut ini adalah operasi createstack, didalamnya terdapat instruksi malloc untuk mengalokasikan memori sesuai kebutuhan (size). tstack createstack(int ukuran) { tstack s; s.size = ukuran; s.data = (int *) malloc (s.size * sizeof(int)); s.top = -1; return s; } Jika ukuran diberi nilai 5 (lima), maka ilustrasi stack adalah sebagai berikut :

stack

[0] [1] [2] [3] [4] stack.data stack.size 5 stack.top -1

Bagaimana dengan operasi lainnya ?

c. Implementasi stack dengan linked list

Struct untuk stack menggunakan Linked List adalah sebagai berikut. Disini data akan tersimpan berupa simpul atau node, jadi diperlukan sebuah struct khusus

untuk simpul atau node. Selanjutnya top adalah sebuah pointer yang menunjuk ke simpul atau node paling depan dari linked list.

struct tnode { int data; struct tnode *next; }; typedef struct { struct tnode *top; int size; } tstack;

Berikut ini adalah operasi createstack, didalamnya terdapat instruksi untuk memberi nilai s.top = NULL;, karena stack masih kosong. Selain itu juga terdapat instruksi untuk mengatur jumlah maksimal simpul atau node pada linked list yaitu s.size = ukuran; .

tstack createstack(int ukuran) { tstack s; s.size = ukuran; s.top = NULL; return s; }

Jika ukuran diberi nilai 5 (lima), maka ilustrasi stack adalah sebagai berikut :

stack stack.size 5 stack.top /

Jika dilakukan push dengan data 102, maka ilustrasi stack adalah sebagai berikut :

stack stack.size 5 stack.top 102 /

Jika dilakukan push dengan data 345, maka ilustrasi stack adalah sebagai berikut :

stack stack.size 5 stack.top 345 102 /

Bagaimana dengan operasi lainnya ?

KASUS YANG BISA DISELESAIKAN DENGAN STRUKTUR DATA STACK Membalik susunan huruf pada kalimat atau kata Memeriksa Palindrome Memeriksa pasangan kurung, misalnya {(())} Evaluasi Postfix Evaluasi Prefix Konversi Basis Bilangan Depth First Search pada Graph dan Tree N-Queens Problem

Contoh :

Evaluasi Postfix Notasi yang manusia gunakan untuk menyatakan suatu operasi matematika disebut notasi infix. Pada notasi ini simbol operator diletakkan di tengah diantara kedua operan yang dioperasikan. Selain notasi infix terdapat notasi prefix dan notasi postfix. Pada notasi prefix, operator ditulis di depan (di kiri) operan, dan pada notasi postfix operator dituliskan di belakang (di kanan operan). Notasi prefix dan postfix mempunyai kelebihan dibandingkan infix karena tidak memerlukan tanda kurung untuk mendahulukan suatu perhitungan.

Compiler menggunakan notasi postfix untuk evaluasi (menghitung nilai) suatu ekspresi. Untuk evaluasi notasi postfix diperlukan bantuan sebuah stack untuk menyimpan bilangan. Cara evaluasinya adalah:

1. kosongkan stack 2. ulangi proses berikut

a. baca data b. jika data adalah bilangan maka bilangan di-push ke dalam stack c. jika data adalah operator maka

(i) pop stack dan hasilnya sebagai operan 2 (ii) pop stack dan hasilnya sebagai operan 1 (iii) operasikan kedua operan berdasarkan operator (iv) push hasil opersi ke dalam stack sampai data habis

diproses. 3. Pop stack dan hasilnya adalah hasil evaluasi ekspresi

Membalik susunan kalimat atau kata Satu persatu karakter pembentuk string di-push ke dalam stack. Setelah semua karakter telah masuk ke stack maka dilakukan pop sampai stack kosong. # include # include stacksa.h int main() { tstack stack; char kalimat[1000], hasil; int i, flag; stack = createstack(); gets(kalimat); for (i = 0; kalimat[i] != '\0'; i++) push(&stack, kalimat[i]); while (!isemptystack(stack)) { flag = pop(&stack, &hasil); printf("%c", hasil); } return 1; }

Pembalikan karakter suatu string dapat juga dilakukan dengan sebuah function yang rekursif seperti program di bawah ini. # include void membalik_string() { char huruf; huruf = getche(); if (huruf != 13) membalik_string(); printf("%c", huruf); } int main() { membalik_string(); return 1; } Atau menambahkan carriage return (\n) sebelum mencetak karakter pertama hasil pembalikan. Karakter \n ini hanya boleh dicetak satu kali saja sehingga diakali dengan sebuah flag. Setelah mencetak \n nilai flag diubah. # include void membalik_string(int *flag) {

char huruf; huruf = getche(); if (huruf != 13) membalik_string(flag); if (*flag == 1) { printf("\n"); *flag = 0; } printf("%c", huruf); } int main() { int a = 1; membalik_string(&a); return 1; }

References : 1. Ngoen, T.S., (2004), Data Structures, IBII Lecture Notes 2. Horowitz,E., Sahni,S. and Anderson-Freed,S.,(1993), Fundamentals of Data Structures in C,

Computer Science Press,New York. 3. Mark Allen Weiss, 1997, Data Structures and Algorithm Analysis in C, Addison Wesley Longman,

inc.

stack

Documents