Pengertian Stack

Pengertian Stack pada Struktur Data adalah sebagai tumpukan dari benda, sekumpulan data yang seolah-olah diletakkan di atas data yang lain, koleksi dari objek-objek homogen, atau Suatu urutan elemen yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. Stack pada Struktur Data dapat diilustrasikan dengan dua buah kotak yang ditumpuk, kotak yang satu akan ditumpuk diatas kotak yang lainnya. Jika kemudian stack 2 kotak tadi, ditambah kotak ketiga, keempat, kelima, dan seterusnya, maka akan diperoleh sebuah stack kotak yang terdiri dari N kotak.

Stack bersifat LIFO (Last In First Out) artinya Benda yang terakhir masuk ke dalam stack akan menjadi yang pertama keluar dari stack 

Operasi-operasi yang biasanya tredapat pada Stack yaitu:

1. Push : digunakan untuk menambah item pada stack pada tumpukan paling atas

2. Pop : digunakan untuk mengambil item pada stack pada tumpukan paling atas

3. Clear : digunakan untuk mengosongkan stack

4. IsEmpty : fungsi yang digunakan untuk mengecek apakah stack sudah kosong

5. IsFull : fungsi yang digunakan untuk mengecek apakah stack sudah penuh

Cara mendefenisikan Stack dengan Array of Struct yaitu:

1. Definisikan Stack dengan menggunakan struct

2. Definisikan konstanta MAX_STACK untuk menyimpan maksimum isi stack

3. Buatlah variabel array data sebagai implementasi stack

4. Deklarasikan operasi-operasi/function di atas dan buat implemetasinya.

contoh :

//Deklarasi MAX_STACK

                #define MAX_STACK 10   

            

//Deklarasi STACK dengan struct dan array data

                typedef struct STACK{

                                int top;

                                char data[10][10];                                                           

                }; 

//Deklarasi/buat variabel dari struct

                STACK tumpuk;

Inisialisasi Stack

Pada mulanya isi top dengan -1, karena array dalam C dimulai dari 0, yang berarti stack adalah kosong.

Top adalah suatu variabel penanda dalam STACK yang menunjukkan elemen teratas Stack sekarang.  Top Of Stack akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.

Ilustrasi Stack pada saat inisialisasi

IsFull berfungsi untuk memeriksa apakah stack sudah penuh atau tidak. Dengan cara, memeriksa top of stack, jika sudah sama dengan MAX_STACK-1 maka full, jika belum (masih lebih kecil dari MAX_STACK-1)  maka belum full.

Ilustrasi Stack pada kondisi Full

IsEmpty berfungsi untuk memeriksa apakah stack masih kosong atau tidak. Dengan cara memeriksa top of stack, jika masih -1 maka berarti stack masih kosong.

Push berfungsi untuk memasukkan elemen ke stack, selalu menjadi elemen teratas stack (yang ditunjuk oleh TOS).

Tambah satu (increment)  nilai top of stack lebih dahulu setiap kali ada penambahan elemen stack.

Asalkan stack masih belum penuh, isikan data baru ke stack berdasarkan indeks top of stack setelah diincrement sebelumnya.

Pop berfungsi untuk mengambil elemen teratas (data yang ditunjuk oleh TOS) dari stack.

Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan dipop, baru dilakukan decrement nilai top of stack sehingga jumlah elemen stack berkurang.

Printberfungsi untuk menampilkan semua elemen-elemen stack dengan cara looping semua nilai array secara terbalik, karena kita harus mengakses dari indeks array tertinggi terlebih dahulu baru ke indeks yang kecil.

Sorting / pengurutan

Sorting / pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian. Pengurutan data baik dari segi ascending (dari nilai terkecil ke terbesar) atau descending (dari nilai terbesar ke terkeci). Ketika akan melakukan sortir di komputer, maka hal-hal yang akan mempertimbangkan, meliputi :
1. Perlu tidaknya data disortir
2. Besarnya atau banyaknya data yang akan disortir
3. Kemampuan atau kapasitas computer atau media penyimpanan data
4. Metode sortir
Teknik sortir sangat erat kaitannya dengan proses perbandingan dan penukaran tempat antar elemen data. Waktu terbaik akan diperoleh ketika susunan elemen datanya sudah sama dengan susunan yang diinginkan melalui sortirnya. Waktu terburuk akan didapatkan ketika susunan elemen – elemen datanya terbalik dari susunan yang dikehendaki sortirnya. Waktu rata-rata diperoleh dengan memperhitungkan berbagai susunan bentuk elemen-elemen datanya.

