Queue (Antrean) Pertemuan 9

PERTEMUAN 9

QUEUE (ANTREAN)

A.      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 pengahapusan 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”

B.      Deklarasi Queue

#define MAX 8

Typedef Struct {

                Int data [MAX];

                Int head;

                Int tail;

                } Queue;

Queue antrian;

    0         1        2         3          4        5          6         7        Max=8

         Head = -1

         Tail = -1

C.      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

D.      Fungsi Create

Digunakan untuk membentuk dan menunjukkan awal terbentuknya suatu Antrean/Queue

E.       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

F.       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;

}

5

10

35

20

15

30

40

25

    0         1        2         3          4        5          6         7        Max=8

 Head=0

Tail=7

Antrian penuh karena Head=0 Tail=Max -1

G.     Fungsi Enqueue

·         Untuk menambahkan elemen pada antrian,penambahan elemen selalu dilakukan pada elemen paling belakang

·         Penambahan elemen selalu menggerakkan variable tail dengan cara menambahkan Tail terlebih dahulu

·          

4

45

1

8

    0         1        2         3          4        5          6         7        Max=8

Head=0

Tail=3

Enqueue (8)

H.      Fungsi Dequeue

·         Digunakan untuk menghapus elemen terdepan(head) dari antrian

·         Dengan cara ; menggeser semua elemen antrian kedepan dan mengurangi tail dengan 1.penggeseran dilakukan dengan menggunakan looping

I.        Fungsi Clear

·         Untuk menghapus elemen-elemen Antrian sebenarnya tidak menghapus arraynya ,namun hanya mengeset index pengaksesan-nya ke nilai-1 sehingga elemen-elemen Antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula

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

PERTEMUAN 9 QUEUE (ANTREAN)

LATIHAN 1 STRUKTUR DATA
Berikan gambaran/ilustrasi dari kasus antrian berikut;a. Diketahui suatu Antrian/queue dengan max =6

5

20

3

9

                0                  1                       2                   3                   4                   5               MAX=6

b. Lakukan Enqueue 4 elemen ke dalam antrian,      dimanakah posisi Head dan Tail ?

5

20

3

9

                0                  1                      2                    3                   4                    5               MAX=6                          HEAD=0                                   TAIL=3                                                                                    ENQUEUE=8
void Enqueue (int data){            if(IsEmpty()==1){                        antrian.head=antrian.tail=0;                        antrian.data[antrian.tail]=data;                        printf(“%d masuk!”,antrian.data[antrian.tail]);  } else  If(IsFull()==0){            antrian.tail++;            antrian.data[antrian.tail]=data;            printf(“%d masuk!”,antrian.data[antrian.tail]);  }}

c.Kemudian lakukan Dequeue 2 elemen dari antrian.Maka dimana posisi Head dan Tail ?

 

5

20

3

9

                0                  1                      2                    3                   4                    5               MAX=6

              
                          HEAD=0                                   TAIL=3                                                                                    DEQUEUE()
int Dequeue(){            int i;            int e = antrian.data[antrian.head];            for(i=antrian.head;i<=antrian.tail-1; i++) {            }            Antrian.tail--;            Return e;}

1

8

                0                  1                      2                    3                    4                   5               MAX=6                          HEAD=0        TAIL=1                                                                                                          MAJU SEMUA TAIL --

d. Dari keadaan diatas, bagaimanakah kondisi IsFull dan     IsEmpty nya ?
    IsFull

4

45

1

8

10

7

                0                  1                      2                    3                   4                   5                     MAX=6                                       head=0              antrean penuh karena                                                                head=0                                                   tail=5                                                tail= max -1int IsFull(){    If(antrian.tail== Max-1)            Return 1;   else            return 0;}
 

IsEmpty           0                       1                    2                     3                  4                   5                MAX=6Head= -1                      antrean kosongTail= -1                                    karena tail= -1
int IsEmpty(){    If(antrian.tail== -1)            Return 1;   else            return 0;}

ARRAY Dimensi Banyak beserta contoh

3.ARRAY DIMENSI TIGA (THREE  DIMENSIONAL ARRAY)
digunakan untuk mengelola data dalam bentuk 3 dimensi atau 3 sisi,
penggambaran secara logika

