IMPLEMENTASI STACK PADA PROGRAM KOMPUTER

BAB I

PENDAHULUAN

1.1 Latar Belakang

Pemakaian struktur data yang tepat di dalam proses pemrograman akan

menghasilkan algoritma yang lebih jelas dan tepat, sehingga menjadi program

secara keseluruhan lebih efisien dan sederhana seperti stack merupakan bagian

dari struktur data yang dikategorikan ke dalam bentuk linier data, dimana operasi

pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya.

Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu

hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan

ruang data dan aplikasi lain. Stack bersifat LIFO (Last In First Out) dan benda

yang terakhir masuk ke dalam stack akan menjadi benda pertama yang

dikeluarkan dari stack itu.

Dalam prosesnya, untuk memasukkan sebuah data ke dalam stack atau

dengan kata lain ke bagian atas dari sebuah tumpukan digunakan perintah push.

Pada stack jarang sekali dilakukan operasi traversal, karena keunikan stack justru

pada operasi yang hanya menyangkut elemen TOP (atas).

Struktur ini sering dipakai dalam informatika misalnya untuk

merepresentasikan pemanggilan prosedur, perhitungan ekspresi aritmatika,

rekursifitas, dan backtracking. Satu hal yang perlu diingat adalah bahwa di dalam

suatu tumpukan dapat menambah (menyisipkan) data dan mengambil

(menghapus) data lewat ujung yang sama yang disebut sebagai ujung atas

tumpukan.

Penyajian stack bisa menggunakan array, namun kurang tepat. Array bisa

digunakan kalau elemen stack tidak melebihi batas maksimum. Tipe yang bisa

digunakan adalah record.

Manipulasi dengan menggunakan record mempunyai dua medan, yaitu

medan penyimpanan elemen tumpukan dan medan pencatat posisi ujung atas

tumpukan. Stack dapat diimplementasikan sebagai representasi berkait atau

kontinyu (dengan tabel fix). “TOP“ merupakan pintu untuk keluar masuknya

elemen – elemen stack.

Halaman|1

1.2 Rumusan Masalah

Berdasarkan latar belakang tadi, maka penyusun menemukan beberapa

permasalahan yang kiranya akan menjadi bahasan pada penyusunan makalah ini,

diantaranya yaitu :

1. Apa pengertian dari stack ?

2. Apa saja operasi-operasi dan fungsi dasar pada stack ?

3. Bagaimana deklarasi stack pada Bahasa Pemrograman C++ ?

4. Bagaimana implementasi Stack pada program komputer ?

1.3 Tujuan dan Manfaat Penyusunan

Tujuan makalah ini adalah untuk mengetahui lebih jauh tentang

penggunaan operasi stack dalam struktur data. Sehingga tentunya akan dapat

memberikan sebuah manfaat bagi diri kita maupun orang lain. Dengan

penyusunan makalah ini, semoga ada manfaat yang dapat kita rasakan, terutama

bagi rekan-rekan yang belajar tentang struktur data dan bagaimana implementasi

dari struktur data tersebut dalam suatu aplikasi sederhana.

Halaman|2

BAB II

PEMBAHASAN

2.1 Sejarah Stack

Stack pertama kali diusulkan pada tahun 1946, oleh desain komputer Alan Turing M. (yang menggunakan istilah "bury" dan "unbury") sebagai sarana menelepon dan kembali dari subroutines. Subroutines sudah dilaksanakan di Konrad Zuse Z4 pada tahun 1945. Klaus Samelson dan Friedrich L. Bauer dari Universitas Teknik Munich mengusulkan gagasan pada tahun 1955 dan mengajukan paten pada tahun 1957. Konsep yang sama dikembangkan, secara mandiri, dengan Australia Charles Leonard Hamblin di paruh pertama tahun 1957....................................................................................

2.2 Definisi Stack

Dalam dunia komputer, penggunaan stack atau tumpukan merupakan salah satu komponen penting untuk menjamin proses penanganan suatu data disamping hal lain seperti Queue (antrian), linked list, dan tree.

Definisi 1 : “ Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya. ”“ Stack adalah suatu konsep pemrograman mengenai tumpukan beberapa data.”“ Stack adalah suatu konsep dimana beberapa data (elemen) dengan tipe yang sama berada pada sebuah tumpukan.”