1. Bubble Sort

Bubble Sort atau metode gelembung adalah metode pengurutan dengan cara melakukan penukaran data dengan tempat disebelahnya jika data sebelum lebih besar dari pada data sesudahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan, atau telah terurut dengan benar. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci atau data akan dengan lambat menggelembung atau membandingan data ke posisinya yang tepat.

Metode ini mudah dipahami dan diprogram, tetapi bila dibandingkan dengan metode lain yang kita pelajari, metode ini merupakan metode yang paling tidak efisien karena memiliki banyak pertukara sehingga memerlukan pengalokasian memori yang besar untuk menjalankan metode ini.

Kelebihan Bubble sort :
- Metode Bubble sort adalah metode yang paling simpel
- Metode Bubble sort mudah dimengerti algoritmanya

Contoh Program Bubble Sort :

#include<iostream.h>

#include<conio.h>

void Selsort(int X[], int SIZE)

{

int pos,small,temp;

for (int i=0; i<SIZE-1; i++) {

small=X[i];

for (int j=i+1; j<SIZE; j++)

{

if (X[j]<small)

{small=X[j];

    pos=j;}

    }

    temp=X[i];

    X[i]=X[pos];

    X[pos]=temp;

    } }

    void main(void)

    { clrscr();

    int A[10];

    int size;

    cout<<"\n Enter array size :";

    cin>>size;

    cout<<"\n Enter array elements :";

    for (int i=0; i<size; i++)

    {

    cin>>A[i];

    }

    Selsort(A,size);

    cout<<"\n The sorted array is as shown below :";

    for (int l=0; l<size; l++)

    {cout<<A[l];}

    getch();

    }

Contoh Gambar Cara Kerja Bubble Sort :

2. Selection Sort

Selection Sort adalah metode yang digunakan dengan cara memilih data yang akan diurutkan menjadi dua bagian, yang belum diurutkan, dan meja yang telah diurutkan. Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakan pada posisinya sesuai dengan bagian lain array yang telah di urutkan. Tahapan ini dilakukan secara berulang-ulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

Contoh Program Selection Sort :

#include <conio.h>

#include <stdio.h>

void tampilkan_larik(int data[], int n)

{

int i;

for (i=0;i<n;i++)

cout<<data[i]<<"  ";

cout<<endl<<endl;

}

void selection_sort(int data[], int n)

{

int posmin, posawal, j, tmp;

for(posawal=0;posawal<n-1;posawal++)

    {

   posmin=posawal;

   for (j=posawal+1;j<n;j++)

       if(data[posmin]>data[j])

          posmin=j;

         //tukarkan

           tmp=data[posawal];

         data[posawal]=data[posmin];

         data[posmin]=tmp;

      cout<<"\n Hasil ketika Posawal = "<<posawal<<" : ";

      tampilkan_larik(data,n);

   }

}

int main ()

{

int data[50], i,n;

cout<<"\n@ SIMULASI SELECTION SORT @\n\n\n";

cout<<"=========================================\n";

cout<<"      masukkan banyak data : ";

cin>>n;

clrscr();

for (int a=0;a<n;a++)

    {

   cout<<"\n   masukkan data ke "<<a<<" : ";

   cin>>data[a];

   }

selection_sort(data,n);

//hasil pengurutan

cout<<"\n\n  hasil pengurutan : \n\n";

cout<<"  "; tampilkan_larik(data,n);

cout<<"\n SORTING SELESAI...................";

getch();

clrscr();

cout<<"-----------------------";

cout<<"by: hamba Allah, 2014";

cout<<"-----------------------";

getch();

return 0;

}

Contoh Gambar Cara Kerja Selection Sort :

3. Insertion Sort

Insertion Sort adalah Metode Literasi (pengulangan) yang menginsert atau menyisipkan setiap elemen ketempat yang sesuai(setelah dibandingkan dengan elemen kiri dan kanannya) atau kita bisa mengumpamakan metode ini seperti bermain kartu, yaitu satu demi satu akan menginsert ketempat yang sesuai.

