Queue

Definisi Queue

Queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari, misalnya saat Anda mengantri di loket untuk membeli tiket.Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang datang terlebih dahulu akan dilayani lebih dahulu.Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue.

Walaupun berbeda implementasi, struktur data queue setidaknya harus memilikioperasi-operasi sebagai berikut :

EnQueue  : Memasukkan data ke dalam antrian

DeQueue  : Mengeluarkan data terdepan dari antrian

Clear        : Menghapus seluruh antrian

IsEmptY   : Memeriksa apakah antrian kosong

IsFull        : Memeriksa apakah antrian penuh

Implementasi Queue

Implementasi Queue dengan Double Linked List

Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linkedlist yang digunakan adalah double linked list, operasi-operasinya:

- Konstruktor 

Konstruktor berguna untuk menciptakan queue yang baru dan kosong, yaitu dengan mengarahkan pointer head dan tail kepada NULL.

- IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.

- IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.

- EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).

- DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).

Contoh Studi Kasus
1.Buatlah program Queue dengan berisikan Data masukan dan Data Pengeluaran !
Pembahasan :

 Output :

Searching

Didalam Pembahasan ini kita akan membahas proses pencarian / searching data pada suatu array / barisan data. Sebagai contoh sederhana :

Apabila diketahui ada sebuah array / barisan data bernama A yang menampung 10 data yang bertipe integer sbb A={1,2,3,4,8,5,7,9,6,0} dan kita diberi tugas untuk mencari beberapa data misal:

 Jika data yang akan dicari dalam array A adalah 6, maka dengan cepat dapat kita ketahui bahwa data 6 ada dalam array A pada index ke-9 (index pada array dimulai dari 0).

 Sedangkan jika data yang akan dicari dalam array A adalah 12, maka dapat disimpulkan bahwa array A tidak memiliki data 12 tersebut.

Bisa diambil kesimpulan, kita sudah memahami proses pencarian data yang sederhana tersebut dalam pikiran kita, sekarang permasalahannya adalah bagaimana mengimplementasikannya kedalam program

Pada umumnya dikenal dua metode searching antara lain : Sequensial search dan binary search, Untuk lebih memahami kedua metode ini lebih baik kita mulai dari metode yang paling sederhana terlebih dahulu yaitu sequensial search.

Sequensial search

Metodenya seperti ini..

1. User diminta menentukan banyaknya data yang akan diinputkan

2. User menginputkan data sebanyak yang telah ditentukan pada langkah pertama

3. User diminta memasukkan data yang dicari

4. Program melakukan perulangan, mencari data yang dicari

5. Pada akhir perulangan ada 2 kondisi

5.1 Data yang tidak dicari tidak ditemukan

5.2 Data yang dicari ditemukan, kemudian tampilkan posisinya

Secara garis besarnya seperti itulah Algortima yang digunakan pada metode Sequential Search. Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.

Contoh studi kasus
1.Buatlah Program Sequencial search dengan mencari suatu data yang ada pada index tersebut !

Pembahasan dan contoh program :

 Output :

Binary search

Algoritma yang digunakan pada metode Binary seperti dibawah ini :

1. User diminta menentukan banyaknya data yang akan diinputkan

2. User menginputkan data sebanyak yang telah ditentukan pada langkah pertama

3. User diminta memasukkan data yang dicari

4. Mengurutkan data jika data belum terurut

5. User diminta memasukkan data yang dicari

6. Menentukan nilai tengah array

7. Pengecekan apakah nilai array pada index tengah sama dengan data yang dicari

8. Jika “sama”, data yang dicari ditemukan

8.1 jika “tidak”, periksa apakah data yang dicari lebih kecil dari nilai tengah

8.1.1 jika “true” lakukan pencarian dari i=0 sampai i=nilai tengah

8.2 jika 8.1 bernilai “false” berarti data yang dicari lebih besar dari nilai tengah

8.2.1 lakukan pencarian mulai dari i=nilaitengah+1 sampai data terakhir

9. Tampilkan hasil pencarian

Secara garis besarnya seperti itulah Algortima yang digunakan pada metode Binary Search. Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan dolah, data yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang akan dicari.

Bedanya metode Sequential dan Binary adalah keadaan datanya. Jika Sequential data tidak terurut pun bisa, namun jika menggunakan Binary data harus dalam keadaan urut.

Contoh Studi Kasus :

