Senin, 25 Juni 2012

stack dan queue dengan array


BAB 6
STACK DAN QUEUE DENGAN ARRAY

1.       Pengertian Stack Dan Queue
                 Tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat sepertiada data yang diletakkan di atas data yang lain seperti pada gambar 01. Saat kita ingin mengambil data A, maka data-data yang berada di atasnya haruslah lebih dulu dikeluarkan (di-POP ). Hal ini membuat tumpukan / stack memiliki ciri-ciri Last In First Out ( LIFO ) yang berarti data yang masuk terakhir akan keluar pertama.
                 Sedangkan queue / antrian hampir mirip dengan stack, tapi hanya saja, data yang masuk pertama kali akan keluar pertama kali dari Queue.
( Bisa dilihat pada gambar 02 ).  FIFO ( First In First Out )

E
D
C
B
A
 Gambar 01                    
A
B
C
D
E

                                                        Gambar 02


2.       Penyajian Stack Dan Queue
                 Stack dan/atau Queue dapat disajikan baik dengan Array maupun dengan struct. Pada Array, stack ataupun queue yang disajikan bersifat statis. Ini disebabkan karena jumlah maksimal data pada array sudah ditentukan sejak awal.
Contoh deklarasi stack dengan struct :
Struct stack
{
char data;
stack*next;
};

3.       Operasi Pada Stack Dan Queue
                 Dalam penyajian stack dan queue, ada 2 proses yang terjadi, yaitu pemasukan data (PUSH) dan pengeluaran data (POP). Seperti yang sudah dijelaskan bahwa array itu memiliki jumlah maksimal, maka pada proses PUSH, perlu pengecekan apakah data yang di-PUSH di stack / queue melebihi jumlah maksimal array atau tidak.

Contoh algoritma untuk proses PUSH (stack dan queue ) adalah sebagai berikut :
0. Masukkan inputan ( x )
1. Jika variable cek ( c ) = nilai maksimal array ( max ), kerjakan langkah 2. Jika tidak, kerjakan langkah 3.
2. cetak ”TUMPUKAN PENUH”
3. selama ( c ) kurang dari ( max ), maka      c      c + 1 dan data [c]      x

Contoh algoritma untuk proses POP pada stack adalah sebagai berikut :
0. Jika c = 0, maka kerjakan langkah 2. Jika tidak, lakukan langkah 3.
1. cetak ”TUMPUKAN KOSONG”
2. c      c-1

CONTOH :
Program stack yang mempunyai fungsi proses PUSH dan proses POP di dalamnya. ( stack dideklarasikan dengan array )
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<stdlib.h>

void main()
{
char A[10];
int dpn,blk;
char cek;
int z;
dpn=0;
blk=-1;
do{
clrscr();
printf("1. tambah antrian\n");
printf("2. hapus antrian\n");
printf("3. lihat antrian\n");
printf("4. exit\n");
printf("silahkan berikan pilihan anda: ");
cek=getche();
if (cek!='1' && cek!='2' && cek!='3' && cek!='4')
printf("\n anda salah mengetikan inputan!\n");
else
{
if(cek=='1')
{
if(blk==9)
{
printf("\n maaf antrian penuh\n");
}
blk++;
printf("\n silahkan masukan inputan : ");
A[blk]=getche();
getch();
}
else if(cek=='2')
{
if(dpn>blk)
{
printf("\n maaf antrian kosong\n");

}
for(int v=0;v<=blk;v++)
{
A[v]=A[v+1];
}
blk--;
printf("\n proses penghapusan berhasil");
}
else if (cek=='3')
{
if (dpn>blk)
{
printf("\n maaf antrian kosong\n");

}
printf("\n\n ada %i antrian\n",(blk+1)-dpn);
for(z=0; z<=blk; z++)
printf("| %c |",A[z]);
getch();
}
}
}
while(cek!='4');
}

Tampilan pada layar
Melakukan tambahan antrian

Melakukan hapus antrian

Analisa :
                 Program di atas merupakan program stack yang mempunyai fungsi proses PUSH dan proses POP di dalamnya, stack dideklarasikan dengan array dengan fungsi antrian dimana dalam program tersebut terdapat menu pilihan dintaranya tambah antrian, hapus antrian, lihat antrian dan exit. Ketika menginputkan tambah maka akan terus di tambahkan, dan yang pertama di inputkan yang pertama di eksekusi apabila memilih hapus antrian, seperti contoh di atas, pertama melakukan tambah antian dimana menginputkan 1 2 3 4 5, kemudian di hapus antrian dan di tambahkan lagi nilai 8 dan 9 sehingga hasilnya 3 4 5 8 9.

