Minggu, 21 Mei 2017

PERTEMUAN || QUEUE (ANTREAN)

PENGERTIAN QUEUE (ANTREAN)
Struktur Data Antrean (Queue) adalah suatu bentuk khusus dari List Linier dengan operasi pemasukan data hanya diperbolehkan pada salah satu sisi, yang disebut sisi Belakang / ekor (Tail) dan operasi penghapusan hanya diperbolehkan pada sisi lainnya yang disebut sisi Depan / kepala (Head) dari LinkedList.

Prinsip Antrean : FIFO (First In First Out)
                            FCFS (First Come First Serve)
Yang Tiba lebih awal Maka akan dilayani Terlebih Dahulu

Deklarasi Queue
OPERASI QUEUE
  • CREATE
    Untuk menciptakan dan menginisialisasi Queue Dengan cara membuat Head dan Tail  = -1
  • ISEMPTY
    Untuk memeriksa apakah queue kosong
  • ISFULL
    Untuk memeriksa apakah queue sudah penuh
  • ENQUEUE
    Untuk menambahkan item pada posisi paling belakang
  • DEQUEUE
    Untuk menghapus item dari posisi paling depan
  • CLEAR
    Untuk mengosongkan queue
Fungsi Create
  • Digunakan untuk membentuk dan menunjukan awal terbentuknya suatu Antrean / Queue
Fungsi IsEmpty
  •  Untuk memeriksa apakah Antrian penuh atau kosong
  •  Dengan cara memeriksa nilai Tail, jika Tail = -1 maka antrian kosong (empty)
  •  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
Int IsEmpty()
{
   if (antrian.tail == -1)
        return 1;
   else
        return 0;
}

Fungsi IsFull
  •   Untuk mengecek apakah Antrian sudah penuh atau belum
  •   Dengan cara :
    - Mengecek nilai Tail
    - Jika tail = MAX-1 berarti antrian sudah penuh
      (MAX-1 adalah batas elemen array dalam  
       program C++)

Int IsFull()
{
   if (antrian.tail == Max-1)
        return 1;
   else
        return 0;
}
Fungsi Enqueue
  • Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu dilakukan pada     elemen paling belakang
  • Penambahan elemen selalu menggerakan variabel Tail dengan cara menambahkan Tail terlebih dahulu
Fungsi Dequeue
  • Digunakan untuk menghapus elemen terdepan (head) dari Antrian
  • Dengan cara : menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1. Penggeseran dilakukan dengan menggunakan looping
Fungsi 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 sehingga mengembalikan antrian seperti keadaan semula
Latihan I Struktur Data (Pertemuan 6)

Berikan gambaran/ilustrasi dari kasus antrian berikut :
  1. Diketahui suatu Antrian/queue dgn max = 6.
  2. Lakukan Enqueue 4 elemen ke dalam antrian, dimanakah posisi Head dan Tail ?
  3. Kemudian lakukan Dequeue 2 elemen dari antrian. Maka dimana posisi Head dan Tail ?
  4. Dari keadaan diatas, bagaimanakah kondisi IsFull dan IsEmpty nya ?

PERTEMUAN 5 || STACK atau TUMPUKAN

STACK atau TUMPUKAN
Merupakan bentuk khusus dari Linier List yang pemasukan dan penghapusan elemennya hanya dapat dilakukan pada satu posisi, yaitu posisi akhir dari List (Top)

Prinsip Stack adalah LAST-IN-FIRST-OUT (LIFO).

OPERASI STACK
  • ISEMPTY
    Untuk memeriksa apakah stack kosong
  • ISFULL
    Untuk memeriksa apakah stack sudah penuh
  • PUSH
    Untuk menambahkan item pada posisi paling atas (TOP)
  • POP
    Untuk menghapus item paling atas (TOP)
  • CLEAR
    Untuk mengosongkan stack

STACK PADA ARRAY
Deklarasi MAX_STACK
    #define MAX_STACK 5

Deklarasi STACK dengan struct dan array data
    typedef struct STACK{
    int top;
    int data[5];
    };


Deklarasi variabel stack dari struct
    STACK tumpuk;
 Inisialisasi
  • Pada mulanya isi top dengan -1, karena array dalam C/C++ dimulai dari 0, berarti stack adalah KOSONG
  • TOP adalah variabel penanda dalam STACK yang menunjukkan elemen teratas Stack.
  • TOP of STACK akan selalu bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack PENUH
Fungsi IsEmpty
  •  Digunakan untuk memeriksa apakah stack masih dalam kondisi kosong
  • Dengan cara memeriksa TOP of STACK.
  •     Jika TOP masih = -1 maka berarti stack masih kosong

