Stack dan Queue Pada Array

Nama : Muh Saiful   

Nim   : E1E1 15 075

           Kali ini saya akan membahas stack dan queue pada array langsung saja saya akan menjelaskan kan sedikit tentang Stack dan Queue.

1. Pengertian Stack (Tumpukan)

          Stack (Tumpukan) adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linear. Kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu posisi ATAS (TOP) tumpukan. Tumpukan digunakan dalam algoritma pengimbas (parsing), algoritma penilaian (evaluation) dan algoritma penjajahan balik (backtrack). Elemen-elemen di dalam tumpukan dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

          Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In First Out), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack. Tumpukan disebut juga “Push Down Stack” yaitu penambahan elemen baru (PUSH)ndan penghapusan elemen dari tumpukann(POP). Contoh pada PDA (Push Down Automaton). Sistem pada pengaksesan pada tumpukan menggunakn system LIFO (Last In First Out), artinya elemen yang terakhir masuk itu yang akan pertama dikeluarkan dari tumpukan (Stack). Ilustrasi tumpukan (Stack) dapat digambarkan seperti tumpukan CD atau tumpukan sate. Stack merupakan suatu susunan koleksi data dimana dapat ditambahkan dan dihapus selalu dilakukan pada bagian akhir data, yang disebut dengan Top Of Stack.

  

Operasi – operasi pada Stack (Tumpukan) :

• Push : digunakan untuk menembah item pada Stack pada Tumpukan paling atas.
• Pop : digunakan untuk mengambil item pada Stack pada Tumpukan paling atas.
• Clear : digunakan untuk mengosongkan Stack.
• Create Stack : membuat Tumpukan baru S, dengan jumlah elemen kosong.
• MakeNull : mengosongkan Tumpukan S, jika ada elemen maka semua elemen dihapus.
• IsEmpty : fungsi yang digunakan untuk mengecek apakah Stack sudah kosong.
• Isfull : fungsi yang digunakan untuk mengecek apakah Stack sudah penuh.

2. Definisi Queue (Antrian)

          Queue merupakan suatu struktur data linear. Konsepnya hampir sama dengan Stack, perbedaannya adalah operasi penambahan dan penghapusan pada ujung yang bebeda. Penghapusan dilakukan pada bagian depan (front) dan penambahan berlaku pada bagian belakang (Rear). Elemen-elemen di dalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur.

          Tumpukan disebut juga “Waiting Line” yaitu penambahan elemen baru dilakukan pada bagian belakang dan penghapusan elemen dilakukan pada bagian depan. Sistem pada pengaksesan pada Queue menggunakan sistem FIFO (First In First Out), artinya elemen yang pertama masuk itu yang akan pertama dikeluarkan dari Queue. Queue jika diartikan secara harfiah, queue berarti antrian. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat anda mengantri diloket untuk membeli tiket.

         Istilah yang cukup sering dipakai apabila seseorang masuk dalam sebuah antrian adalah enqueue. Sedang istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

Operasi-operasi pada Queue :

• Create Queue (Q) : membuat antrian baru Q, dengan jumlah elemen kosong.
• Make NullQ (Q) : mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.
• EnQueue : berfungsi memasukkan data kedalam antrian.
• DeQueue : berfungsi mengeluarkan data terdepan dari antrian.
• Clear : Menghapus seluruh Antrian
• IsEmpty : memeriksa apakah antrian kosong
• IsFull : memeriksa apakah antrian penuh.

Berikut codingannya , jangan lupa untuk dipahami ya setiap codingannya !!!

Semoga bermanfaat . 

1. Program Stack (Tumpukan)

Script Program :

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define max_stack 15

using namespace std;

struct stack {//Mendefinisikan stack dengan menggunakan struct

    int top;
    string data[max_stack]; //string data untuk menampung stack yg tidak berurut
    string tampil_urut[max_stack]; //string tampil_urut untuk menampung stack yang terurut
};stack tumpuk; //stack dideklarasikan menjadi tumpuk


void push(string d){ //Fungsi push untuk memasukkan stack
    tumpuk.top++;
   tumpuk.data[tumpuk.top]=d;
    cout<<"data berhasil dimasukkan"<<endl;
}

void pop(){ // fungsi pop untuk mengeluarkan stack teratas(paling trakhir di input)
    cout<<"data "<<tumpuk.data[tumpuk.top]<<" terambil";
    tumpuk.top--;
}

bool isFull() //untuk mengecek apakah stack penuh
{
    if (tumpuk.top==max_stack-1)
        return true;
    else
        return false;
}