Gambar 1. Ilustrasi Stack 1

Halaman|3

Gambar 2. Ilustrasi Stack 2

Definisi 2 :Stack dilambangkan dengan huruf S.Sedangkan elemen stack dilambangkan dengan S1 , S2, S3, ... , ST.Diberikan suatu himpunan yang terurut himpunan sebagai S = {S1, S2, ......., ST}, T pada anggota S merupakan linear order, sehingga stack dari himpunan tersebut memiliki informasi sebagai berikut: 1. Elemen puncak dari stack dalam himpunan S dikatakan sebagai TOP,

Sehingga : TOP(S) = ST

2. Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL, Sehingga :NOEL(S)= T, dimana himpunan dari S tersebut dapat disusun sebagai : S = {S1, S2, .........., SNOEL}

Secara formal sebuah stack bertipe T didefinisikan sebagai sebuah barisan berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasinya berikut:

1) Inisiasi stack menjadi kosong.2) Mencari tahu status stack kosong atau tidak.3) Mencari tahu stack penuh atau tidak.4) Mencari panjang stack (jumlah elemen stack).5) Memasukkan elemen baru pada stack, yaitu top stack jika stack tidak penuh.6) Jika stack tidak kosong, mengambil elemen teratas(top stack).

Dari dua definisi tersebut di atas maka suatu stack dapat digambarkan sebagai berikut :1. Suatu stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan TOP(S) = undefined.

Halaman|4

S2. Untuk stack yang bukan kosong, maka akan memiliki informasi seperti yang digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan TOP(S) = Merah.

S3. Untuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru seperti ditunjukan pada gambar di bawah ini :

SElemen-elemen yang berada dalam stack tersebut di atas, memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau yang masuk paling belakang akan memiliki prioritas untuk keluar paling depan.Suatu stack dapat digambarkan sebagai suatu array (larik) berdimensi satu yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika suatu stack didefinisikan dengan n elemen maka dapat dikatakan jumlah maksimum dari stack atau NOEL(S) nya adalah n, sehingga penambahan elemen stack yang ke n+1 tidak diperkenankan atau stack tersebut dalam kondisi overflow. Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu NOEL(S) dari stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas stack tersebut

Halaman|5

akan mengakibatkan stack tersebut dalam kondisi underflow. Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer.

Jadi, 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. ”

2.3 Deklarasi Stack dengan Struct Pada Bahasa Pemrograman C++Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain. Deklarasi tersebut :

#define MAX_STACK 10Typedef struct STACK{

int isi[MAX_STACK];int Top;

};STACK S;

Fungsi : Top yang menunjuk posisi data terakhir (top)

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang. 

Isi : Elemen yang berisi data yang ada dalam stack. Bagian ini lah yang berbentuk array.

Max_stack yaitu variable yang menunjuk maksimal banyaknya elemen dalam stack. Nilai yang diizinkan adalah 0 s.d. max-stack. Jika array diakses dari indeks kecil (1)  ke arah indeks besar (max_stack), maka nilai ini akan bertambah 1 bila ada penambahan elemen; dan berkurang 1 jika ada penghapusan elemen.

S adalah alias dari STACK.

2.4 Operasi-Operasi Pada Stack1. Push (Operator Pemasukkan Elemen)

Push digunakan untuk menambah item pada stack pada tumpukan paling atas. Operasi push pada stack yang menggunakan array. Langkah operasi push dalam array adalah dengan :

Periksa apakah stack penuh. Jika bernilai false/0 (tidak penuh) maka proses push dilaksanakan dan jika pemeriksaan ini bernilai true/1 (stack penuh), maka proses push digagalkan.

Proses push-nya sendiri adalah dengan menambah field top dengan 1, kemudian elemen pada posisi top diisi dengan elemen data baru.

Notasinya : PUSH(E,S)Void PUSH(int X, STACK S){

Halaman|6

S.Top++;S.isi[S.Top] = X;

}

Artinya : menambahkan elemen E ke dalam stack S.Elemen yang baru masuk ini akan menempati posisi TOP.Jadi : TOP(PUSH(E,S)) = EAkibat dari operasi ini jumlah elemen dalam stack akan bertambah, artinya NOEL(S) menjadi lebih besar atau stack menjadi tidak kosong (ISEMPTY(PUSH(E,S)) = false).