Fungsi IsFull
  • Digunakan untuk memeriksa apakah kondisi stack sudah penuh
  • Dengan cara memeriksa TOP of Stack.
    Jika TOP of STACK = MAX_STACK-1 maka FULL (Penuh).
    Jika TOP of STACK < MAX_STACK-1 maka belum penuh

int IsFull ()
{
   if (tumpuk.top == MAX_STACK-1
    return 1;
   else
    return 0;   
}



Fungsi PUSH
  • Digunakan untuk memasukkan elemen ke dalam stack dan selalu menjadi elemen teratas stack
  • Dengan cara  :
  1. Menambah satu (increment) nilai TOP of STACK setiap ada penambahan elemen stack selama stack masih belum penuh
  2. Isikan nilai baru ke stack berdasarkan indeks TOP of STACK setelah ditambah satu (diincrement)
void push (char d[5])
{
   tumpuk.top++
   strcpy(tumpuk.data[tumpuk.top],d);
}
 Fungsi POP
  • Digunakan untuk menghapus elemen yang berada pada posisi paling atas dari stack.
  • Dengan cara :
    1.    Ambil dahulu nilai elemen teratas stack dengan mengakses TOP of STACK.
    2.    Tampilkan nilai yang akan diambil.
    3.    Lakukan decrement nilai TOP of STACK sehingga jumlah elemen stack berkurang 1
void pop ()
{
   printf(“Data yg di POP = %s\n”, tumpuk.data[tumpuk.top]);
   tumpuk.top--;
}
 Fungsi CLEAR
  • Digunakan untuk mengosongkan stack / membuat stack hampa sehingga Top pada Stack berada kembali di posisi Top = -1
 

 Latihan I Struktur Data (Pertemuan 5)

 Diketahui suatu stack dgn max_stack = 6
  1. Bila dilakukan PUSH 3 elemen kedalam stack, kemudian di PUSH lagi 2 elemen dan di POP 3 elemen. Maka dimana posisi Top of Stack ?
  2. IsEmpty pada kondisi terakhir adalah ?
  3. Dari kondisi diatas, Berapa elemen yg hrs di PUSH unt mencapai kondisi penuh Top of Stack = max_stack ?
  4. Berapa elemen yg hrs di POP unt mencapai kondisi IsEmpty = True

PERTEMUAN 4 || SINGLE LINK LIST (Non Circular )

SINGLE LINKED LIST
(Non Circular)

KONSEP POINTER  DAN LINKED LIST
Untuk mengolah data yang banyaknya tidak bisa ditentukan sebelumnya, maka disediakan satu fasilitas yang memungkinan untuk menggunakan suatu perubah yang disebut dengan perubah dinamis (Dinamic variable)

Perubah Dinamis (Dinamic variable)
Suatu perubah yang akan  dialokasikan hanya pada saat diperlukan, yaitu setelah program dieksekusi.
   
Perbedaan Perubah Statis & Dinamis
Pada perubah statis, isi Memory pada lokasi tertentu (nilai perubah) adalah data sesungguhnya yang akan diolah. Pada perubah dinamis, nilai perubah adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data yang sesungguhnya dapat dimasukkan secara langsung.
Dalam hal cara pemasukkan data dapat diilustrasikan seperti dibawah ini.
DEKLARASI POINTER

Pointer digunakan sebagai penunjuk ke suatu alamat memori
Dalam pemrograman C++, Type Data Pointer
dideklarasikan dengan bentuk umum :
   
               Type Data * Nama Variabel;


Type Data dapat berupa sembarang type data, misalnya char, int atau float. Sedangkan Nama veriabel merupakan nama variabel pointer


Contoh penggunaan pointer dalam program C++:

Void main()
{
  int x,y,*z;
  x = 75;      //nilai x = 75
  y = x;        //nilai y diambil dari nilai x
  z = &x;     //nilai z menunjuk kealamat pointer dari nilai x
  getch();
}

LINKED LIST (LINKED LIST)

Salah satu Struktur Data Dinamis yang paling sederhana adalah Linked List atau Struktur Berkait atau Senarai Berantai, yaitu suatu kumpulan komponen yang disusun secara berurutan dengan bantuan Pointer.
Linked List (Senarai Berantai) disebut juga dengan Senarai Satu Arah (One-Way List). Masing-masing komponen dinamakan dengan Simpul (Node).
Perbedaan Karakteristik Array dan Linked List
Setiap simpul dalam suatu Linked List terbagi menjadi dua bagian,yaitu :
1.    Medan Informasi
    Berisi informasi yang akan disimpan dan diolah.
2.    Medan Penyambung (Link Field)
    Berisi alamat berikutnya. Bernilai 0, Jika Link tersebut tidak menunjuk ke Data (Simpul) lainnya. Penunjuk ini disebut Penunjuk Nol.

Linked List juga mengandung sebuah variabel penunjuk List, yang biasanya diberi nama START (AWAL) yang berisi alamat dari simpul pertama dalam List
 

Bentuk Node Single Linked List non Circular
  • Single : field pointer-nya hanya satu dan satu arah,pada akhir node pointernya menunjuk NULL
  • Linked List : node-node tersebut saling terhubung satu sama lain.
  • Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
  • Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Pembuatan Single Linked List non Circular
Deklarasi Node :
    typedef struct TNode{
        int data;
        TNode *next;
    };


Keterangan:
Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data bertipe integer dan field next yang bertipe pointer dari TNode

  • Setelah pembuatan struct, buat variabel head yang bertipe pointer dari TNode yang berguna sebagai kepala linked list.
  • Digunakan perintah new untuk mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya ditunjuk ke NULL.
        TNode *baru;
        baru = new TNode;
        baru->data = databaru;
        baru->next = NULL;
Single Linked List non Circular Menggunakan Head
  • Dibutuhkan satu buah variabel pointer : head yang akan selalu menunjuk pada node pertama
Deklarasi Pointer Penunjuk Head Single Linked List

Manipulasi linked list tidak dapat dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk ke node pertama (Head) dalam linked list

Deklarasinya sebagai berikut:
                TNode *head;

Fungsi Inisialisasi Single Linked List
    void init()
    {
    head = NULL;
    }


Function untuk mengetahui kondisi Single Linked List
Jika pointer head tidak menunjuk pada suatu node maka kosong
            int isEmpty()
            {
                if (head == NULL) return 1;
                else return 0;
            }


 Menambah Node di Depan
  • Penambahan node baru akan dikaitan di node paling depan, namun pada saat pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara: node head ditunjukkan ke node baru tersebut.
  • Prinsipnya adalah mengkaitkan node baru dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan.





























Menambah Node di Belakang
  • Penambahan data dilakukan di belakang, namun pada saat pertama kali, node langsung ditunjuk oleh head.
  • Penambahan di belakang membutuhkan pointer bantu untuk mengetahui node terbelakang. Kemudian, dikaitkan dengan node baru. 
  • Untuk mengetahui data terbelakang perlu digunakan perulangan.
























Menghapus Node di Depan
  • Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penggunakan suatu pointer lain (hapus) yang digunakan untuk menunjuk node yang akan dihapus, barulah kemudian menghapus pointer hapus dengan menggunakan perintah delete.
  • Sebelum data terdepan dihapus, terlebih dahulu head harus menunjuk ke node berikutnya agar list tidak putus, sehingga node setelah head lama akan menjadi head baru
  • Jika head masih NULL maka berarti data masih kosong!

Menghapus Node di Belakang
  • Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node yang akan dihapus, pointer bantu untuk menunjuk node sebelum node yang dihapus yang akan menjadi node terakhir.
  • Pointer bantu digunakan untuk menunjuk ke nilai NULL. Pointer bantu selalu bergerak sampai sebelum node yang akan dihapus, kemudian pointer hapus diletakkan setelah pointer bantu.  Selanjutnya pointer hapus akan dihapus, pointer bantu akan menunjuk ke NULL.


 Function untuk menghapus semua elemen Linked List
    
void clear()
    {
    TNode *bantu,*hapus;
    bantu = head;
        while(bantu!=NULL)
        {
        hapus = bantu;
        bantu = bantu->next;
        delete hapus;
        }
    head = NULL;  
    }

 
 Menampilkan / Membaca Isi Linked List
  • Linked list ditelusuri satu-persatu dari awal sampai akhir node.  Penelusuran dilakukan dengan menggunakan pointer bantu, karena pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.
  • Penelusuran dilakukan terus sampai ditemukan node terakhir yang menunjuk ke nilai NULL.  
  •     Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait.
  • Jika head masih NULL berarti data masih kosong!
    void tampil(){
        TNode *bantu;
        bantu = head;
        if(isEmpty()==0){
            while(bantu!=NULL){
                cout<<bantu->data<<" ";
                bantu=bantu->next;
            }
            printf(“\n”);
        } else printf(“Masih kosong\n“);
    }



 Single Linked List non Circular Menggunakan Head dan Tail
  • Dibutuhkan dua variabel pointer : head dan tail
  • Head selalu menunjuk pada node pertama, sedangkan tail selalu menunjuk pada node terakhir.
  • Kelebihan dari Single Linked List dengan Head & Tail adalah pada penambahan data di belakang, hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan perulangan pointer bantu.
Inisialisasi Linked List
        TNode *head, *tail;

Fungsi Inisialisasi Linked List
        void init(){
           head = NULL;
         tail = NULL;
        }

Function untuk mengetahui kondisi LinkedList kosong / tidak
        int isEmpty(){
           if(tail == NULL) return 1;
           else return 0;
        }


 
Menambah Node di Depan Dengan Head dan Tail 






















Menambah Node di Belakang Dengan Head dan Tail  

























Menghapus Node di Depan (Dengan Head dan Tail)
  • Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan pointer hapus pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data setelah head menjadi head baru,  kemudian menghapus pointer hapus dengan menggunakan perintah delete.
  • Jika tail masih NULL maka berarti list masih kosong!





Menghapus Node di Belakang (Dengan Head dan Tail)
  • Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variabel hapus pada tail. Jika tail masih NULL maka berarti list masih kosong!
  • Dibutuhkan pointer bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail, sehingga tail dapat ditunjukkan ke bantu, dan bantu tersebut akan menjadi tail yang baru.  
  • Setelah itu hapus pointer hapus dengan menggunakan perintah delete.


    Function untuk menghapus semua elemen LinkedList dengan HEAD & TAIL

    void clear()
    {
        TNode *bantu,*hapus;
        bantu = head;
        while(bantu!=NULL)
        {
           hapus = bantu;
           bantu = bantu->next;
           delete hapus;
        }
    head = NULL;
    tail = NULL;  
    }

PERTEMUAN 3 || ARRAY DIMENSI BANYAK

3.    ARRAY DIMENSI TIGA (Three Dimensional Array)
   
    Digunakan untuk mengelola data dalam bentuk 3 dimensi atau tiga sisi.
    Deklarasi :
    Type_Data Nama_Variabel [index1] [ndex2] [index3];  Misal : int A [3][4][2];
   
Penggambaran secara Logika :
Menentukan jumlah elemen dalam Array dimensi 3 :

= Perkalian dari statemen sebelumnya    
     



Contoh :
Suatu Array X dideklarasikan sbb :
int A [3][4][2]; maka jumlah elemen Array dimensi tiga tersebut adalah :

(3) * (4) * (2)     =   24

Contoh mengenal alamat array dimensi tiga
1. Terdapat array tiga dimensi dengan int A[2][3][5].
Diketahui &A[0][0][0]=1000H, Ditanya &A[1][2][3]=....?

&A[0][0][0]=10Tipe int satu elemen=2byte
Untuk array [2][3][5]: 1 baris=5 elemen
                : 1 grup=3 * 5=15 elemen

00H

 2. Terdapat array tiga dimensi dengan int A[2][3][5].
Diketahui &A[1][1][4]=12EFH, Ditanya &A[0][0][2]=....?

Tipe int satu elemen=2byte
Untuk array [2][3][5]: 1 baris=5 elemen
             : 1 grup=3 * 5=15 elemen

 Contoh Program array dimensi 3

Tampilan Program

 TRINGULAR ARRAY (ARRAY SEGITIGA)Tringular Array dapat merupakan Upper Tringular (seluruh elemen di bawah diagonal utama = 0), ataupun Lower Tringular (seluruh elemen di atas diagonal utama = 0). Dalam Array Lower Tringular dengan N baris, jumlah maksimum elemen <> 0 pada baris ke-I adalah = I, karenanya total elemen <> 0, tidak lebih dari
Contoh :
Diketahui suatu array segitiga atas memiliki 3 baris dan kolom, tentukan berapakah jumlah elemen yang bukan nol pada array tersebut.
           I     =   N(N+1) / 2   
           I    =   3 (3+1) / 2   
                 = 12 / 2 
                 = 6      

Contoh bentuk array nya adalah seperti dibawah ini :

Suatu Array Upper Tringular  dan Array Lower Tringular dapat dengan order yang sama, dapat disimpan sebagai suatu array dengan order yang berbeda, Contohnya :

SPARSE ARRAY (ARRAY JARANG)
Suatu Array yang sangat banyak elemen nol-nya, contohnya adalah Array A pada Gambar berikut :

PERTEMUAN || QUEUE (ANTREAN)

PENGERTIAN QUEUE (ANTREAN) Struktur Data Antrean (Queue) adalah suatu bentuk khusus dari List Linier dengan operasi pemasukan data hanya ...