Stack atau tumpukan adalah kumpulan data yang seolah-olah diletakkan di atas data yang
lain.
Dalam suatu tumpukan akan dapat dilakukan operasi penambahan (penyisipan) dan
pengambilan (penghapusan) data melalui ujung yang sama, ujung ini merupakan ujung
atas tumpukan
Bersifat LIFO (Last In First Out)
Benda yang terakhir masuk ke dalam stack akan menjadi benda pertama yang
dikeluarkan dari stack
Contoh: Tumpukan buku di perpustakaan, tumpukan kartu deck.
Operasi-Operasi / Fungsi Stack
Push : digunakan untuk menambah item pada stack pada tumpukan paling atas
Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas
IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong
IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh
// stack.h: header file
class Stack {
int MaxStack;
int EmptyStack;
int top;
char* items;
public:
Stack(int);
~Stack();
void push(char);
char pop();
int empty();
int full();
};
// stack.cpp: stack functions
#include "stack.h"
Stack::Stack(int size) {
MaxStack = size;
EmptyStack = -1;
top = EmptyStack;
items = new char[MaxStack];
}Stack::~Stack() {delete[] items;}
void Stack::push(char c) {
items[++top] = c;
}char Stack::pop() {
return items[top--];
}int Stack::full() {
return top + 1 == MaxStack;
}int Stack::empty() {
return top == EmptyStack;
}
Pemanfaatan Stack
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, dan Postfix
Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand
merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator
untuik menghasilkan suatu solusi.
Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’
merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua
operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat dibedakan dalam tiga
bentuk notasi perhitungan yaitu :
1) Notasi prefix, jika operator ditempatkan sebelum dua operand
Contoh: * + A B C
2) Notasi infix, jika operator ditempatkan di antara dua operand
Contoh: (A + B) * C
3) Notasi postfix, jika operator ditempatkan setelah dua operand
Contoh: A B + C *
Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan notasi aritmatika
yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding
dengan dua notasi yang lain, akan tetapi notasi Postfix merupakan notasi yang digunakan oleh
mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean,
sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.
Proses Konversi Infix ke Prefix
Misalkan diberikan ekspresi: (A + B) * (C – D)
(A + B) * (C – D) = ((A + B) * (C – D))
= ( + (A B) * - (C D))
= *+ AB–CD
Proses Konversi Infix ke Postfix
Misalkan diberikan ekspresi: (A + B) * (C – D)
(A + B) * (C – D) = ((A + B) * (C – D)) = ((A B) + * (C D) - ) = A B+CD -*
Proses Konversi Prefix ke Infix
Misalkan diberikan ekspresi: * + A B – C D
* + A B – C D = (* (+ A B) (– C D) )
= (A + B) * (C – D)
Proses Konversi Postfix ke Infix
Misalkan diberikan ekspresi: A B + C D - *
A B + C D - * = ((A B +) (C D -) *)
= (A + B) * (C – D)