2. Pop (Operator Penghapusan Elemen)

Pop digunakan untuk mengambil/ menghapus item pada stack pada tumpukan paling atas. Operasi pop pada stack yang menggunakan array. Langkah operasi pop pada stack yang menggunakan array adalah terlebih dahulu memeriksa apakah stack sedang keadaan kosong, jika tidak kosong maka data diambil pada posisi yang ditunjuk oleh posisi top, kemudian simpan dalam variable baru dengan nama data, kemudian posisi top – 1, kemudian nilai pada variable data di-return-kan ke function.

Notasinya: POP(S)

Void POP(STACK S){S.isi[S.Top] = 0;S.Top--;

}

Elemen yang keluar dari dalam stack adalah elemen yang berada pada posisi TOP. Akibat dari operasi ini jumlah elemen stack akan berkurang atau NOEL(S) berkurang dan elemen pada posisi TOP akan berubah. Operator POP ini tidak dapat digunakan pada stack kosong, artinya : POP(CREATE(S)) = error condition

Contoh Program Stack dengan C++ :

Halaman|7

#include<iostream.h>#include<stdio.h>#include<conio.h>#include<windows.h>

#define MAX 5#define true 1#define false 0

char stack[MAX];int top;

void init(void);int full(void);int empty(void);char pop(void);void push(char info);void baca(void);

void main(){char pilih,elm;cout<<"Demo Operasi Single Stack"<<endl;init();do{cout<<"OPERASI SINGLE STACK :"<<endl;cout<<"[1]PUSH"<<endl;cout<<"[2]POP"<<endl; cout<<"[3]BACA DATA"<<endl;cout<<"[4]KELUAR"<<endl;cout<<"pilihan:";cin>>pilih;switch(pilih)

{case '1':cout<<"PUSH-->";cin>>elm;push(elm);break;case '2':elm=pop();cout<<"pop"<<elm;break;case '3':baca();break;case '4':exit (EXIT_SUCCESS);default:cout<<"Salah pilih..."<<endl;}cout<<endl;}while(pilih!='5');}

void init(void){top=0;}

void push(char info){if(full()!=true){top++;stack[top]=info;}elsecout<<"Stack overflow..."<<endl;}char pop(void){

char info;if(empty()!=true){info=stack[top];top--;return(info);}elsecout<<"Stack underflow..."<<endl;}

int full(void){if(top==MAX)return(true);elsereturn(false);}

int empty(void){if(top==0)return(true);elsereturn(false);}

void baca(void){ int i;cout<<"Isi data stack:"<<endl;if(top>0){for(i=1;i<=top;i++)cout<<stack[i];}elsecout<<"(Kosong)";cout<<endl;getch();}

Halaman|8

Fungsi dalam Stack : Fungsi init : fungsi yang digunakan untuk inisialisasi atau membuat stack baru yang

masih kosong. Fungsi full : digunakan untuk mengetahui stack penuh atau tidak. Fungsi empty : digunakan untuk mengetahui stack kosong atau tidak. Fungsi push : digunakan untuk menambahkan data ke dalam stack. Penambahan data

tidak bisa dilakukan apabila stack sudah penuh. Urutan perintahnya adalah: menambahkan nilai top dan menambahkan data pada posisi nilai top.

Fungsi pop :  digunakan untuk mengeluarkan data teratas stack dengan syarat bahwa stack tidak kosong.Urutan perintahnya adalah : menghapus data pada posisi nilai top dan menurunkan nilai top.

2.5 Impelementasi STACK Pada Program KomputerLogika stack digunakan untuk menyelesaikan berbagai macam masalah. Antara lain

digunakan pada compiler, operating system dan dalam program-program aplikasi komputer. Berikut ini beberapa contoh implementasi stack pada program komputer, yaitu :

1. Program Notasi Postfix      Bentuk aplikasi stack kali ini adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix.Contoh :Misal diberikan ekspresi aritmatik : A + B ;Maka bentuknya dalam notasi postfix menjadi : AB+

Urutan (prioritas) dari operator adalah :1. Perpangkatan (^)2. Perkalian (*) atau Pembagian (/)3. Penjumlahan (+) atau Pengurangan (-)

Aturan yang digunakan dalam proses transformasi tersebut adalah :1. Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan.2. Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam

stack.3. Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai

dari simbol "(" yang pertama ditemukan dalam stack.4. Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol

(operator) yang berada pada posisi top dalam stack.a) Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi

top, maka top stack di-pop keluar sebagai output dan simbol yang baru di-push ke dalam stack.

b) Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.

5. Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output.

6. Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.

Contoh :

Misal diberikan sebuah ekspresi aritmatik dengan bentuk sbb:( (A + B) * C / D + E ^ F ) / G ;

Selanjutnya akan dicari bentuk ekspresi diatas dalam notasi postfix.

Halaman|9

Proses yang dilakukan dapat digambarkan dalam tabel berikut :

Jadi ekspresi aritmatik : ( ( A + B ) * C / D + E^F ) / G ; Dalam notasi postfix menjadi : AB+D*C/EF^+G/

2. Matching Parentheses (Pengecekan Tanda Kurung)      Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah :

1. Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.2. Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push

ke dalam stack.3. Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.4. Jika stack kosong terjadi kesalahan berarti : ada simbol ")", tetapi tidak ada

simbol "(" yang seharusnya mendahului.5. Jika stack tidak kosong artinya ada pasangannya dan langsung di-POP keluar   

stack.

3. Game Tower Of Hanoi

The Tower of Hanoi (juga disebut Menara Brahma atau Lucas 'Tower) adalah permainan matematika atau teka-teki. Ini terdiri dari tiga batang, dan sejumlah piringan dengan ukuran yang berbeda yang dapat berpindah ke batang lainnya. Teka-teki dimulai dengan tumpukan piringan dalam urutan ukuran pada satu batang, yang terkecil di bagian atas, sehingga membuat bentuk kerucut. 

Tujuan dari teka-teki adalah untuk memindahkan seluruh tumpukan ke batang lain, dan harus mematuhi aturan sederhana berikut ini:

1. Hanya satu piringan dapat dipindahkan pada satu kali langkah.2. Setiap langkah terdiri dari mengambil satu piringan paling atas dari salah satu

tumpukan dan meletakkannya di paling atas tumpukan lain yaitu piringan hanya dapat dipindahkan jika piringan ada di paling atas suatu tumpukan. 

3. Tidak ada piringan yang dapat ditempatkan di atas piringan yang lebih kecil.

Sedangkan algoritma yang kita gunakan dalam membuat game ini adalah algoritma Stack (tumpukan) dalam teori Struktur Data. Stack (tumpukan) adalah salah satu model struktur data yang tersusun secara LIFO (Last In First Out) dimana penyisipan elemen selalu dilakukan di atas (TOP) dan penghapusan elemen selaku dilakukan pada TOP.

Halaman|10

Contoh Source Code Tower of Hanoi dengan bahasa pemrograman C++ :

#include <iostream.h>#include <conio.h>void tower(int a,char from,char aux,char to){ if(a==1){ cout<<"\t\tPindah disc 1 dari "<<from<<" ke "<<to<<"\n"; return; } else{ tower(a-1,from,to,aux); cout<<"\t\tPindah disc "<<a<<" dari "<<from<<" ke "<<to<<"\n"; tower(a-1,aux,from,to);

}}

void main(){ clrscr(); int n; cout<<"\n\t\t*****Tower of Hanoi*****\n"; cout<<"\t\tMasukkan nilai disc : "; cin>>n; cout<<"\n\n"; tower(n,'A','B','C'); getch();}

4. Backtracking Runut balik (backtracking) adalah algoritma yang berbasis pada Depth First

Search (DFS) untuk mencari solusi persoalan secara lebih singkat. Runut balik, yang merupakan perbaikan dari algoritma brute-force, secara sistematis mencari solusi persoalan di antara semua kemungkinan solusi yang ada. Dengan metode runut balik, kita tidak perlu memeriksa semua kemungkinan solusi yang ada. Hanya pencarian yang mengarah ke solusi saja yang selalu dipertimbangkan.

Algoritma Depth First Search (DFS) menggunakan struktur data stack untuk mengingat kemana seharusnya Depth First Search (DFS) pergi saat ia mencapai suatu simpul tertentu.

Istilah “depth first” artinya melewati sebuah lintasan sejauh (sedalam) mungkin. Hanya pada titik tertentu yang tidak dapat ditelusuri, maka dilakukan runut balik (backtracking) dan menelusuri lintasan alternatif lain.Skema umum algoritma runut balik adalah :

