ndymam

Bab 5 : STACK

Gambar 5.1 : Jenis – jenis data

Keterangan :

Stack dan Queue dapat diimplementasikan dengan array, record maupun pointer / link-list sedangkan array, record dan pointer / link list sendiri merupakan tipe data struktur yang dapat terdiri dari byte, integer, real dll

5.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.

ditambah 2 piring diambil 1 piring

Gambar 5.2: Ilustrasi STACK dengan tumpukan piring

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

	OPERASI	ISI STACK	NILAI TOP
1.	CREATESTACK(S)	:	0
2.	PUSH(‘a’,S)	: a	1
3.	PUSH(‘b’,S)	: a b	2
4.	PUSH(‘c’,S)	: a b c	3
5.	POP(e)	: a b	2
6.	PUSH(‘d’,S)	: a b d	3
7.	POP(e)	: a b	2
8.	POP(e)	: a	1

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.

5.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.

stack yang terisi

tempat kosong

1 top pjg_max

5 5 5

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;

	Index	Isi
	1	‘Ali’
	2	‘Amir’
	3	‘Tina’
	4	‘Tuti’
Top Ø	5	‘Maria’
	6
	100

Seperti terlihat pada contoh di atas, diperlukan suatu penunjuk (dalam contoh disebut top), yang menunjukkan posisi paling atas dari stack.

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;

}

Misalkan kita memiliki stack yang mempunyai elemen bertipe integer

Sebelum di PUSH Sesudah di PUSH

1	100	1	100
2	25	2	25
topØ> 3	2	3	2
4		PUSH (70) top Ø 4	70
5		5
.
.
Pjg_max		Pjg_max

Gambar 5.3: Operasi PUSH pada STACK dengan ARRAY

Dengan mempergunakan contoh yang sama seperti di atas

Sebelum di PUSH Sesudah di PUSH

1	100	1	100
2	25	2	25
3	2	top Ø3	2
top Ø 4	70	POP ( e ) 4	70
5		5
.			.
.			.
pjg_max		pjg_max

Note : setelah di pop var e akan berisi angka 70 perhatikan bahwa secara fisik, angka 70 masih tetap berada pada stack, tetapi hal ini tidak akan berpengaruh karena top sudah berada pada posisi ke 3.

Gambar 5.4: Operasi POP pada STACK dengan ARRAY

5.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

typedef int elementype;

struct node {

elementype data;

struct node *next;

};

struct node *head;

void create();

{

Head = null;

}

void clear();