PEMETAAN (MAPPING)
Rumus 
@M[m][n][p] = M[0][0][0] + {((m-1)*(jumlah element2*jumlah element3)) + ((n-1)*(jumlah element3))+((p-1)}*L

soal
1. suatu array A dideklarasikan sebagai berikut :
int A[2][4][3],dengan alamat awal index A[0][0][0] 0011(H) dan ukuran type data int=2 tentukan berapa alamat array di A[2][3][2]?
A[2][3][2] = 0011(H) + {((2-1)*4*3)) + (( 3-1)*3)+((2-1)}*2
                  = 0011(H) + {12+6+1} * 2
                  = 0011(H) + 19*2
                  = 0011(H) + 38⇰ 26(H)
                  = 0037(H)
2. Dik : A[2][4][3]
             A[0][0][0] = 0011 (H)
             Float=4
  Dit : A[2][4][2]
penyelesaian
A[2][4][2] = 0011(H) + {((2-1)*4*3)) + (( 4-1)*3)+((2-1)}*2
                  = 0011(H) + {12+9+1} * 2
                  = 0011(H) + 22*2
                  = 0011(H) + 44(D)⇰ 2C(H)
                  = 003D(H)
3. dik : A[0][0][0] = ABCD
           L=4
           float= A[2][4][3]
Dit : A[2][2][3] dan A[2][4][2]
penyelesaian
A[2][2][3] = ABCD(H) + {((2-1)*4*3)) + (( 2-1)*3)+((3-1)}*4
                  = ABCD(H) + {12+3+2} * 4
                  = ABCD(H) + 17*4
                  = ABCD(H) + 68(D)⇰ 44(H)
                  = AC11(H)

4.suatu array A dideklarasikan sbb:

Float A[5][5][5] dengan alamat awal A[0][0][0] = 0021(H),berapakah alamat array
A[2][3][2] dan A[5][4][3]?
      penyelesaian
Dik : float=[5][5][5]
         A[0][0][0] = 0021(H)
         L=4
Dit : array=A[2][3][2] dan A[5][4][3]
A[2][3][2] = 0021(H) + {((2-1)*5*5)) + (( 3-1)*5)+((2-1)}*4
                  = 0021(H) + {25+10+1} * 4
                  = 0021(H) + 36*4
                  = 0021(H) + 144⇰ 90(H)
                  = 00B1H)

A[5][4][3] = 0021(H) + {((5-1)*5*5)) + (( 4-1)*5)+((3-1)}*4
                  = 0021(H) + {100+15+2} * 4
                  = 0021(H) + 117*4
                  = 0021(H) + 468⇰ 1D4(H)
                  = 01F5(H)
5.suatu array B dideklarasikan sbb:
char B[3][4][3] dengan alamat awal A[0][0][0] = 0021(H) ,berapakah alamat array
A[2][3][2] dan A[3][4][3]
Dik : char=[3][4][3]
         A[0][0][0] = 0021(H)
         L=1
Dit : array=A[2][3][2] dan A[3][4][3]
penyelesaian
A[2][3][2] = 0021(H) + {((2-1)*4*3)) + (( 3-1)*3)+((2-1)}*1
                  = 0021(H) + {12+6+1} * 1
                  = 0021(H) + 19*1
                  = 0021(H) + 19(D)⇰ 13(H)
                  = 0034(H)
A[3][4][3] = 0021(H) + {((3-1)*4*3)) + (( 4-1)*3)+((3-1)}*1
                  = 0021(H) + {24+9+2} * 1
                  = 0021(H) + 35*1
                  = 0021(H) + 35⇰ 23(H)
                  = 0044(H)
6. dik : A[2][4][5]
           A[0][0][0] = 0021(H)
           int= 2
   dit : A[2][2][2]
A[2][2][2] = 0021(H) + {((2-1)*4*5)) + (( 2-1)*5)+((2-1)}*2
                  = 0021(H) + {20+5+1} * 2
                  = 0021(H) + 26*2
                  = 0021(H) + 52(D)⇰ 34(H)
                  = 0055(H)



Sahma E

uji kompetensi no 21-30

21. Metode sorting manakah yang lebih cepat (disarankan) apabila menggunakan data yang cukup banyak (misal 100 data)
C.Quick Sort