1. Solusi dicari dengan membentuk lintasan dari akar ke daun. Aturan yang dipakai adalah mengikuti metode pencarian mendalam (DFS). Simpul-simpul yang sudah dilahirkan dinamakan simpul hidupm dan simpul hidup yang sedang diperluas dinamakan simpul-E. Simpul dinomori dari atas ke bawah sesuai dengan kelahirannya.

2. Jika lintasan yang diperluas yang sedang dibentuk tidak mengarah ke solusi, maka simpul-E tersebut “dibunuh” sehingga menjadi simpul mati (dead node). Simpul yang sudah mati ini tidak akan diperluas lagi.

3. Jika pembentukan lintasan berakhir dengan simpul mati, maka proses pencarian diteruskan dengan membangkitkan simpul anak lainnya. Bila tidak ada lagi simpul anak yang dibangkitkan, maka pencarian solusi dilanjutkan dengan melakukan runut-balik (backtracking) ke simpul hidup terdekat. Selanjutnya simpul ini menjadi simpul-E yang terbaru.

4. Pencarian dihentikan bila telah ditemukan solusi atau tidak ada lagi simpul hidup untuk runut balik (backtracking).

Contoh Backtracking :

Halaman|11

1. Backtracking pada history call browserPada saat buka browser pasti akan membuka icon seperti pada gambar di samping, fungsi icon di samping adalah icon kembali akses halaman

sebelumnya. Konsepnya sama dengan STACK, yaitu halaman akan menumpuk, dan untuk memanggil satu persatu halaman sebelumnya dengan mengklik icon back seperti pada gambar di samping.

2. Backtracking pada game SudokuSudoku adalah suatu permainan teka-teki yang memiliki aturan sederhana.

Teka-teki ini terdiri atas 9 buah blok yang berupa tabel 3 × 3. Sebagian sel tabel dalam teka-teki ini telah diisi dengan angka-angka yang berupa patokan untuk menyelesaikan teka-teki. Tujuan permainan ini adalah untuk mengisi setiap sel tabel yang masih kosong

dengan angkaangka, sedemikian sehingga dalam 1 blok hanya terdiri atas angka 1-9 yang tidak berulang dan tidak ada angka yang berulang dalam 1 baris maupun kolom. Meskipun aturannya sederhana namun penyelesaian teka-teki ini tidak semudah aturannya. Tentu saja tingkat kesulitan tiap teka-teki dapat bervariasi. 2.2 Strategi umum penyelesaian teka-teki Sudoku Secara umum, Sudoku dapat diselesaikan dengan kombinasi teknik pemindaian (scanning), penandaan ( marking), dan analisa (analysing). Beberapa tekiteki Sudoku yang tergolong mudah dapat diselesaikan hanya dengan salah satu proses, namun pada umumnya kita harus mengkombinasikan ketiga teknik tersebut. a. Pemindaian

Berupa proses memindai baris atau kolom untuk mengindentifikasi baris mana dalam suatu blok yang terdapat angka-angka tertentu. Proses ini kemudian diulang pada setiap kolom (atau baris) secara sistematis. Kemudian menentukan nilai dari suatu sel dengan membuang nilai-nilai yang tidak mungkin.

b. Penandaan Berupa analisa logika, dengan menandai kandidat angka yang dapat

dimasukkan dalam sebuah sel.c. Analisa

Berupa eliminasi kandidat, dimana kemajuan dicapai dengan mengeliminasi kandidat angka secara berturut-turut hingga sebuah sel hanya punya 1 kandidat.

Penerapan algoritma runut balik dalam teka-teki Sudoku :

Algoritma runut balik sangat efektif dalam mengurangi jumlah pencarian kemungkinan solusi teka-teki. Menurut perhitungan ada sebanyak 6,670,903,752,021,072,936,960 jumlah kemungkinan status untuk teka-teki Sudoku berukuran 9 x 9. Suatu angka yang sangat besar jika ingin dicari secara brute-force, dengan kompleksitas.

Halaman|12

3. Dan lain masih banyak lagi backtracking lainnya.

