laporan algoritma dan sturktur data 3

Dokumen Laboratorium Teknik Informatika UMM @ 2015 Laporan Modul Praktikum Algoritma dan Struktur Data By. [ 201410370311127 ] [ Akhmad Zulfikar Al Ghivani ]

Pengampu :

Ilyas Nuryasin S.Kom

Nur Hayatin, SST

Nama:

201410370311127 Akhmad Zulfikar Al

Ghivani

Laporan Praktikum Algoritma & Struktur

Data

Modul 3

STACK AND QUEUE

Daftar Isi :

1. Deskripsi Praktikum

2. Perangkat Lunak

3. Teori Penunjang

4. Prosedur Pelaksanaan

5. Implementasi dan Hasil Praktikum

6. Kesimpulan


Daftar Isi

Deskripsi Praktikum .......................................................................................................... 3

Perangkat Lunak ............................................................................................................... 3

Teori Penunjang ................................................................................................................. 3

Prosedur Pelaksanaan ....................................................................................................... 6

Implementasi dan Hasil Praktikum ................................................................................. 8

Kesimpulan ....................................................................................................................... 19


1. Deskripsi Praktikum

Mahasiswa mampu memahami garis besar dari konsep stack dan queue

Mengetahui perbedaan antara stack dan queue

Mengimplementasikan stack dan queue kedalam program

2. Perangkat Lunak

Peralatan yang digunkan :

Perangkat PC yang terinstal Java

Editor Java (NetBeans IDE 8.0.2)

3. Teori Penunjang

STACK

Merupakan struktur data di mana semua penyisipan dan penghapusan entri dibuat

pada salah satu ujung disebut TOP tumpukkan.

Menggunakan prinsip kerja LIFO (Last In First Out)

Operasi dasar pada Stack

o Insisialisasi (create Stack)

Untuk menginisialiasi tumpukkan , menyisipkan tempat yang nantinya

digunakan untuk menyimpan tumpukkan

o Cek kosong (isEmpty)

Melakukan pengecekkan apakah tumpukkan kosong atau tidak

o Cek penuh

Melakukan pengecekkan apakah tumpukkan penuh atau tidak

o Tambahan stack (PUSH)

Untuk menambah elemen ke dalam tumukkan

o Ambil dari tumpukkan (POP)

Untuk mengambil sebuah elemen dari tumpukkan

Deklarasi Stack


Inisialiasi Stack

Fungsi cek kosong

Fungsi cek penuh

Fungsi cek PUSH

Fungsi cek POP

QUEUE

Aturan queue :

- Penambahan elemen dilakukan di sisi yang berbeda dengan penghapusan

elemen

- Elemen yang dapat dihapus adalah elemen yang berada di posisi terdepan dari

queue

- Untuk operasi penyisipan elemen dilakukan pada posisi belakang dari queue

Skeme pengaksesan : First In , First Out

Contoh :

- Antrian printer


- Antrian tiket bioskop

- Antrian nasabah di teller bank , dll

Seperti halnya stack, queue juga dapat direpresentasikan sebagai array maupun

linked list

Deklarasi queue menggunakan array

Operasi dasar Queue

- Inisialisasi

Untuk menginisialiasi antrian, menyiapkan tempat yang nantinya digunakan

untuk menyimpan antrian

- Cek kosong (isEmpty)

Melakukan pengecekkan apakah antrian kosong atau tidak

- Cek penuh

Untuk mengecek apakan tumpukkan penuh atau tidak


- Enqueue

Untuk menambahkan elemen ke dalam antrian

- Dequeue

Untuk mengambil data dari sebuah antrian

4. Prosedur Pelaksanaan

1. Implementasikan class stack yang ada pada latihan di atas untuk membuat

program Konversi bilangan desimal ke bilangan binner, dengan algoritma

sebagai berikut :

Konversi bilangan desimal ke binner