SOAL LATIHAN :
1. Coba buat program stack (tumpukan) dengan fungsi PUSH dan POP yang
terpisah dari program utama!
#include<stdio.h>
#include<conio.h>

//deklarasi 'STACK' dengan struct dan array
typedef struct STACK
{
int data[5];
int atas;
};

//deklarasi variabel 'tumpuk' dari struct
STACK tumpuk;
void main()
{
clrscr();
int pilihan,baru,i;
//inisialisasi awal
tumpuk.atas=-1;
do
{
clrscr();
printf("1.Push Data\n");
printf("2.Pop Data\n");
printf("3.Print Data\n");
printf("\nPilihan = ");
scanf("%i",&pilihan);
switch(pilihan)
{
case 1:
{
if(tumpuk.atas==5-1)
{
printf("Tumpukan penuh");
getch();
}
else
{
printf("Data yang akan di-push = ");
scanf("%d",&baru);
tumpuk.atas++;
tumpuk.data[tumpuk.atas]=baru;
}
break;
}
case 2:
{
if(tumpuk.atas==-1)
{
printf("Tumpukan kosong");
getch();
}
else
{
printf("Data yang akan di-pop = %d", tumpuk.data[tumpuk.atas]);
tumpuk.atas--;
getch();
}
break;
}
case 3:
{
if(tumpuk.atas==-1)
{
printf("Tumpukan kosong");
getch();
}
else
{
printf("Data = ");
for(i=0; i<=tumpuk.atas; i++)
{
printf("%d ",tumpuk.data[i]);
}
getch();
}
break;
}
default:
{
printf("\nTidak ada dalam pilihan");
}
}
}while(pilihan>=1 && pilihan<=3);
getch();
}

Tampilan pada layar
Melakukan push
Melakukan pop
Hasil setelah melakukan pop
Analisa :
                 Program di atas merupakan program tumpukan dengan fungsi push dan pop. Dalam program di atas user melakukan push sebanyak 4 kali, nialai yang di inputkannya yaitu 9 8 3 5, kemudian melakukan pop sebanyak 2 kali sehingga hasilnya menjadi 9 8. Karena pada tumpukan ini nilai yang terakhir di inputkan dan setelah melakukan pop maka nilai yang terakhir di inputkan tersebut yang pertama di eksekusi, sehingga nilai yang terakhir di inputkan tersebut hilang atau di hapus.

2. Buat program yang sejenis untuk Queue / antrian.
# include <iostream.h>
# include <conio.h>

class Linked_list_Queue
{
      private:
      struct node {
            int data;
            node *next;
            };
      node *rear;
      node *entry;
      node *print;
      node *front;

      public:
      Linked_list_Queue( );

      void Delete( );
      void Insert( );
      void print_list( );
      void show_working( );
};

Linked_list_Queue::Linked_list_Queue ( )
{
      rear=NULL;
      front=NULL;
}

void Linked_list_Queue::Insert( )
{
      int num;
      cout<<"\n\n\n\n\n\t Masukkan angka dalam Queue : ";
      cin>>num;
      entry=new node;
      if(rear==NULL)
      {
            entry->data=num;
            entry->next=NULL;
            rear=entry;
            front=rear;
      }
      else
      {
            entry->data=num;
            entry->next=NULL;
            rear->next=entry;
            rear=entry;
      }
      cout<<"\n\n\t *** "<<num<<" sudah masuk dalam Queue."<<endl;
      cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
      getch( );
}

void Linked_list_Queue::Delete( )
{
      if(front==NULL)
            cout<<"\n\n\n\t ***  Error : Queue is empty. \n"<<endl;
      else
      {
            int deleted_element=front->data;
            node *temp;
            temp=front;
            front=front->next;
            delete temp;
            cout<<"\n\n\n\t *** "<<deleted_element<<" dihapus dari Queue."<<endl;
      }
      cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
      getch( );
}

void Linked_list_Queue::print_list( )
{
      print=front;
      if(print!=NULL)
cout<<"\n\n\n\n\n\t Angka-angka yang ada dalam Queue adalah : \n"<<endl;
      else
            cout<<"\n\n\n\n\n\t *** Tidak ada yang ditampilkan. "<<endl;
      while(print!=NULL)
      {
            cout<<"\t "<<print->data<<endl;
            print=print->next;
      }
      cout<<"\n\n\n\t\t Pres any key to return to Menu. ";
      getch( );
}