bool isEmpty(){ // untuk mengecek apakah stack kosong
    if (tumpuk.top==-1)
        return true;
    else
        return false;
}

void clear(){ //untuk menghapus isi stack
    tumpuk.top=-1;
    cout<<"semua data terhapus "<<endl;
}
void tukar(int a,int b) //untuk menukar nilai a dan b (mengurutkan stack)
{
    string t;
    t=tumpuk.tampil_urut[b];
    tumpuk.tampil_urut[b]=tumpuk.tampil_urut[a];
    tumpuk.tampil_urut[a]=t;
}

void print(){  //untuk menampilkan data stack
    string t;
    string pilih;
    cout<<"Tampilkan Data Yang Belum Terurut:"<<endl;
    for (int i=tumpuk.top;i>=0;i--){
        cout<<tumpuk.data[i]<<endl;
        tumpuk.tampil_urut[i]=tumpuk.data[i];
    }

    cout<<"\nPilih Sorting Ascending atau Descending(asc/desc) :"; cin>>pilih;
    if(pilih=="asc"){
        for (int i=0; i<tumpuk.top; i++){
            for(int j = (i+1); j<=tumpuk.top; j++){
                if (tumpuk.tampil_urut[i] < tumpuk.tampil_urut[j])
                    tukar(i,j);

            }
        }

    }

    else if(pilih=="desc"){
        for (int i=0; i<tumpuk.top; i++){
            for(int j = (i+1); j<=tumpuk.top; j++){
                if (tumpuk.tampil_urut[i] > tumpuk.tampil_urut[j])
                    tukar(i,j);

            }
        }
    }

    for (int i=tumpuk.top;i>=0;i--)
        cout<<tumpuk.tampil_urut[i]<<endl;


}



int main()
{
    int pil;
    string input;
    tumpuk.top=-1;

    do{

        system("cls");
        cout<<"=====MENU PROGRAM STACK====="<<endl;
        cout<<"1. Push Data Pada Stack \n";
        cout<<"2. Pop Data Pada Stack  \n";
        cout<<"3. Clear Data Pada Stack \n";
        cout<<"4. Tampilkan Data Pada Stack\n";
        cout<<"5. Keluar Dari Program Stack\n\n";

        cout<<"Pilihan : ";
        cin>>pil;

        switch(pil){
        case 1: //untuk mempush (input) stack
            if(isFull()==1)
                cout<<"Stack penuh"<<endl;
             else{
                cout<<"Masukkan data : ";
                cin>>input;
                push(input);
            }break;

        case 2: //untuk mempop (mengeluarkan) stack
            if(isEmpty()==true)
                cout<<"Stack kosong"<<endl;
            else
                pop();
            break;

        case 3: //untuk menghapus atau mengosongkan stack
            clear();
            cout<<"Stack Kosong "<<endl;
            break;

        case 4: //untuk menampilkan data
            if(isEmpty()==true)
                cout<<"Stack Kosong "<<endl;
            else{
                         print();
            }
            break;

        }
    getch ();
    }while(pil!=5);


    return 0;
}

Output:

Keterangan :
1.Saya mempush bilangan dari 4,6,5,8
2.Lalu saya mempopnya , angka 8 terpop karna angka 8 adalah angka terakhir yang saya inputkan(sesuai dengan prinsip stack/tumpukan last in first out).
3.Angka 8 hilang atau terhapus karna telah terpop

2. Program Queue (Antrian) .

Script Program :

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define max 15

using namespace std;

struct queue {//Mendefinisikan queue dengan menggunakan struct

    int head,tail; //head adalah antrian awal dan tail adalah antrian akhir
    string data[max]; //string data untuk menampung queue yg belum diurut
    string urut[max]; //string data untuk menampung stack yg terurut
};queue antri; //queue dideklarasikan menjadi antri


void enqueue(string d){ //fungsi enqueue untuk memasukkan antrian
    antri.head=0;
    antri.tail++;
    antri.data[antri.tail]=d;

    cout<<"data berhasil dimasukkan"<<endl;
}

void dequeue(){ //fungsi dequeue untuk mengeluarkan antrian yg paling awal masuk
    cout<<"data "<<antri.data[antri.head]<<" terambil";
    for(int i=antri.head;i<antri.tail;i++){
        antri.data[i]=antri.data[i+1];

    }
    antri.tail--;
}

bool isFull() //untuk mengecek apakah antrian penuh
{
    if (antri.tail==max-1)
        return true;
    else
        return false;
}