a. Simpan inputan user ke dalam variabel decimal

b. Bagi variabel decimal dengan anga 2


c. Ambil sisa pembagian variabel desimal, lalu simpan dalam variabel sisa.

Kemudia simpan isi variabel sisi ke dalam stack

d. Ulangi langkah 1 dan 2 selama desimal tidak bernilali 0, Jika variabel decimal

telah bernilai 0 maka lanjutkan ke langkag 5

e. Ambil nilai yang ada di stack. Kemudian tambahkan hasilnya pada variabel

binner

f. Tampilkan isi variabel binner ke layar

g. selesai

2. Buatlah flowchart dan program implementasi dari penggabungan konsep stack

dan queue. Program berupa menu untuk memilih operasi yang dilakukan pada

stack maupun queue. Program akan berakhir jika user memilih menu selesai.

Aturan :

a. Jika operasi remove maka akan menghapus item yang ada pada stack

maupun queue

b. Jika operas add , maka akan menambahkan item pada stack maupun linked

list

c. Jika operasi peek maka akan menampilkan 1 item pada masing-masing

struktur data

d. Jika operasi peer to peer maka akan dilakukan pertukaran data pada stack

dan queue. Item yang ditunjuk oleh top pada stack akan menempati posisi item

yang ditunjuk oleh front pada queue. Sebaliknya item yang ditunjuk oleh front

pada queue akan menampati posisi item yang ditunjuk oleh top pada stack.

3. Ubahlah notasi infix yang dimasukkan oleh user menjadi notasi postfix dengan

memamnfaatkan stack dan queue


5. Implementasi dan Hasil Praktikum

1. Konversi bilangan desimal ke bilangan binner

/*

* To change this license header, choose License Headers in

Project Properties.

* To change this template file, choose Tools | Templates

* and open the template in the editor.

*/

package Nomer_1;

import java.util.EmptyStackException;

import java.util.Scanner;

/**

*

* @author ZULFIKAR

*/

public class DesimalBinerCoba {

int tumpukkan[];

int array_size;

int top;

int peekStack(){

return tumpukkan[top];

}

void pushStack(int data){

if(isFull()){

System.out.println("STACK PENUH!");

tumpukkan = resizing (tumpukkan);

} else{

tumpukkan [++top]=data;

}

}

int popStack() {

if (isEmpty()) {

throw new EmptyStackException();

}

return tumpukkan[top--];

}

int[] resizing (int [] element){

int[] newArr = new int [2*array_size];

System.arraycopy(element, 0, newArr, 0, array_size);

array_size = newArr.length;

return newArr;

}

boolean isEmpty(){

return (top == -1); //paling hanya memastikan ini benar2

kosong

}


boolean isFull(){

return (top == array_size-1);

}

void inisialisasi (int arrSize){

array_size = arrSize;

tumpukkan = new int[array_size];

top = -1;

}

void konverter(int decimal){

int sisa;

do{

sisa = decimal%2;

pushStack(sisa);

decimal = decimal/2;

} while (decimal!=0);

while(!isEmpty()){

int data = popStack();

//data.popStack();

System.out.println(data);

}

}

public static void main(String[] args) {

DesimalBinerCoba DB = new DesimalBinerCoba();

Scanner input = new Scanner(System.in);

DB.inisialisasi(50);

System.out.println("Input : ");

int binner = input.nextInt();

System.out.println("Hasil Biner : ");

DB.konverter(binner);

}

}

ANALISA :

- Di dalamnya menggunakan method standard yang digunakan pada STACK

- Untuk merubah desimal ke binner, dibuat method baru bernama Konverter


- Pertama data desimal akan diambil nilai sisa pembagiannya dengan 2, kemudian

sisa ini akan diambil dan digunakan sebagai data yang akan dimasukkan ke

dalam stack (pushStack). Selama nilai desimal tidak sama dengan 0, maka

pembagian akan terus berlanjut (decimal = decimal/2).

