4.1 Definisi Stack
Dalam perancangan suatu program, kadang-kadang kita memerlukan tipe data yang abstraksinya lebih tinggi dari sekedar native data type yang tersedia. Pada bab ini akan dibahas satu abstrak data type yang lebih tinggi abstraksinya dan pada umumnya tidak disediakan native data typenya, yaitu stack. Walaupun dikatakan tipe data ini mempunyai abstraksi yang lebih tinggi tetapi kalau sampai pada tahap implementasi dari tipe data ini, kita tetap memerlukan native data type yang tersedia (array, record, pointer, linked-list, dll). Untuk keperluan implementasi dalam buku ini dipergunakan 2 tipe data, yaitu array dan linked-list. Gambar berikut ini diharapkan dapat menjelaskan hubungan dan level abstraksi dari tipe data.
Stack adalah tipe data yang mengikuti pola Last In First Out (LIFO), yang berarti elemen yang terakhir masuk adalah elemen yang pertama keluar. Contoh yang dapat diilustrasikan sebagai stack ini tumpukan piring di kantin dimana pada saat piring diletakkan akan diletakkan pada bagian atas, dan pada saat pengambilan juga akan diambil dari yang paling atas.
Secara umum operasi yang sering diterapkan pada stack adalah:
> CREATESTACK(S) : membuat stack baru S, dengan jumlah elemen kosong.
> CLEARSTACK(S) : mengosongkan tumpukan S, jika ada elemen dalam stack maka akan dihapus.
> EMPTY(S) : mengecek apakah stack kosong?, mengembalikan nilai TRUE apabila stack kosong atau nilai FALSE apabila stack berisi.
> FULL(S) : mengecek apakah stack penuh?, mengembalikan nilai TRUE apabila stack penuh atau FALSE apabila stack belum penuh.
> PUSH(e,S) : memasukkan elemen baru e kedalam stack
> POP(e) : mengeluarkan elemen pada posisi teratas pada stack.
Ilustrasi operasi – operasi diatas terhadap stack
Apa yang akan terjadi apabila dilakukan operasi POP(e) sebanyak 2 kali lagi. Yang terjadi adalah UNDERFLOW, yaitu suatu keadan dimana tidak ada lagi elemen didalam stack yang dapat di ambil. Maka dari itu untuk operasi POP(e) selalu terkait dengan pengecekan status stack (apakah stack kosong), apabila pada pengecekan dengan EMPTY(S) menghasilkan nilai TRUE, maka operasi POP(e) tidak bisa dilakukan. Begitu pula sebaliknya pada operasi PUSH(e,S) tidak dapat dilakukan apabila stack penuh (OVERFLOW) dalam hal ini fungsi FULL(S) menghasilkan nilai TRUE. Nilai TRUE yang dihasilkan oleh fungsi FULL(S) dikarenakan terdapatnya batas jumlah elemen dalam stack.
4.2 Implementasi Stack dengan array
Sebelum kita menuliskan program untuk mengimplementasikan stack dengan menggunakan array, ada baiknya kita lihat ilustrasi dari stack seperti diperlihatkan pada gambar berikut ini.
Berikut akan diberikan contoh dari implementasikan stack dengan array beserta dengan contoh isi datanya.
#define pjg_max = 100;
typedef …… elementype; /*titik-titik diisi oleh user*/
elementype s[pjg_max];
int TOP;
void createstack();
{
Top = 0;
}
void clearstack();
{
Top = 0;
}
int full();
{
if(top == pjg_max) return(1);
else return (0);
}
int empty();
{
if(top == 0) return(1);
else return (0);
}
void push(type e);
{
if(!full()) {
Top = top + 1;
S[top] = e;
}
}
void pop(type e);
{
if(!empty()) {
e = S[top];
Top = top – 1;
}
}
4.3 Implementasi Stack dengan list
Salah satu perbedaan yang menyolok antara implementasi stack dengan menggunakan array dan linked-list adalah alokasi memory yang bersifat dinamis pada linked-list, sehingga tidak dikenal operasi full. Seperti halnya array, pada implementasi linked-list diperlukan satu penunjuk; top; yang menunjukkan posisi awal dari stack yang bersangkutan. Implementasi berikut ini mempergunakan single linked-list.
#include<stdio.h>
#include<malloc.h>
typedef int elementype;
struct node {
elementype data;
struct node *next;
};
struct node *head;
void create();
{
Head = null;
}
void clear();
{
elementype x;
while(!empty()) pop(&x);
}
int empty();
{
if(head == null) return(1);
else return(0);
}
void push(elementype e);
{
struct node *ptr;
ptr = (struct node *)malloc(sizeof(struct node));
ptr->data=e;
ptr->next=head;
Head=ptr;
}
void pop(elementype *e);
{
struct node *ptr;
*e= head-> data;
ptr=head;
Head=head->next;
free(ptr);
}
AGUSTIAN 