void Linked_list_Queue ::show_working( )
{
      char Key=NULL;
      do
      {
            clrscr( );
            gotoxy(5,5);
            gotoxy(10,8);
            cout<<"Pilih salah satu menu :"<<endl;
      gotoxy(15,10);
            cout<<"- Press \'I\' to Masukkan data dalam Queue"<<endl;
            gotoxy(15,12);
            cout<<"- Press \'D\' to Hapus data dari Queue"<<endl;
            gotoxy(15,14);
            cout<<"- Press \'P\' to Tampilkan data dari Queue"<<endl;
            gotoxy(15,16);
            cout<<"- Press \'E\' to Exit"<<endl;

            Input:

            gotoxy(10,20);
            cout<<"                      ";
            gotoxy(10,20);
            cout<<"Masukkan Pilihan : ";
            Key=getche( );
            if(int(Key)==27 || Key=='e' || Key=='E')
                  break;
            else if(Key=='i' || Key=='I')
                  Insert( );
            else if(Key=='d' || Key=='D')
                  Delete( );
            else if(Key=='p' || Key=='P')
                  print_list( );
            else
                  goto Input;
      }
      while(1);
}

int main( )
{
      Linked_list_Queue  obj;
      obj.show_working( );
      return 0;
}





Tampilan pada layar
Tampilan menu
Hasil proses memasukan data dalam queue








Proses penghapusan data dari queue








Hasil setelah melakukan penghapusan dari queue
Analisa :
                 Program di atas merupakan program queue atau antrian. Pada program di atas sintaksnya beda dengan program sebelumnya, akan tetapi fungsinya sama. Dalam program di atas terdapat pilihan menu masukan data dalam queue, hapus data dari queue, tampilkan data dari queue dan exit. Pada program di atas terdapat 5 kali inputan dengan nilai 1 2 3 4 5, kemudian melakukan penghapusan sehingga hasilnya menjadi 3 4 5, karena pada queue ini nilai yang pertama di inputkan maka akan pertama di hapus, sehingga hasilnya seperti pada contoh di atas.

CONTOH :
Program stack yang mempunyai fungsi proses PUSH dan proses POP terpisah dan stack dideklarasikan dengan struct.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct tumpukan
{
char data;
tumpukan*next;
};
tumpukan*atas;
tumpukan*bawah;
tumpukan*baru;
tumpukan*hapus;
tumpukan*bantu;
void push()
{
baru=new tumpukan;
fflush(stdin);
printf("Data yg ingin dimasukkan -> ");
scanf("%c",&baru->data);
baru->next=NULL;
if(atas==NULL)
{
atas=baru;
bawah=baru;
}
else
{
baru->next=atas;
atas=baru;
}
}
void pop()
{
if(atas!=NULL)
{
if(atas==bawah)
{
delete atas;
atas=NULL;
}
else
{
hapus=atas;
atas=atas->next;
delete hapus;
}
}
else
{
printf("tumpukan kosong\nTekan enter untuk melanjutkan...");
getch();
}
}
void show()
{
bantu=atas;
while(bantu!=NULL)
{
printf("| %c |\n",bantu->data);
bantu=bantu->next;
}
printf("\ntekan enter untuk melanjutkan...\n");
getch();
}
void main()
{
clrscr();
int pil;
do
{
clrscr();
printf("program tumpukan\n");
printf("==================\n");
printf("1.push\n");
printf("2.pop\n");
printf("3.tampil\n");
printf("4.keluar\n");
printf("Masukkan pilihan : ");scanf("%i",&pil);
switch(pil)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
show();
break;
}
}
while(pil!=4);
}

Tampilan pada layar
Melakukan push






Setelah melakukan pop


Analisa :
                 Program di atas merupakan program stack yang mempunyai fungsi proses PUSH dan proses POP terpisah dan stack dideklarasikan dengan struct dengan fungsi tumpukan. Dalam program di atas terdapat menu pilihan diantaranya push, pop, tampil dan keluar. Contoh program di atas melakukan push diantaranya menginputkan 2 3 4 1 0, kemudian melakukan  pop, pada program tumpukan ini nilai yang terakhir di inputkan maka nilai tersebut yang di eksekusi sehingga seperti pada contoh program di atas melakukan 2 kali pop sehingga hasilnya menjadi 2 3 4 karena 1 dan 0 nya di hapus.

SOAL LATIHAN
1.      Program queue dengan memakai struct
#include <stdio.h>
#include <conio.h>
#define MAX 6
typedef struct
{
int data [MAX];
int head;
int tail;
}
Queue;
Queue antrian;
void Create()
{
antrian.head=antrian.tail=-1;
}