2. Gabungan STACK dan QUEUE

FLOWCHART :


/*


Project Properties.



*/

package Nomer_2;

import java.util.EmptyStackException;


/**

*

* @author ZULFIKAR

*/

public class StackQueue {

int tumpukkan[];

int array_size;

int top;

int Simpanan_St;

int antrian[];

int array_sizeQueue;

int front, rear;

int jumlah_item;

int Simpanan_Que;

int peekStack(){

return tumpukkan[top];

}

int peekQueue(){

return antrian[front];

}

void pushStack(int data){

if(isFull()){

System.out.println("STACK PENUH!");

tumpukkan = resizing (tumpukkan);

} else{

tumpukkan [++top]=data;

}

}

void enqueue(int dataQue){

if(isFullQue()){

System.out.println("Queue Penuh!");

antrian = resizing(antrian);

}

jumlah_item++;

antrian[++rear]=dataQue;

}

int popStack() {

if (isEmpty()) {

throw new EmptyStackException();

}

Simpanan_St = tumpukkan[top];

return tumpukkan[top--];


}

void dequeue(){

int temp = antrian[front];

if(!isEmpty()){

for (int i = 0; i


for (int i = 0; i


//SQ.peekStack();

System.out.println("Peek QUEUE

:\n"+SQ.peekQueue());

//SQ.peekQueue();

break;

case 4:

System.out.println("\nSetelah dilakukan peer

to peer");

SQ.popStack();

SQ.dequeue();

SQ.pushStack(SQ.Simpanan_Que);

SQ.enqueue(SQ.Simpanan_St);

break;

case 5:

System.out.println("Silahkan ketik 'n' lagi!

");

break;

}

SQ.cetak();

System.out.println("Ingin lanjut lagi ? KLIK Y for

yes or N");

ulang = scan.next().charAt(0);

System.out.println("--------------------------------

-------\n");

}while (ulang == 'Y');

}

}


ANALISA :

- Di dalam terdapat method stack dan queue standarnya

- untuk melakukan proses insert data, menggunakan method pushStack pada

stack dan Enqueue pada queue

- untuk melakukan proses remove, pada stack menggunakan method popStack ,

dan menggunakan dequeue pada queue

- untuk melakukan peek, pada stack menggunakan method peekStack, jadi di sini

yang diambil adalah data top dari antrian, sedangkan pada queue menggunakan

peekQueue dan mengambil front dari tumpukkan

- untuk melakukan proses peer to peer, pertama kali yang dilakukan adalah

mengambil data top dan front di Stack dan queue. Data yang sudah diambil tadi

akan di simpan di variabel simpanan_st dan simpanan_que yang nantinya akan

dipanggil lagi. Kemudian data yang sudah disimpan akan dijadikan data sebagai

inputan, namun harus berkebalikan. Jika kita ingin push data ke antrian, maka

yang akan menjadi data masukkan adalah data simpanan dari variabel

simapanan_que, sebaliknya jika kita ingin push data ke tumpukkan, maka yang

akan menjadi data masukkan adalah data simpanan dari variabel simpanan_st.

- END


3. INFIX to POSTFIX

/*


Project Properties.



*/

package Nomer_3;

/**

*

* @author ZULFIKAR

*/


import java.util.Stack;

public class CobaInfixKePosfix {

private boolean isOperator(char c) {

if (c == '+' || c == '-' || c == '*' || c == '/' || c ==

'^') {

return true;

}

return false;

}

private boolean CekUtama(char c1, char c2) {

if ((c2 == '+' || c2 == '-') && (c1 == '+' || c1 == '-

')) {

return true;

} else if ((c2 == '*' || c2 == '/') && (c1 == '+' || c1

== '-' || c1 == '*' || c1 == '/')) {

return true;

} else if ((c2 == '^') && (c1 == '+' || c1 == '-' || c1

== '*' || c1 == '/')) {

return true;

} else {

return false;

}

}

public String convert(String infix) {

System.out.printf("%-8s%-10s%-15s\n", "Input", "Stack",

"Postfix");

String postfix = "";

Stack s = new Stack();

s.push('#');

System.out.printf("%-8s%-10s%-15s\n", "",

format(s.toString()), postfix);

for (int i = 0; i < infix.length(); i++) {

char MasukkanSimbol = infix.charAt(i);

if (isOperator(MasukkanSimbol)) {

while (CekUtama(MasukkanSimbol, s.peek())) {


postfix += s.pop();

}

s.push(MasukkanSimbol);

} else if (MasukkanSimbol == '(') {

s.push(MasukkanSimbol);

} else if (MasukkanSimbol == ')') {

while (s.peek() != '(') {

postfix += s.pop();

}

s.pop();

} else {

postfix += MasukkanSimbol;

}

System.out.printf("%-8s%-10s%-15s\n", "" +

MasukkanSimbol, format(s.toString()), postfix);

}

while (s.peek() != '#') {

postfix += s.pop();

System.out.printf("%-8s%-10s%-15s\n", "",

format(s.toString()), postfix);

}

return postfix;

}

private String format(String s) {

s = s.replaceAll(",", "");

s = s.replaceAll(" ", "");

s = s.substring(1, s.length() - 1);

return s;

}

public static void main(String[] args) {

CobaInfixKePosfix IP = new CobaInfixKePosfix();

Scanner input = new Scanner(System.in);

System.out.print("Masukkan Infix :");

String infix = input.next();

System.out.print("Hasil Postfix :" + IP.convert(infix));

}

}


ANALISA :

- Ketika data dimasukkan, data akan dibaca dan dipisahkan mana yang karakter

yang akan tercetak , mana yang akan di simpan di stack. Misalnya kita

masukkan ( A + B ) / (( C D ) * E ^ F) , semua karakter akan dibaca. Kemudian

akan dipisahkan mana yang termasuk operator matematika, mana yang bukan.

Data pertama yang akan dibaca adalah tanda (, nah ini akan dsimpan di stack,

tidak tercetak, dan postfix belum terbentuk. Baru setelah karakter A mulai

terbaca, maka A ini akan tercetak dan postfix telah terbentuk ditaruh disebelah

kiri. Nah , kemudian ketika tanda operator + dibaca, operator ini akan di

simpan di stack setelah penyimpanan tanda ( tadi, dan ini tidak tercetak. Ketika

B mulai terbaca, karakter tidak disimpan di stack dan langsung di cetak.

Postfix yang terbentuk adalah AB. Setelah tanda ) dibaca, maka operator +

tadi baru tercetak, dan ditampilkan di postfix setelah karakter AB, maka

jadinya AB+ . Begitu seterusnya. Jadi kesimpulannya, dalam hal ini, tanda

kurung pada persamaan infix sangat menentukan hasil operasi postfix yang

terbentuk. Sementara postfix tidak mencantumkan tanda kurung.


6. Kesimpulan

Dari percobaan di atas dapat disimpulkan bahwa ada perbedaan antara single Stack dan

queue, yaitu pada sistem jenis kumpulan datanya. Stack dengan jenis tumpukkan, dan

Queue dengan jenis antrian. Pada Stack, Ketika data berada dalam wadah tumpukkan,

maka data paling atas ini yang bisa diambil terlebih dahulu, ini dinamakan TOP. Pada

queue, ketika data berada dalam suatu antrian yang menuju satu tempat tujuan, maka

data yang pertama kali masuk antrian ini yang bisa keluar duluan, ini dinamakan

FRONT. TOP dan FRONT sangat menentukan bagaimana method pembacaan,

pengambilan, penghapusan, dan penambahan bisa terjadi di dalam Stack dan Queue

laporan algoritma dan sturktur data 3

Documents