Contoh Program Insertion Sort :

#include <iostream.h>

#include <conio.h>

#define ELEMENTS 6

void insertion_sort(int x[], int length){

    int key, i;

   for(int j=0; j<length;j++){

            key=x[j];

            i=j-1;

            while(x[i]>key&&i>=0){

                x[i+1]=x[i];

                i--;

            }

            x[i+1]=key;

   }

}

int main(){

    int A[ELEMENTS]={9,2,7,5,4,3};

   int x;

   cout<<"array yang belum di sort:";

   for(x=0;x<ELEMENTS;x++){

           cout<<A[x];

   }

   cout<<endl;

   insertion_sort(A,ELEMENTS);

   cout<<"Array yang sudah di sort:";

   for(x=0;x<ELEMENTS;x++){

           cout<<A[x];

   }

   getch();

   return 0;

}

Contoh Gambar Cara Kerja Insertion Sort :

Pengertian Searching

1. Pengertian Searching 
Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data. 

2. Metode pencarian dibagi menjadi 2, yaitu: 
1. Metode Pencarian Beruntun 
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir. 
2. Metode Pencarian Bagi Dua (Binary Search) 
Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini. 
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut. 
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0; 
Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen. 


Contoh implementasi searching 

#include 

void main() 
{ 
clrscr(); 

int bil[5]; 
int jml_bil,nilai_max; 
int i; 

/* input data */ 
cout<<"masukkan jumlah bilangan kurang dari 5 : ";cin>>jml_bil; 
for(i=0;i
{ 
cout<<"bilangan ke"<<i+1<<":";cin>>bil[i]; 
} 

/* menentukan nilai max */ 
nilai_max=bil[0]; 
for(i=0;i
{ 
if (bil[i]>nilai_max) 
{ 
nilai_max=bil[i]; 
} 
} 

/* mencetak nilai max */ 
cout<<"nilai maksimum : "<<nilai_max<
cout<
 
getch(); 

} 

Algoritma dari 

Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut : 

1. Membaca Array data 
2. Apabila Array belum terurut maka array diurutkan terlebih dahulu. 
3. Menentukan data yang akan dicari 
4. Menentukan elemen tengah dari array 
5. Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti. 
6. Jika elemen tengah tidak sama dengan data yang dicari maka : 
1. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama. 
2. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya. 

</nilai_max<</i+1<<":";cin>

Queue

Queue pada Struktur Data atau antrian adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front). 

Pada Stack atau tumpukan menggunakan prinsip“Masuk terakhir keluar pertama”atau LIFO (Last In First Out), Maka pada Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out).

Queue atau antrian banyak kita jumpai dalam kehidupan sehari-hari, ex: antrian Mobil diloket Tol, Antrian mahasiswa Mendaftar, dll.

Contoh lain dalam bidang komputer adalah pemakaian sistem komputer berbagi waktu(time-sharing computer system) dimana ada sejumlah pemakai yang akan menggunakan sistem tersebut secara serempak.

Pada Queue atau antrian Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya dimana membutuhkan variabel Head dan Tail ( depan/front, belakang/rear).

Karakteristik Queue atau antrian :

1. elemen antrian

2. front (elemen terdepan antrian)

3. tail (elemen terakhir)

4. jumlah elemen pada antrian

5. status antrian

Operasi pada Queue atau antrian

1. tambah(menambah item pada belakang antrian)

2. hapus (menghapus elemen depan dari antrian)

3. kosong( mendeteksi apakah pada antrian mengandung elemen atau tidak)

Operasi-operasi Queue :

1. Create()

Untuk menciptakan dan menginisialisasi Queue

Dengan cara membuat Head dan Tail  = -1

2. IsEmpty()

Untuk memeriksa apakah Antrian sudah penuh atau belum

Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty

Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah

Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.

3. IsFull

Untuk mengecek apakah Antrian sudah penuh atau belum

Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh

4. Enqueue

Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang

Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu

5. Dequeue()

Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian

Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1

Penggeseran dilakukan dengan menggunakan looping

6. Clear()

Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1

Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca

7. Tampil()

Untuk menampilkan nilai-nilai elemen Antrian

Menggunakan looping dari head s/d tail