int IsEmpty()
{
if(antrian.tail==-1)
return 1;
else
return 0;
}
int IsFull()
{
if(antrian.tail==MAX-1)
return 1;
else
return 0;
}
void Enqueue(int data)
{
if(IsEmpty()==1)
{
antrian.head=antrian.tail=0;
antrian.data[antrian.tail]=data;
printf("%d masuk !",antrian.data[antrian.tail]);

void Tampil();
{
if(IsEmpty()==0)
{
for(int i=antrian.head;i<=antrian.tail;i++)
{
printf("%d ",antrian.data[i]);
}
}
else
 printf("Data Kosong !\n");
     }
}
else
if(IsFull()==0)
 {
antrian.tail++;
antrian.data[antrian.tail]=data;
 printf("%d masuk !", antrian.data[antrian.tail]);
            }
}
int Dequeue()
{
int i;
int e=antrian.data[antrian.head];

for(i=antrian.head;i<=antrian.tail-1;i++)
{
antrian.data[i]=antrian.data[i+1];
}
antrian.tail--;
return e;
}
void Clear()
{
antrian.head=antrian.tail=-1;
printf("Data Clear");
}

void Tampil()
{
if (IsEmpty()==0)
{
for (int i=antrian.head;i<=antrian.tail; i++)
{ printf("%d ",antrian.data[i]);
}
}
else
{
printf("Data Kosong\n");
}
}
void main()
{
int pil;
int data;
Create();
 do
{
 clrscr();
printf ("\n MENU PILIHAN PROGRAM QUEUE\n");
printf ("1. Enqueue\n");
printf ("2. Dequeue\n");
printf ("3. Tampil\n");
printf ("4. Clear\n");
printf ("5. Keluar\n");
printf ("Masukkan Pilihan Anda : ");
scanf("%d",&pil);

switch(pil){
case 1:
printf("Data : ");
scanf("%d",&data);
Enqueue(data);
break;

case 2:
printf("Elemen yang keluar : %d", Dequeue());
break;

case 3:
Tampil();
break;

case 4:
Clear();
break;
case 5:

break;
}
getch();
} while(pil!=5);
}
Tampilan pada layar
Insert antrian queue
Delete antrian queue




Hasil setelah di delete
Analisa :
               Program di atas merupakan program queue dengan menggunakan struck dalam sintaksnya. Program ini tidakbeda dengan program sebelumnya dimana dalam program tersebuat ada menu pilihan diantaranya insert antrian queue, delete antrian queue, display antrian dan exit. dalam contoh program di atas user menginputkan 4 kali insert antrian queue dan 2 kali delete antrian queue. Yang di inputkan yaitu 9 8 3 2 kemudian di delete menjadi 2 3, karena pada program queue ini inputan pertama yang di inputkan dialah yang pertama kali di eksekusi, sehinghga hasilnya menjadi 2 dan 3.
2.      Program untuk memindahkan piringan.
#include <stdio.h>
#include <iostream.h>
#include <conio.h>

void Hanoi(int n,char asal,char bantu,char tujuan) // pindahkan piringan ke n
{ // dari asal menuju tujuan
// melalui bantu
if (n == 0) return;
Hanoi(n-1,asal,tujuan,bantu); //pindahkan piringan ke n-1
// dari asal ke bantu melalui
//tonggak tujuan
printf("Pindahkan piringan ke %d ke dari %c ke %c\n",n,asal,tujuan);
Hanoi(n-1,bantu,asal,tujuan); //pindahkan piringan ke n – 1
// dari bantu menuju tujuan
// melalu asal
}
int main(void)
{
int n;
printf("Jumlah piringan ? ");
scanf("%d",&n);
Hanoi(n,'a','b','c');
return 0;
}

Tampilan pada layar
Analisa :
           Program di atas digunakan untuk memindahkan piringan, dimana dalam memindahkan piringan  tersebut setiap kalinya hanya satu piringan yang boleh di pindahkan, tetapi tidak ada piringan besar di atas piringan kecil dan tiang c nerupakan perantaranya, untukm lebih jelasnya lagi bisa di lihat pada contoh di atas.

1 komentar:

  1. makasih mass infonya..
    info seputar bola, prediksi bola ter-update..
    berita bola TERBARU DAN TERPERCAYA hanya ada di Bola368.net
    Kunjungi juga Bola368.org , Anda puas Kami pun senang.!

    BalasHapus