header ads

PRAKTIKUM ALGORITMA DAN STRUKTUR DATA BAB III

Dankus - 9:09 AM
Pengertian STACK
Stack bisa diartikan sebagai tumpukan. Tumpukan juga dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada 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.
E
D
C
B
A
    Gambar 01

Pada proses single stack, terdapat tiga proses utama, yaitu :
-          Inisialisasi
-          PUSH (Insert, Masuk, Simpan, Tulis)
-          POP (Delete, Keluar, Ambil, Baca, Hapus)

Stack adalah list linier yang dikenali elemen puncaknya (TOP) dan memiliki autan penyisipan dan penghapusan elemennya tertentu (LIFO).
Struktur data ini banyak dipakai dalam informatika, misalnya untuk merepresentasikan :
·         Pemanggilan prosedur
·         Perhitungan ekspresi aritmatika
·         Rekursifitas
·         Backtracking dan algoritma lanjut lainnya.
Inisialisasi adalah proses awal untuk menyimpan indeks pada stack. PUSH adalah proses penginputan data pada stack. POP adalah proses mengeluarkan elemen TOP pada stack.

Definisi S adalah Stack dengan elemen ElmtS, maka definisi fungsional stack adalah :
CreatEmpty : → S {Membuat sebuah stack kosong}
IsEmpty       : S → Boolean {Tes stack kosong, true jika benar}
IsFull           : S → Boolean {Tes stack penuh, true jika stack penuh}
Push             : ElmtS x S → S {Menambahkan sebuah elemen ElmtS sebagai
                       TOP, TOP berubah nilainya}
Pop               : S → S x ElmtS {Mengambil nilai elemen TOP, sehingga TOP
                       yang baru adalah elemen yang dating sebelum elemen TOP,
                       mungkin stack menjadi kosong}


 Hasil dan Pembahasan

Pengimplementasian Stack :

/* File : boolean.h */
#ifndef BOOLEAN_H
#define BOOLEAN_H
#define boolean unsigned char
#define true 1
#define false 0
#endif


/* File : stack.h */
#ifndef stack_H
#define stack_H

#include "boolean.h"
#define Nil 0

typedef int infotype;
typedef int address;

typedef struct {
      infotype*T;
      address TOP;
      int Size;
}Stack;

#define Top(S) (S).TOP
#define InfoTop(S) (S).T[(S).TOP]
#define Size(S) (S).Size

boolean IsEmpty(Stack S);
boolean IsFull(Stack S);

void CreateEmpty(Stack*S, int Size);
void Destruct(Stack*S);

void Push(Stack*S, infotype X);
void Pop(Stack*S, infotype*X);

#endif


/* File : stack.c */
#include "boolean.h"
#include "stack.h"

boolean IsEmpty (Stack S) {
      return (Top (S) == Nil);
}

boolean IsFull (Stack S) {
      return (Top (S) == Size(S)+1);
}

void CreateEmpty(Stack * S, int Size) {
      (*S).T = (int *) malloc((Size+1) * sizeof(int));
      Top(*S) = Nil;
      Size(*S) = Size;
}

void Destruct(Stack *S) {
      free ((*S).T);
}

void Push(Stack * S, infotype X) {
      Top(*S)++;
      InfoTop(*S) = X;
}

void Pop(Stack* S, infotype * X) {
}



/* File : mstack.c */
#include "stack.h"
#include "stack.c"
#include <stdio.h>
int main () {
      Stack S;
      infotype X;
     
      printf ("PROGRAM STACK \n");
      CreateEmpty(&S,100);
      printf("size stack : %d \n", Size(S));
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
      Push(&S,3);
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
      Push(&S,8);
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
      Pop(&S,9);
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
     
      Destruct(&S);
      return 0;
}








Tampilan Program :


Analisis :
Pada program di atas, terdapat 4 file yaitu boolean.h, stack.h, stack.c dan mstack.c. Program diatas juga merupakan program untuk menampilkan nilai top dan infonya dengan array statis, artinya nilai top dan infonya sudah ada. 


Tugas 

  1. Diberikan sebuah ekspresi aritmatika postfix dengan operator [‘.’;’:’;’+’;’-‘;’^’] dan operator mempunyai prioritas (prioritas makin besar, artinya makin tinggi) sebagai berikut :

Operator
Arti
Prioritas
^
Pangkat
3
/ *
Bagi, kali
2
+ -
Tambah, kurang
1