bool isEmpty(){//untuk mengecek apakah antrian kosong
    if (antri.tail==-1)
        return true;
    else
        return false;
}

void clear(){//untuk menhapus antrian
    antri.head=antri.tail=-1;

    cout<<"semua data terhapus "<<endl;
}
void tukar(int a,int b) //untuk menukar nilai a dan b (mengurutkan antrian)
{
    string t;
    t=antri.urut[b];
    antri.urut[b]=antri.urut[a];
    antri.urut[a]=t;
}

void print(){ //untuk menampilkan antrian
    string t;
    string pilih;
    cout<<"Tampilkan Data Yang Belum Terurut:"<<endl<<endl;
    for (int i=0;i<=antri.tail;i++){
        cout<<antri.data[i]<<" ";
        antri.urut[i]=antri.data[i];
    }

    cout<<"\n\nPilih Sorting Ascending atau Descending(asc/desc) :"; cin>>pilih;
    cout<<endl;
    if(pilih=="asc"){
        for (int i=0; i<antri.tail; i++){
            for(int j = (i+1); j<=antri.tail; j++){
                if (antri.urut[i] > antri.urut[j]) tukar(i,j);
            }
        }
    }

    else if(pilih=="desc"){
        for (int i=0; i<antri.tail; i++){
            for(int j = (i+1); j<=antri.tail; j++){
                if (antri.urut[i] < antri.urut[j]) tukar(i,j);
            }
        }
    }

     for (int i=0;i<=antri.tail;i++)
        cout<<antri.urut[i]<<" ";


}



int main()
{
    int pil;
    string input;
    antri.head=antri.tail=-1;

    do{

        system("cls");
        cout<<"=====MENU PROGRAM QUEUE====="<<endl;
        cout<<"1. Enqueue Data Pada Antrian \n";
        cout<<"2. Dequeue Data Pada Antrian  \n";
        cout<<"3. Clear Data Pada Antrian \n";
        cout<<"4. Tampilkan Data Pada Antrian\n";
        cout<<"5. Keluar Dari Program Antrian\n\n";

        cout<<"Pilihan : ";
        cin>>pil;

        switch(pil){
        case 1://untuk meng enqueue/memasukan antrian
            if(isFull()==1)
                cout<<"Antrian penuh"<<endl;
            else{
                cout<<"Masukkan data : ";
                cin>>input;
                enqueue(input);
            }break;

        case 2: //untuk meng dequeue/mengeluarkan antrian yg pling pertama masuk
            if(isEmpty()==true)
                cout<<"Antrian Kosong"<<endl;
            else
                dequeue();
            break;

        case 3: //untuk menhapus smua antrian
            clear();
            cout<<"Antrian Kosong "<<endl;
            break;

        case 4: //untuk menampilkan smua antrian
            if(isEmpty()==true)
                cout<<"Antrian Kosong "<<endl;
            else{
                         print();
            }
            break;

        }
    getch ();
    }while(pil!=5);




    return 0;
}

Output :

Keterangan :

1. Saya meng enqueue(memasukkan antrian) data dimulai dari 5,4,7,8 lalu saya menampilkannya.
2. Lalu saya meng dequeue (mengeluarkan antrian) dan data 5 terambil karena data 5 adalah data yang paling pertama saya inputkan (sesuai dengan prinsip queue/antrian first in first out).
3. kemudian data 5 hilang/dikeluarkan dari antrian karena telah ter dequeue dari antrian 

3. Program Konversi Infix ke Postpix dan hasil operasinya .

Script Program :

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stack>
#include <string.h>
#define max_stack 15


using namespace std;

struct stack1 {//Mendefinisikan stack dengan menggunakan struct

    int topx,topy;
    char x[max_stack]; //string data untuk menampung stack yg tidak berurut
    char y[max_stack];
};stack1 tumpuk; //stack dideklarasikan menjadi tumpuk




void pushx(char d){ //Fungsi push untuk memasukkan stack

    tumpuk.topx++;
    tumpuk.x[tumpuk.topx]=d;

}
void pushy(char d){ //Fungsi push untuk memasukkan stack
    tumpuk.topy++;
   tumpuk.y[tumpuk.topy]=d;

}





void popx(){ // fungsi pop untuk mengeluarkan stack teratas(paling trakhir di input)

    tumpuk.topx--;
}


void popy(){ // fungsi pop untuk mengeluarkan stack teratas(paling trakhir di input)

    tumpuk.topy--;
}


bool isEmpty(){ // untuk mengecek apakah stack kosong
    if (tumpuk.topy==-1)
        return true;
    else
        return false;
}
bool isFull(){ // untuk mengecek apakah stack kosong
    if (tumpuk.topy==max_stack-1)
        return true;
    else
        return false;
}

