Pengertian Stack dari Struktur Data

Secara bahasa, Stack berarti tumpukan. Jika dikaitkan dengan struktur data, Stack berarti sekumpulan data yang organisasi atau strukturnya bersifat tumpukan atau menyerupai tumpukan.

Dalam ilmu komputer, stack atau tumpukan merupakan sebuah koleksi objek yang menggunakan prinsip LIFO (Last In First Out), yaitu data yang terakhr kali dimasukkan akan pertama kali keluar dari stack tersebut. Stack dapat diimplementasikan sebagai representasi berkait atau kontigu (dengan tabel fix).

Ciri Stack :

1. - Elemen TOP (puncak) diketahui
2. - penisipan dan penghapusan elemen selalu dilakukan di TOP
3. - LIFO
4. - Pemanfaatan Stack :
5. - Perhitungan ekspresi aritmatika (posfix)
6. - algoritma backtraking (runut balik)
7. - algoritma rekursif

Pemanfaatan Stack :

• Perhitungan ekspresi aritmatika (posfix)
• algoritma backtraking (runut balik)
• algoritma rekursif

Operasi Stack yang biasanya :

· buat stack (stack) – create: membuat sebuah stack baru yang masih kosong, dan beberapa selektor yang lain.

• Push (input E : typeelmt, input/output data : stack): menambahkan sebuah elemen ke stack
• Pop (input/output data : stack, output E : typeelmt ) : menghapus sebuah elemen stack

·IsEmpty (): fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak
·IsFull () : fungsi untuk memeriksa apakah stack yang ada sudah penuh

1. buat stack (stack) – create

• membuat sebuah stack baru yang masih kosong
• spesifikasi:

1. — tujuan : mendefinisikan stack yang kosong
2. — input : stack
3. — syarat awal : tidak ada
4. — output stack : – (kosong)?
5. — syarat akhir : stack dalam keadaan kosong

2. stack kosong (stack) – empty

• fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak
• spesifikasi:

1. — tujuan : mengecek apakah stack dalam keadaan kosong
2. — input : stack
3. — syarat awal : tidak ada
4. — output : boolean
5. — syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong

3. stack penuh (stack) – full

• fungsi untuk memeriksa apakah stack yang ada sudah penuh
• spesifikasi:

1. — tujuan : mengecek apakah stack dalam keadaan penuh
2. — input : stack
3. — syarat awal : tidak ada
4. — output : boolean
5. — syarat akhir : stack penuh bernilai true jika stack dalam keadaan penuh

4. push (stack, info baru)?

• menambahkan sebuah elemen kedalam stack.
• spesifikasi:

1. — tujuan : menambahkan elemen, info baru pada stack pada posisi paling atas
2. — input : stack dan Info baru
3. — syarat awal : stack tidak penuh
4. — output : stack
5. — syarat akhir : stack bertambah satu elemen

5. pop (stack, info pop)?

• mengambil elemen teratas dari stack
• spesifikasi:

1. — tujuan : mengeluarkan elemen dari stack yang berada pada posisi paling atas
2. — input : stack
3. — syarat awal : stack tidak kosong
4. — output : stack dalam info pop
5. — syarat akhir : stack berkurang satu elemen

OPERASI PADA STACK –

Contoh :

• Operasi Push

void Push (NOD **T, char item)
{
NOD *n;
n=NodBaru (item);
n->next=*T;
*T=n;
}

• Operasi Pop

char Pop (NOD **T)
{
NOD *n; char item;
if (!StackKosong(*T)) {
P=*T;
*T=(*T)->next;
item=P->data;
free(P);
}
return item;
}

Di dalam pengembangannya, stack dapat dikelompokkan menjadi dua bagian. Dua bagian tersebut yaitu Single Stack dan Double Stack.
1.Single Stack
Single Stack atau Stack Tunggal adalah stack yang hanya terdiri dari satu koleksi. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus dilakukan bertahap dari indeks TOP-nya.

Menggunakan Single Lingked List dalam pembuatan stack mempunyai keunggulan dibandingkan dengan array yaitu dapat digunakan lokasi memori yang dinamis sehingga menghindari pemborosan memori.

Di dalam proses single stack terdapat tiga macam proses utama, yaitu :
-          Inisialisasi
-          PUSH (Insert, Masuk, Simpan, Tulis)
-          POP (Delete, Keluar, Ambil, Baca, Hapus)
INISIALISASI
Proses inisialisasi merupakan proses awal yang dilakukan untuk menyimpan indeks penunjuk stack. Roses ini dilakukan dengan intruksi :

top = -1;

PUSH
Proses push adalah proses memasukkan data baru ke stack indeks selanjutnya. Algoritma dasar proses PUSH adalah :

top = top + 1; array[top] = variable_tampung;

POP
Proses pop adalah proses mengeluarkan  / mengambil data dari stack dengan indeks yang disimpan pada variable top. Algoritma dasar proses POP adalah :

variable_tampung = array[top]; top = top – 1;

2.Double Stack
Double Stack atau Stack Ganda adalah stack yang hanya terdiri dari dua single stack. Bila stack ini direpresentasikan dengan array, maka pengisian dan penghapusan harus melalui salah satu arah.
Merupakan metode khusus yang dikembangkan untuk menghemat pemakaian memori dalam pembuatan dua stack dengan array . intinya adalah penggunaan hanya sebuah array untuk menampung dua buah stack.
Di dalam proses double stack terdapat lima macam proses utama, yaitu :
-          Inisialisasi
-          PUSH1 (Proses Push untuk Single Stack pertama)
-          POP1 (Proses Pop untuk Single Stack pertama)
-          PUSH2 (Proses Push untuk Single Stack kedua)
-          POP2 (Proses Pop untuk Single Stack kedua)
Algoritma dasar masing – masing proses adalah sebagai berikut :

INISIALISASI	top1 = -1; top2 = MAX_ARRAY;
PUSH1	top1 = top1 + 1; array[top1] = variable_tampung;
POP1	variable_tampung = array[top1]; top1 = top1 – 1;
PUSH2	top2 = top2 – 1; array[top2] = variable_tampung;
POP2	variable_tampung = array[top2]; top2 = top2 + 1;

CONTOH PEMANFAATAN STACK
• Notasi Infix Prefix
• Notasi Infix Postfix
Pemanfaatan stack antara lain untuk menulis ungkapan dengan menggunakan notasi tertentu.
Contoh :
( A + B ) * ( C – D )
Tanda kurung selalu digunakan dalam penulisan ungkapan numeris untuk mengelompokkan bagian mana yang akan dikerjakan terlebih dahulu.
Dari contoh ( A + B ) akan dikerjakan terlebih dahulu, kemudian baru ( C – D ) dan terakhir hasilnya akan dikalikan.
A + B * C – D
B * C akan dikerjakan terlebih dahulu, hasil yang didapat akan berbeda dengan hasil notasi dengan tanda kurung.

Notasi Infix Prefix

Cara penulisan ungkapan yaitu dengan menggunakan notasi infix, yang artinya operator ditulis diantara 2 operator.
Seorang ahli matematika bernama Jan Lukasiewiccz mengembangkan suatu cara penulisan ungkapan numeris yang disebut prefix, yang artinya operator ditulis sebelum kedua operand yang akan disajikan.
Contoh :
Proses konversi
dari infix ke prefix :
= ( A + B ) * ( C – D )
= [ + A B ] * [ - C D ]
= * [ + A B ] [ - C D ]
= *+AB – C D
Penggunaan notasi postfix dalam stack, misal :
2 14 + 5 * = 80