Struktur Data

Stack

Stack adalah struktur data yang memiliki sifat last in first out.

Struktur dari stack yang dapat kita lihat sehari-hari adalah : tumpukan (lihat gambar 1.1)

Gambar 1.1

StackTerdapat 2 (dua) operasi yang dapat dikerjakan dalam stack :

push  dan pop  (lihat gambar 2.2). 

Push adalah operasi menambahkan data ke tumpukkan, sedangkan

pop adalah operasi mengambil data yang menempati posisi teratas dari stack.

Gambar 2.2a Operasi Push Pada Stack

Gambar 2.2b Operasi Pop Pada Stack

Gambar 2.2c Operasi Push dan Pop Pada Stack

 

Gambar 2.2d Contoh Lengkap Operasi Stack

Stack bisa dipakai untuk aplikasi delimiter check

.  Contoh delimiter {, [, (, ), ], }. Setiap pembuka delimiter harus mempunyai delimiter penutup.  Contoh :a{bc[d]e}f(g)                 BENARa{bc[d}e]f(g)                 SALAH

Implementasi Stack Menggunakan Array

Diandaikan jumlah tumpukan stack tidak akan melebihi K.  Maka berikut ini adalah langkah-langkah implementasi stack menggunakan Array :1.Buat array dengan nama S (array 1 dimensi) yang memiliki ukuran KS[K]2.bagian top dari stack dinamakan h, diberi nilai awal = 03.Misal terjadi operasi

push(x)

 : menambahkan elemen

x

 ke dalam stack. maka terdapat dua proses yang terjadi :(3.1)  S[h]=x(3.2)  h++4.Jika terjadi operasi pop() : mengambil data teratas dari stack, maka terdapat dua proses yang terjadi :(4.1)  h--(4.2)  return S[h]5.Top()  : melihat data teratas dari stack, maka proses yang terjadi :(5.1)  return S[h-1]6.Empty()  : Mengecek apakah stack dalam kondisi kosong ?(6.1)  return (h==0)Setiap kali terjadi operasi, harus dilakukan pengujian terhadap batas dari array. Terdapat 2 (dua) kondisi yang terjadi :1.Jika memasukkan data ke stack yang telah penuh, saat h=K maka terjadi

Overflow

2.Jika mengambil data dari stack yang kosong, saat h<0 maka terjadi

Underflow

Penentuan Ukuran Stack

Ukuran dari stack perlu diperhatikan. Ukuran yang ideal disesuaikan dengan kebutuhan pemakaian karena Jika ukuran stack yang disediakan sangat besar dibandingkan dengan stack yang terpakai maka terjadi kondisi

wasting space

(pemborosan tempat penyimpanan).  Sedangkan jika ukuran stack yang disediakan lebih sedikit dibandingkan dengan yang dibutuhkan maka akan terjadi masalah kekurangan tempat penyimpanan.Implementasi Stack Menggunakan Alokasi Memori Dinamis dan Pointer

Ide dasar dari implementasi ini adalah mengalokasikan memori saat dibutuhkan. Ada beberapa hal yang perlu diperhatikan berkaitan dengan implementasi ini :1.penunjuk (pointer)

head

 akan menunjuk ke data pertama.2.Setiap data dalam stack disimpan dalam

node

3.Setiap

node

 memiliki 2 (dua) informasi penting yaitu

data

 dan

berikut

4.Pada saat awal,

head

 berikan nilai NULL yang berarti belum ada data di dalam stack5.Pada saat operasi pengecekan kosong atau tidaknya sebuah stack, maka perintah yang diberikan adalah :return (

head

 == NULL)6.Pada saat operasi memperoleh nilai teratas dari stac, maka perintah yang diberikan adalah :

jika

 (stack tidak kosong)

maka

 kembalikan data pada posisi teratasdi dalam potongan bahasa C/C++, pernyataan di atas dituliskan sebagai berikut :if (!empty()){return (

head

.data)}

Fungsi

Push

 Pada Stack Menggunakan Pointer

void push(int x){//buat node baruT = new struct_dari_nodeT.data = xT.berikut =

head

head = T}

Fungsi

Pop

 Pada Stack Menggunakan Pointer

tipe_dari_datapop(){if(empty()){return NULL}X = head.dataT = headhead = head.berikutdelete Treturn X}