Algoritma dan Struktur Data : Bab 4

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.

sda 8

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

sda 9

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.

sda 10

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;

sda 11
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;
}
}

sda 13

sda 14

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);
}

sda 14

sda 15

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s