5. Manajemen MemoriAlgoritma Memori LRU (Least Recently Used)Secara konsep halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar, halaman yang baru di-load akan digunakan kembali.Algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses. Halaman yang berada di linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan di posisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.

Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.

6. Konversi Bilangan Desimal Ke BinerAdapun algoritma dari program Konversi bilangan desimal ke biner dengan stack adalah sebagai berikut:

1. Ambil sisa pembagian variable bilangan dengan angka 2, kemudian simpan dalam variable sisa. Kemudian simpan isi variable sisa ke dalam stack.

2. Bagi variable bilangan dengan angka 2.

Halaman|13

3. Ulangi langkah 1 dan 2 selama bilangan tidak 0. Jika variable bilangan telah bernilai 0 maka lanjutkan ke langkah 4,

4. Lakukan perulangan untuk langkah 5 dan 6 selama stack masih mempunyai isi (tidak kosong).

5. Ambil (pop) nilai yang ada di stack simpan di variable data.6. Tulis isi variable data ke layar .7. Selesai.

Contoh dalam bahasa pemrograman C++ :

#include<stdio.h>#include<conio.h>#include<iostream.h>int MAXSTACK;typedef int itemtype;

typedef struct{itemtype item[300]; int count;}stack;

void initializestack(stack *s){s->count = 0;}

int empty(stack *s){return (s->count == 0);}

int full(stack *s){return (s->count == MAXSTACK);}

void push(itemtype x, stack *s){if(full(s))

cout<<"Stack penuh !\n"; else

{s->item[s->count]=x; ++(s->count);}}

int pop(stack *s){if(empty(s))

cout<<"Stack kosong\n";else{--(s->count);return (s->item[s->count]);}}

main(){

int i, n, m, l, z; int input;stack tumpukan;

cout<<"PROGRAM KONVERSI DECIMAL KE BINER\n\n";initializestack(&tumpukan);

cout<<"Masukkan bilangan desimal = ";cin>>input;

for(z=1,n=input;n>0;n=n/2, z++){MAXSTACK=z;}m=0;for(n=input;n>0;n=n/2){l=n%2;push(l,&tumpukan);++m;}

cout<<"Bilangan biner = ";for(i=MAXSTACK;i>0;i--){cout<<pop(&tumpukan);}

getch();return 0;

Halaman|14

}

7. Shortcut Keyboard WINDOWS BUTTON + TAB

Saat kita menghidupkan PC dengan sistem operasi windows akan muncul tampilan desktop. Sering kita mengoperasikan PC dengan berbagai macam aplikasi, nah dari aplikasi-aplikasi tersebut akan membuat sebuah tumpukan dimana tumpukan tersebut menggunakan konsep STACK. Aplikasi yang berjalan tersebut akan mengeksekusi aplikasi yang terakhir dahulu. Dan dimana kursor itu berada maka itulah aplikasi yang sedang berjalan atau dieksekusi pertama. Kita bisa melihat apa saja sih tumpukan program aplikasi yang sedang berjalan, yaitu dengan menekan WINDOWS BUTTON + TAB.

8. Undo Log pada text editor.Konsep sama dengan konsep backtracking history call browser.

9. RekursifRekursif merupakan salah satu metode algoritma yang kerap digunakan dalam membuat perulangan, seperti halnya iterasi for, repeat .. until, do.. while, dsb. Perbedaannya adalah dalam sifatnya yang memanggil dirinya sendiri, baik secara langsung ataupun melalui metode yang lainnya. Ciri masalah yang dapat diselesaikan secara rekursif adalah masalah itu dapat direduksi menjadi satu atau lebih masalah-masalah serupa yang lebih kecil. Secara umum metode algoritma rekursi terdiri atas dua komponen utama, yaitu :

Bagian induksi, merupakan satu atau lebih kasus yang menyelesaikan masalah serupa namun dengan ukuran data ataupun metode yang lebih sederhana

Bagian penyetop, merupakan satu atau lebih kasus yang paling sederhana dan solusinya tidak perlu lagi terjadi rekursi

Supaya tidak terjadi rekursi yang tak berhingga,setiap langkah rekursif haruslah mengarah ke kasus penyetop. Cara bekerja algoritma rekursi ini adalah ketika sebuah metode rekursif dipanggil S(n), maka aksi ini akan di push ke stack yang ada di dalam register. Demikian pula ketika S(n) memanggil S(n-1) hingga S(k) yang merupakan komponen penyetop dipanggil maka barulah isi stack di pop.