Contoh :
AB.C/                          (A.B)/C
ABC^/DE*+AC*-      (A/(B^C)+(D*E))-(A*C)
Tuliskan programnya dan gunakan stack?
Jawaban :
/* File : latihan1.cpp */
 #include<stdio.h>
 #include<conio.h>
 #include<string.h>
 #include<math.h>

 #define oper(x) (x=='+' || x=='-' || x=='*' || x=='/' || x=='^')

 char in[30], post[30], stack[30];
 int top=-1;

 void push(char x)
 {
 stack[++top]=x;
 }

 char pop()
 {
     return stack[top--];
 }

 int precedence(char c)
 {
  if (c=='+' || c=='-')
  return 1;
     if (c=='*' || c=='/')
  return 2;
     if (c=='^')
  return 3;
 }

 main()
 {
     char c;
     int l,i,j=0,st1[20],k,h,f,eval,s,N;

     printf("PROGRAM STACK ARITMATIKA POSTFIX \n");
     printf("________________________________ \n");
     printf("\n");
       printf("Masukkan notasi infix : ");
     scanf("%s",&in);
     l=strlen(in);

     for(i=0;i<=l;i++)
     {
  if(oper(in[i]))
  {
      post[j++]=' ';
      while(precedence(in[i])<precedence(stack[top]))
      {
   post[j++]=stack[top];
   pop();
   post[j++]=' ';

      }
      push(in[i]);
  }
  else if(in[i]=='\0')
  {
      while(top!=-1)
      {
   post[j++]=' ';
   post[j++]=stack[top];
   pop();
      }
  }
  else
      post[j++]=in[i];
     }
     post[j]='\0';
     printf("Hasil notasi postfix : %s\n",post);
     i=0;top=-1;f=0;k=0;
     while(i<j)
     {
  if(oper(post[i]))
  {
      f=1;
      c=post[i];
      eval=0;
      switch(c)
      {
      case '+':
   eval=st1[top-1]+st1[top];
   break;
      case '-':
   eval=st1[top-1]-st1[top];
   break;
      case '*':
   eval=st1[top-1]*st1[top];
   break;
      case '/':
   eval=st1[top-1]/st1[top];
   break;
        case '^':
   eval=st1[top-1]*st1[top-1];
   break;
      }
      top--;
      st1[top]=eval;
  }
  else if(post[i]==' ')
  {
      if(f==0)
      {
   h=i-k;
   s=0;
   while(post[h]!=' ')
   {
       N=(int)post[h];
       N=N-48;
       s=s+N*(pow(10,(k-1)));
       k--;
       h++;
   }
   st1[++top]=s;
      }
      k=0;
  }
  else
  {
      k++;
      f=0;
  }
  i++;
     }
     printf("\n");
       printf("Hasil dari operasi perhitungan : %d\n",st1[top]);
 getch();
 return 0;
}     Push(&S,8);
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
      Pop(&S,9);
      printf("Nilai top dan infonya : %d dan %d\n", Top(S), InfoTop(S));
     
      Destruct(&S);
      return 0;
}
           

Tampilan Program :



Analisis :

Pada program di atas juga menggunakan switch untuk mengatur case agar operator yang diinputkan dapat dihitung dengan benar. Operator yang digunakan disini yaitu pangkat, kali, bagi, tambah dan kurang. Dengan prioritas sebagai berikut pangkat=3, kali,bagi=2, tambah,kurang=1

 Tugas 2 

2.      Legenda di Hanoi, tentang kisah pendeta Budha bersama murid-muridnya. Bagaimana memindahkan seluruh priringan (3 piringan) tersebut ke sebuah tiang yang lain (dari A ke B); setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Ada tiang perantara C. Bagaimana memindahkan seluruh piringan (3 piringan) tersebut ke sebuah tiang yang lain (dari A ke B); setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Ada tiang perantara C. Tuliskan program untuk memindahkan piringan tersebut :


Jawaban :

/* File : latihan2.cpp */
void MenaraHanoi(int N, char asal, char bantu, char tujuan);


int main()

{
    int piringan;
    cout<< "\nPROGRAM MENARA HANOI\n";
    cout<< "--------------------\n\n";
    cout<< "Banyaknya piringan: ";
    cin >> piringan;
    cout<< endl;
    MenaraHanoi(piringan,'A','B','C');
    return 0;
}

void MenaraHanoi(int N, char asal, char bantu, char tujuan)
{
    if( N == 1)
        cout<<"Piringan 1 dari "<<asal<< " ke " << tujuan <<endl;

    else
        {
            MenaraHanoi(N-1,asal,tujuan, bantu);
            
            cout<<"Piringan " << N <<" dari " << asal << " ke " << tujuan<<endl;

            MenaraHanoi(N-1, bantu, asal, tujuan);

        }

}

Tampilan Program :



Analisis :

Di sini kita menggunakan 2 void yaitu untuk penginputan jumlah piringan serta pemanggilan proses pemindahan piringan dan void yang kedua untuk memindahkan piringan dari tiang yang satu ke tiang lainnya. Dengan proses pengulangan if. Dalam program ini saya menggunakan 3 piringan.










Post a Comment

0 Comments