22.diberikan deret angka sbb:
45,  100,21, 67,80,20,23,29,99,46,73
untuk mencari data 23 pada teknik linear/sequential search maka nilai X pada algoritma tersebut adalah
E.23
23.diberikan derek angka sbb: 45,100,21,67,80,20,23,29,99,46,73
dengan menggunakan tehnik linear search,untuk mencari data 23 akan ditemukan pada langkah yang ke
B.7
24. terdapat deret angka sebagai berikut:
16,20,36,45,56,60,67,70,78,89,93,99
untuk mencari data 78 maka teknik pencarian yang disesuaikan adalah:
A.Binary Search

25. terdapat deret angka sebagai berikut:
24,46,15,40,56,18,90
dengan menggunakan tehnik strait maxmin,berapakah nilai Max dan Min untuk A{4}?
B.Max = 46; Min=15
26.terdapat 7 buah program (N=7) yang masing2 mempunyai panjang program sbb:
L1=8,L2=11,L3=4,L4=12,L5=6,L6=20,L7=10
dengan metode optimal ontapes storage problem,tentukan order yang paling optimal
E. 3,5,1,7,2,4,6

27. Tentukanlah waktu perjalanan seorang salesmanuntuk mengunjungi lima tempat (misal: a,b,c,d,dan e) dengan graph sebagai berikut;

noted: waktu tempuh dalam jam tempat (A-B); 7 Jam 

buatlah rute Perjalanannya

C.  A-B-D-C-A=20 jam

28. permasalahan pada shortest path problem adalah untuk menghitung jalur terpendek dari sebuah grab berarah,kriteria untuk permasalahan ini adalah:

D.Setiap ruas pada graph tidak harus terhubung

29. permasalahan pada minimum spanning Tree adalah untuk mencari biaya yang minimal,dengan kriteria adalah :

B.setiap ruas pada graph tidak harus mempunyai nilai (label graph)

30.pada pewarnaan (coloring) diberikan contoh arus perjalanan sebagai berikut:

menurut anda pada fase 1 lampu lalulintas dengan warna hijau adalah:
E.AC,AD,AB,BC,ED


Terimakasih,

S.e.m

uji kompetensi no 01-09

1.diberikan matriks A sebagai Berikut:

   2  2  2  2

   0  2  2  2

   0  0  2  2

   0  0  0  2

perintah pokok yang digunakan pada pengisian matriks A adalah

 E. A[I,J]= 0 jika I>J; A[I,J]=2 jika I<=J

2. diberikan matriks A sebagai Berikut:

  1  2  3  4

  2  2  3  4

  3  3  3  4

  4  4  4  4

perintah pokok yang digunakan pada pengisian matriks A adalah

B.A[I,J] = j jika i>j; A[I,J]=i jika i>j

3. diberikan Matriks  A sebagai berikut:

  1  1  1  1

  2  2  2  2

  3  3  3  3 

  4  4  4  4 

perintah pokok yang digunakan pada pengisian matriks A adalah

d.A[I,J]=i jika i < j; A[I,J]=i jika i >= j

4. diberikan perintah pokok sebagai berikut:

A[i,j] = j jika I > J; A[I,J] =i, Jika i<=J

matriks dari perintah pokok tersebut adalah

C  1  2  3  4

     1  2  3  4

     1  2  3  4

     1  2  3  4

5. diberikan perintah pokok sebagai berikut:

A.[I,J]=J jika I<=J; A[I,J]=i, jika I>J

Matriks dari perintah pokok tersebut adalah

d.  1  1  1  1

     2  2  2  2 

     3  3  3  3

     4  4  4  4 

6.diberikan perintah pokok sebagai berikut:

 A[i,j] = i-1 jika I>J; A[I,J]= j, jika I<=J

Matriks dari perintah pokok tersebut adalah

B. 1  2  3  4 

     1  2  3  4

     2  2  2  4

     3  3  3  4

7.Diberikan perintah pokok sebagai berikut:

A[I,J]=4 jika I = J; A[I,J]=J+1, jika I<>J

Matrikx dari perintah pokok tersebut adalah

E  4  2  3  4

     2  4  4  5 

     3  4  4  6

     4  5  6  4

8. diberikan matriks A berikut:

A[i,j} = i jika I>=J; A[I,J]=), jika I<J

Matriks dari perintah Pokok tersebut adalah

 E. 1  0  0  0

      2  2  0  0

      3  3  3  0

      4  4  4  4 

9.diberikan algoritma sebagai berikut;

int i,a[4];

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

{ a[i]= 2* i+1

cout<<a[i]}

hasil nilai a yang tercetak adalah 

C 1 3 5 7