Halaman|15

Berikut adalah beberapa contoh kasus pemrograman yang menggunakan algoritma rekursi, yakni menhitung jumlah digit suatu bilangan, jumlah deret bilangan bulat positif dan jumlah deret bilangan genap positif dengan menggunakan bahasa C++ :

#include <stdio.h>

#include <windows.h>

#include <conio.h>

#include <iostream.h>

//menghitung jumlah digit suatu bilangan ex. 234 == 9

int digit(n){

if (n < 10)

return n;

else return (n % 10) + digit(n / 10);

}

//menghitung jumlah deret S(n) = 1 + 2 + 3 + 4 + .... + n

int deret1(n){

if (n == 1)

return 1;

else return deret1(n - 1) + n;

}

//menghitung jumlah deret genap S(n) = 2 + 4 + 6 + 8 + .... + (2 * n)

int deret2(n){

if (n == 1)

return 2;

else return deret2(n - 1) + (2*n);

}

int main(){

cout<<"Penjumlahan digit dengan n = 678 : "<<digit(678);

cout<<"\nPenjumlahan deret bilangan dengan n = 8 : " <<deret1(8);

cout<<"\nPenjumlahan deret genap dengan n = 5 : "<<deret2(5);

getch();

}

10. Dan lain masih banyak lagi.Dan lain masih banyak lagi implementasi STACK pada program komputer, tim penulis hanya bisa memberikan sebagian contoh dari implementasi STACK pada program komputer.

Halaman|16

BAB III

PENUTUP

3.1 Kesimpulan

Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya dilakukan pada salah satu sisinya. Keunikan Stack justru pada operasi yang hanya menyangkut elemen TOP. Pada stack, elemen yang diproses hanyalah elemen pada TOP.

3.2 SaranPenggunaan stack pada struktur data sangat bermanfaat untuk para pemrogram untuk

melakukan suatu pemakain dalam informatika misalnya untuk meresenpetasi pemanggilan prosedur, perhitungan ekspresi aritmatika, rekursifitas, backtracking. Gunakan stack pada program yang operasinya selalu dilakukan pada elemen yang paling atas.

Halaman|17

DAFTAR PUSTAKA

Wikipedia .2011. Stack (abstract data type) http://id.wikipedia.org/wiki/Stack (abstract data

type) , Diakses pada 2 Juni 2015, Pukul 16.00 WIB.

Informatika .2008. Makalah Stmik

http://www.informatika.org/~rinaldi/Stmik/Makalah/MakalahStmik26.pdf, 12 Januari 2008

Diakses pada 30 Mei 2015, Pukul 11.00 WIB.

Informatika 2008. Makalah Stmik

http://www.informatika.org/~rinaldi/Stmik/2007-2008/Makalah2008/MakalahIF2251-2008-

109.pdf, Diakses pada 30 Mei 2015, Pukul 10.23 WIB.

M. Shalahuddin, Rosa A.S. 2010. Modul Pembelajaran Struktur Data.Penerbit: Modula.

Bandung.

Marcus, Zakaria, Teddy.Prijono,Agus.Konsep dan Implementasi Struktur Data. Penerbit:

Informatika. Bandung.

Dewa. 2009. Struktur Data – Pengertian Stack. http://dewa18.wordpress.com/

2009/10/28/struktur-data-pengertian-stack/. Diakses pada 30 Mei 2015, Pukul 10.23 WIB.

Hastuti, Nor Fitriana. 2009. Program Implementasi Stack dalam Pascal.

http://terminaltechno.blog.uns.ac.id/2009/11/07/program-implementasi-stack-dalam-pascal/.

Diakses pada 30 Mei2015, Pukul 10.37 WIB.

Hendradhy, Oke. 2008. Aplikasi Stack Pada Struktur Data Untuk Mengkonversikan Notasi

Infix Menjadi Notasi Postfix. http://mugi.or.id/blogs/oke/ archive/2008/08/27/aplikasi-stack-

pada-struktur-data-untuk-mengkonversikan-notasi-infix-menjadi-notasi-postfix.aspx.

Diakses pada 30 Mei 2015, Pukul 11.09 WIB.

Halaman|18