1.Buatlah Program Binary Search dengan mencari suatu data pada index tersebut !

Pembahasan : 

Output :

Stack

Definisi Stack

Stack adalah suatu tumpukan dari benda. Konsep utamanya adalah LIFO (Last In FirstOut), benda yang terakhir masuk dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.

DiC++, ada dua cara penerapan prinsip stack, yakni dengan array dan linked list.

Setidaknya stack haruslah memiliki operasi-operasi sebagai berikut:

- Push : Untuk menambahkan item pada tumpukan paling atas

- Pop : Untuk mengambil item teratas

- Clear : Untuk mengosongkan stack

- IsEmpty : Untuk memeriksa apakah stack kosong

- IsFull : Untuk memeriksa apakah stack sudah penuh

Dalam bab ini penjelasan mengenai stack akan menggunakan kelas stack. Kelima operasi stack diatas akan dideklarasikan secara abstrak dalam kelas ini, sedangkan kelas turunan dari stack akan mengimplementasikan operasi-operasi tersebut.

B. Implementasi Stack

1. Stack dengan Array

Sesuai dengan sifat stack, pengambilan / penghapusan delemen dalam stack harus dimulai dari elemen teratas.

Operasi-operasi pada Stcak dengan Array:

a. Konstruktor

Fungsi ini membuat sebuah stack baru yang masih kosong. Konsepnya adalah bahwa Top menunjukkan elemen stack teratas. Jika Top bernilai -1, berarti tumpukan kosong.

b. IsFull

Fungsi ini memeriksa apakah stack yang ada sudah penuh. Stack penuh jika stack penuh jika puncak stack terdapat tepat dibawah jumlah maksimum yang dapat ditampung stack atau dengan kata lain Top = MAX_STACK -1.

c. Push

Fungsi ini menambahkan sebuah elemen ke dalam stack dan tidak bisa dilakukan lagi jika stack sudah penuh.

d. IsEmpty

Fungsi menentukan apakah stack kosong atau tidak. Tanda bahwa stack kosong adalah Top bernilai kurang dari nol.

e. Pop

Fungsi ini mengambil elemen teratas dari stack dengan syarat stack tidak boleh kosong.

f. Clear

Fungsi ini mengosongkan stack dengan cara mengeset Top dengan -1. Jika Top bernilai kurang dari nol maka stack dianggap kosong.

Stack dengan Single Linked List

Selain implementasi stack dengan array seperti telah dijelasnkan sebelumnya, ada cara lain untuk mengimplementasi stack dalam C++, yakni dengan single linked list.Keunggulannya dibandingkan array tebtu saja adalah penggunaan alokasi memori yangdinamis sehingga menghindari pemborosan memori. Misalnya saja pada stack denganarray disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai olehuser stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack. Oleh karena itupula dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi olehpembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas,yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List

 Konstruktor

Fungsi ini membuat stack baru yang kosong. Stack adalah kosong jika Top tidak menunjuk apa pun (bernilai NULL).

 IsEmpty

Fungsi memeriksa apakah stack yang ada masih kosong.

 Push

Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan inser tdalam single linked list biasa.

 Pop

Fungsi ini mengeluarkan elemen teratas dari stack.

 Clear

Fungsi ini akan menghapus stack yang ada.

contoh studi kasus :
1.buatlah contoh program tentang operasi single stack !

Pembahasan dan contoh program :

Output:

Sorting

Pengurutan (Sorting) adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Sorting dapat dibedakan menjadi dua jenis yaitu ascending dan descending. Ascending adalah pengurutan data dari kecil ke besar, sedangkan Descending adalah pengurutan data dari besar ke kecil.

Metode Pengurutan

Dalam pertemuan ini akan membahas tentang 2 metode, yaitu :

1) Insertion Sort

2) Selection Sort

Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana Input : deretan angka sejumlah dan buah,

Output : permutasi (pengurutan) sejumlah dan angka dari input yang sudah terurut secara ascending maupun descending .

Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.

Metode ini mengurutkan bilangan-bilangan yang telah dibaca dan berikutnya secara

berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut. 

Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.

contoh Studi Kasus :

1.Buatlah Program C++ tentang Insertion Sort dimana user bebas menginputkan suatu data !

 Pembahasan :

Output :

Selection Sort

Selection Sort

