Untuk postingan kali ini, saya akan membahas Stack dan Queue beserta contoh kodingannya
Queue adalah antrian dimana dalam antrian ini diterapkan sistem FIFO atau First In First Out, artinya data yang pertama masuk adalah data yang pertama keluar.
Ilustrasi Queue (antrian)
Berikut adalah kelemahan queue
Data yang terakhir tidak akan diproses dahulu sebelum data yang pertama diproses, sehingga waktu tunggu untuk memproses data yang ahir tadi tidak bisa diperkirakan sampai kapan.
Enqueue adalah proses untuk memasukkan elemen artinya menambah data baru.
Dequeue adalah proses untuk menghapus data dari antrian yang pertama kali masuk dan sistem menghapusnya menggunakan FIFO
Berikut contoh kodingannya
#include<iostream>
#include<conio.h>
#include<string.h>
#include<stdio.h>
#define max 15
using namespace std;
struct queue //Mendefinisikan queue dengan menggunakan
struct
{
int head;
int tail ;
int data
[15]; // menampung 15 data
};
queue antri;
//Menginputkan data queue
void enqueue(int d){
antri.head=0;
antri.tail++;
antri.data[antri.tail]=d;
cout<<"data berhasil dimasukkan"<<endl;
cout<<endl;
}
//Mengambil data dari queue
void dequeue()
{
cout<<"data terambil "<<antri.data[antri.head];
for (int
i=antri.head;i<=antri.tail;i++)
(antri.data[i]=antri.data[i+1]);
antri.tail--;
cout<<endl;
}
//Mengecek apakah antrian penuh
int isFull(){
if
(antri.tail==max-1)
return
1;
else
return
0;
}
//Mengecek apakah antrian kosong
int isEmpty(){
if
(antri.tail==-1)
{
antri.head=-1;
return
1;
}
else
return
0;
}
//Membersihkan seluruh antrian
void clear(){
antri.head=antri.tail=-1;
cout<<"semua data terhapus.";
cout<<endl;
}
//Mencetak seluruh antrian yang telah disorting secara
askending
void print_as(){
int j,i;
int tampung;
for(i=0;i<=antri.tail;i++)
{
for(j=i+1;j<=antri.tail;j++)
{
if(antri.data[i]>antri.data[j])
{
tampung=antri.data[i];
antri.data[i]=antri.data[j];
antri.data[j]=tampung;
}
}
}
for (int
c=0;c<=antri.tail;c++)
cout<<antri.data[c]<<endl;
cout<<endl;
}
int main()
{
int pil;
int input;
antri.tail=-1;
do
{
cout<<"MENU\n";
cout<<"1. ENQUEUE\n";
cout<<"2. DEQUEUE\n";
cout<<"3. DELETE ALL\n";
cout<<"4. VIEW\n";
cout<<"5. EXIT\n";
cout<<endl<<"Masukkan Pilihan Anda =
";cin>>pil;
fflush(stdin);
switch(pil)
{
//Menginputkan antrian
case 1 :
cout<<endl;
cout<<"1. ENQUEUE ";
if(isFull()==1){ //Kondisi jika antrian sudah penuh
cout<<"Antrian Penuh ! "<<endl;
}
else
//Menginputkan antrian
cout<<endl<<" Masukkan Data = ";cin>>input;
fflush(stdin);
enqueue(input);
getch();
break;
//Mengambil
data dari antrian
case 2 :
cout<<endl;
cout<<"2. DEQUEUE";
if(isEmpty()==1){
cout<<endl<<"Antrian Kosong ! ";
}
else
cout<<endl;
dequeue();
getch();
break;
//Menghapus
seluruh antrian
case
3:
cout<<endl;
cout<<"3. DELETE ALL"<<endl;
clear();
cout<<endl<<"Antrian Kosong"<<endl;
break;
//Mencetak
seluruh antrian
case 4 :
cout<<endl;
cout<<"4. VIEW";
if(isEmpty()==1){ //Pilihan jika antrian kosong
cout<<endl<<"Antrian Kosong"<<endl;
}
else
cout<<endl<<"Data
yang dicetak ";
cout<<endl;
print_as();
getch();
break;
//Keluar
dari program
case 5:
return
0;
}
}while
(pil!=6);
getch();
return 0;
}
Berikut tampilan programnya
Stack bisa diartikan sebagai suatu kumpulan data yang seolah-olah ada data yang diletakkan di atas data yang lain. Di dalam stack ini kita dapat menambahkan ataupun mengambil (menghapus) data melalui ujung yang sama yang disebut dengan ujung atas stack (top of stack). Sifat dari STACK adalah LIFO atau Last In First Out, dapat kita artikan yang terakhir masuk ialah yang pertama keluar.
Gambar Ilustrasi Stack
Berikut adalah contoh kodingan program
untuk mengkonversi inputan infix menjadi postfix, program tersebut akan
menghasilkan output berupa hasil konversi ke postfix dan hasil perhitungannya.
#include<iostream>
#include<conio.h>
#include<string>
#include<math.h>
#include<sstream>
#include<cstdlib>
using namespace std;
const int max_stack=40;
struct type_stack{
int top;
string data[max_stack];
};
type_stack stack; // mendeklarasikan variable stack dengan tipe data
bentukan (struct type_stack)
//inisiasi stack awal sebagai stack kosong dengan nilai top= -1
void init(type_stack &namastack){
namastack.top = -1;
}
//membuat fungsu isFull untuk mengecek apakah stack sudah penuh atau
belum
bool isFull(type_stack namastack, int max_stack){
if(namastack.top == (max_stack-1))
return true;
else
return false;
}
//membuat
fungsi isEmpty untuk mengecek apakah stack masih kosong atau sudah terisi
bool isEmpty(type_stack namastack){
if(namastack.top == -1)
return true;
else
return false;
}
//membuat fungsi Push untuk menambah elemen data pada stack
void Push(type_stack &namastack, string data){
namastack.top++;
namastack.data[namastack.top]=data;
}
//membuat fungsi Pop u ntuk menghapus elemen data pada stack yang paling
atas
void Pop(type_stack &namastack){
//cout<<"data
"<<namastack.data[namastack.top]<<" telah
terambil...";
namastack.top--;
}
//membuat fungsi Cetak Stack
void CetakStack_LIFO(type_stack namastack){
cout << "Data Stack (LIFO) : \n";
for(int i=namastack.top; i>=0; i--){
cout<<"
"<<namastack.data[i]<<"\n";
}
}
//fungsi memasukkan elemen-elemen string ke stack
void inputElemen(type_stack &namastack){
//menginputkan expresi infix
cout<<" Masukkan
\n";
cout<<"tekan enter setelah selesai menginputkan 1
element, \n"<<
"sampai menginputkan '=' \n";
string dataElemen;
//setiap kali memilih menu 1, maka string dataelemen diberinilai
kosong("")
dataElemen="";
int elm=0; //untuk menampilkan angka elemen ke pada saat menginputkan
elemen
while(dataElemen != "=") //melakukan perulangan untuk
menginput per elemen ekspresi sampai selesai
{
elm++;
cout<<"elemen ke "<<elm<< " : ";
cin>>dataElemen; //menginput dari keyboard 1 elemen
if(dataElemen!="=") //mengecek jika string dataInfix tidak
samadengan "="
Push(namastack,dataElemen);
//push masing elemen ke stackInfix
}
}
//fungsi untuk mengetahui operator atau bukan (operator)
bool isOpr(string opr)
{
if((opr=="*") ||
(opr=="/")||(opr=="%")||(opr=="+") ||
(opr=="-")||(opr=="^"))
{
return true;
}
else
return false;
}
//fungsi untuk menyimpan derajat presedence
int presedence(string opr)
{
if((opr=="^")||(opr=="!"))
return 4;
else if((opr=="*") ||
(opr=="/")||(opr=="%"))
return 3;
else if((opr=="+") || (opr=="-"))
return 2;
else
return 1;
}
//fungsi convert infix to postfix
void infixToPostfix(type_stack &infix, type_stack &postfix){
string symbol;
string topSymbolOpr;
type_stack stackOperator;
init(stackOperator);
for(int k=0; k<=infix.top; k++)
{
symbol=infix.data[k];
if((!isOpr(symbol)) && (symbol!="(") &&
(symbol!=")") ) //jika bukan operator, berarti symbol atau angka
{
Push(postfix,symbol);
}
else if(isOpr(symbol))
{
while((!isEmpty(stackOperator))
&& (stackOperator.data[stackOperator.top]!="("))
{
topSymbolOpr=stackOperator.data[stackOperator.top];
if(presedence(topSymbolOpr)>=presedence(symbol))
{
Pop(stackOperator);
Push(postfix,topSymbolOpr);
}
else
break;
}
Push(stackOperator,symbol);
}
else if(symbol=="(")
{
Push(stackOperator,symbol);
}
else if(symbol==")")
{
while((!isEmpty(stackOperator))
&& (stackOperator.data[stackOperator.top]!="("))
{
topSymbolOpr=stackOperator.data[stackOperator.top];
if(presedence(topSymbolOpr)>=presedence(symbol))
{
Pop(stackOperator);
Push(postfix,topSymbolOpr);
}
else
Push(stackOperator,symbol);
}
if(stackOperator.data[stackOperator.top]=="(")
Pop(stackOperator);
else
cout<<"kurung '('
tidak ditemukan";
}
}
while(!isEmpty(stackOperator))
{
topSymbolOpr=stackOperator.data[stackOperator.top];
Pop(stackOperator);
Push(postfix,topSymbolOpr);
}
}
//fungsi untuk menghitung 2 bilangan
double hitungMat(double operand1, string opr, double operand2)
{
if(opr=="+")
return (operand1 + operand2);
else if(opr=="-")
return (operand1 - operand2);
else if(opr=="*")
return (operand1 * operand2);
else if(opr=="/")
return (operand1 / operand2);
else if(opr=="")
return (double)((int)operand1 % (int)operand2);
else if(opr=="^")
return (pow(operand1,operand2));
else
return 0;
}
//fungsi konvert string to double
double strToDouble(string strangka)
{
std::istringstream stm;
stm.str(strangka);
double d;
stm >>d;
return (d);
}
//fungsi konvert double to string
string doubleToStr(double angka)
{
ostringstream ss;
ss << angka;
return (ss.str());
}
//fungsi eksekusi ekspresi postfix
string ekskusiPostfix(type_stack &namastackPostfix)
{
type_stack stackHasil;
init(stackHasil);
string symbol;
double operand1, operand2;
for(int i=0; i<=namastackPostfix.top; i++)
{
symbol=namastackPostfix.data[i];
if(!isOpr(symbol))
{
Push(stackHasil,symbol);
}
else if(isOpr(symbol))
{
operand2=strToDouble(stackHasil.data[stackHasil.top]);
Pop(stackHasil);
operand1=strToDouble(stackHasil.data[stackHasil.top]);
Pop(stackHasil);
double hasilHitungan;
hasilHitungan=hitungMat(operand1,symbol,operand2);
Push(stackHasil,doubleToStr(hasilHitungan));
}
}
return stackHasil.data[stackHasil.top];
}
int main(){
type_stack stackInfix;
type_stack stackPostfix;
do
{
Menu :
int menu;
cout<< "
Menu Stack" << endl;
cout<< endl;
cout<< "1. Input Infix "<<endl;
cout<< "2. Konvert Infix ke Postfix "<<endl;
cout<< "3. Hasil Perhitungan "<<endl;
cout<< "4. Keluar "<<endl;
cout<< endl;
cout<< "Masukkan Pilihan Anda : ";
cin>>menu;
switch(menu)
{
case 1:
init(stackInfix); //inisiasi stackInfix untuk membuat stack kosong
if(!isFull(stackInfix,max_stack))
{
inputElemen(stackInfix);
//memanggil fungsi inputElemen
cout<<endl;
cout<<"expresi infix yang
anda masukkan : ";
cout<<" ";
for(int i=0; i <=stackInfix.top; i++){cout<<stackInfix.data[i]; }
cout<<endl;
cout<<endl;
}
else
{
cout<<"Maaf, Stack Telah Penuh..!";
}
cout<<endl;
break;
case 2:
init(stackPostfix);
infixToPostfix(stackInfix,stackPostfix);
cout<<endl;
cout<<"expresi Postfix
: ";
cout<<" ";
for(int i=0; i <=stackPostfix.top;
i++){cout<<stackPostfix.data[i]; }
cout<<endl;
cout<<endl;
break;
case 3:
cout<<endl;
cout<<"hasil Perhitungan expresi "; for(int i=0; i
<=stackPostfix.top; i++){cout<<stackPostfix.data[i]; }
cout<<"\nadalah :
"<<ekskusiPostfix(stackPostfix)<< endl<<endl;
break;
case 4:
exit(0);
break;
default:
cout <<"\n Input Menu Salah...!!!";
cout<<"\n Press Any key to return to menu ";
_getch();
system("cls");
goto Menu;
}
}while(1);
}
Berikut tampilan hasil programnya
Sekian untuk postingan kali ini. Semoga postingan ini bermanfaat untuk teman-teman semua.
Tidak ada komentar:
Posting Komentar