void convert(int jml,char postfix[15]){
    tumpuk.topx=-1;
    tumpuk.topy=-1;

    for(int i=0; i<jml;i++){
        if(postfix[i]>='0' && postfix[i]<='9'){
            pushx(postfix[i]);
            if(i==jml-1){
                if(tumpuk.topy==1){
                pushx(tumpuk.y[tumpuk.topy]);
                popy();
                pushx(tumpuk.y[tumpuk.topy]);
                popy();
                }
                else{
                    pushx(tumpuk.y[tumpuk.topy]);
                    popy();
                }
            }
        }


        else if(postfix[i]=='+' || postfix[i]=='-' || postfix[i]=='/'|| postfix[i]=='*' ){


            if(isEmpty()==true){
                pushy(postfix[i]);
            }
            else if((tumpuk.y[tumpuk.topy]=='+' || tumpuk.y[tumpuk.topy]=='-') && (postfix[i]=='/' || postfix[i]=='*')){
                pushy(postfix[i]);
            }
            else if((tumpuk.y[tumpuk.topy]=='+' || tumpuk.y[tumpuk.topy]=='-') && (postfix[i]=='-' || postfix[i]=='+')){
                pushx(tumpuk.y[tumpuk.topy]);
                popy();
                pushy(postfix[i]);
            }
            else if((tumpuk.y[tumpuk.topy]=='*' || tumpuk.y[tumpuk.topy]=='/') && (postfix[i]=='/' || postfix[i]=='*') ){
                pushx(tumpuk.y[tumpuk.topy]);
                popy();
                pushy(postfix[i]);
            }

            else if((tumpuk.y[tumpuk.topy]=='*' || tumpuk.y[tumpuk.topy]=='/') && (postfix[i]=='-' || postfix[i]=='+') ){
                pushx(tumpuk.y[tumpuk.topy]);
                popy();
                if((tumpuk.y[tumpuk.topy]=='-' ||tumpuk.y[tumpuk.topy]=='+') &&  (postfix[i]=='-' || postfix[i]=='+') ){
                    pushx(tumpuk.y[tumpuk.topy]);
                    popy();
                    pushy(postfix[i]);
                }

                else{
                        pushy(postfix[i]);
                }

            }

        }

    }

    cout<<"\n\Infix Expression               : ";
    for(int i=0;i<jml;i++){
        cout<<postfix[i]<<" ";
    }

    cout<<"\nHasil Konversi Infix ke Postfix : ";
    for(int i=0;i<=tumpuk.topx;i++){
        cout<<tumpuk.x[i]<<" ";
    }
    cout<<endl;

}
bool isOperator(char ch)
{
    if (ch=='+' || ch=='-' || ch=='*' || ch=='/')
        return true;
    else
        return false;
}
double performOperation(double op1, double op2, char op)
{
    double ans;
    switch(op){
    case '+':
        ans = op2 + op1;
        break;
    case '-':
        ans = op2 - op1;
        break;
    case '*':
        ans = op2 * op1;
        break;
    case '/':
        ans = op2 / op1;
        break;
    }
    return ans;
}


void operasi(){
    int len;
    double x,op1,op2;
    char buffer[15];

    stack <double> s;
    len = strlen(tumpuk.x);
    int j=0;
    for(int i=0; i<len;i++){
        if(tumpuk.x[i]>='0' && tumpuk.x[i]<='9'){
            buffer[j]=tumpuk.x[i];
                x = atof(buffer);
                s.push(x);
        }

        else if(isOperator(tumpuk.x[i])){
            op1 = s.top();
            s.pop();
            op2 = s.top();
            s.pop();
            s.push(performOperation(op1, op2, tumpuk.x[i]));
        }


    }
    cout<<"Hasil : "<<s.top();
}





int main()
{
    char infix[max_stack];
    int jumlah;

    cout<<"=======PROGRAM KALKULATOR SCIENTIFIC SEDERHANA======="<<endl<<endl;

    cout<<"Masukkan Operasi Kalkulator Infix (a+b*c...n) : "; cin>>infix;
    jumlah = strlen(infix);

    if(isFull()==true)
        return 0;
    else{
        convert(jumlah,infix);
        operasi();
    }
    getch();
    return 0;
}
Output :

Keterangan Program :
Maap Program ini hanya bisa mengoperasikan angka 1 sampai 9 tidak bisa mengoperasikan angka puluhan ,ratusan dan lainnya