metode ini dikatakan kebalikan dari metode Bubble sort. Pencarian dimulai dengan bilangan terkecil.Bilangan terkecil ini lalu diletakan di elemen atau urutan pertama, demikian seterusnya sampai dihasilkan urutan bilangan dari kecil ke besar.

Studi Kasus 

1.Buatlah program Selection sort sebagaimana user hanya bisa menginputkan 5 buah data saja !
Pembahasan :

Output

Array

Array adalah variabel yang dapat menyimpan sejumlah data sejenis (bertipe data sama).

Array dibagi menjadi dua yaitu Array satu dimensi dan multi dimensi

berikut perjabarannya

Array satu dimensi adalah kumpulan elemen yang tersusun dalam suatu baris

Deklarasi Array

                        : tipe_data   nama_array[ukuran];

Keterangan :

-tipe_data                     : menyatakan jenis tipe data elemen arra (int, char, float, dll)

-nama_array                 : menyatakan nama variabel yang dipakai.

-ukuran                        : menunjukkan jumlah maksimal elemen array.

Mengakses Array Dimensi Satu

Suatu array dapat diakses menggunakan indeksnya.

Bentuk umum :

-         Nama_array[indeks]

contoh studi kasus 
1.buatlah program array 1 dimensi dengan menggunakan tipe data int !
Pembahasan :

                                                                          output :

Array Multidimensi merupakan sebuah perluasan dari sebuah array satu dimensi. Jika pada array satu dimensi hanya terdiri dari sebuah baris dengan beberapa kolom elemen maka pada array dua dimensi terdiri dari beberapa baris dan beberapa kolom elemen yang bertype sama.

Deklarasi Array

                       : tipe_data nama_array[jml_baris][jml_kolom];

Keterangan :

tipe_data                      : menyatakan jenis tipe data elemen array

                                     (int, char, float, dll)

nama_array                  : menyatakan nama variabel yang dipakai.

jml_baris                     : menunjukkan jumlah maksimal baris.

jml_kolom                   : menunjukkan jumlah maksimal kolom.

contoh study kasus array 2 dimensi :

2. buatlah contoh program array 2 dimensi yang menggunakan tipe data int!
 Pembahasan :

Output :

Variabel,Konstanta dan Tipe Data

Identifier

Di dalam program, selalu dibutuhkan suatu tempat untuk menyimpan nilai yang disebut identifier.

Identifier dibagi menjadi 2 jenis, yaitu:

1.Variabel

2.Konstanta

Variabel

Variabel adalah nama yang digunakan dalam memori komputer untuk menyimpan suatu nilai.

Nilai suatu variabel dapat berubah-ubah selama program berjalan.

Cara mendeklarasikan variabel:

tipe_data nama_variabel;

Aturan Penamaan Variabel :

-Ketentuan pemberian nama untuk variabel :

-Tidak boleh sama dengan nama keyword reserved, function, dan harus unik.

-Maksimum 32 karakter. Bila lebih, maka karakter selebihnya tidak akan diperhatikan oleh komputer.

-Case sensitive : membedakan huruf besar dan kecil

-Karakter pertama harus huruf atau underscore (_)

-Tidak boleh mengandung spasi / blank , tanda – , dan tanda #

Tipe Data

Tipe data adalah jenis data yang dapat diolah oleh komputer untuk memenuhi kebutuhan dalam pemrograman komputer. Setiap variabel atau konstanta yang ada dalam kode program, sebaiknya kita tentukan dengan pasti tipe datanya. Ketepatan pemilihan tipe data pada variabel atau konstanta akan sangat menentukan pemakaian sumberdaya komputer (terutama memori komputer). Salah satu tugas penting seorang programmer adalah memilih tipe data yang sesuai untuk menghasilkan program yang efisien dan berkinerja tinggi.

Tipe Data dikelompokkan menjadi dua Yaitu primitive dan composite :

Tipe Data Primitive :

• Numeric
• Character
• Boolean

Tipe Data Composite :

• Array
• Record
• Image
• Date Time
• Lainya (Subrange, Enumerasi, dll)

Tipe Data Char

-Karakter ASCII (American Standard for Information Interchange)

Studi Kasus

1.Deklarasikan beberapa variabel yang bertipe data integer,char,dan float.

2.Buatlah variabel bertipe data integer dengan menginputkan data dari user

Pembahasan :

1.Deklarasi tipe data int,float,char :

2.Input nilai bertipe data integer :