OPERASI DASAR STACK

OPERASI PADA STACK

1. CREATE (STACK)
2. ISEMPTY (STACK)
3. PUSH (ELEMEN, STACK)
4. POP (STACK)

CREATE(S)
Operator ini berfungsi untuk membuat sebuah stack kosong (menjadi hampa) dan didefinisikan bahwa
NOEL (CREATE (S)) = 0 dan
TOP (CREATE(S)) = null / tidak terdefinisi




 ISEMPTY(S)
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong (hampa) atau tidak . Operasinya akan bernilai boolean dengan definisi sebagai berikut :
ISEMPTY(S) = true, jika S adalah stack kosong atau NOEL(S) = 0
False, jika S bukan stack kosong atau NOEL(S)  0
Catatan : ISEMPTY(CREATE(S)) = true

 PUSH(E,S)
• Operator ini berfungsi untuk menambahkan satu elemen ke dalam stack . Notasi yang digunakan adalah PUSH(E,S)
Artinya : menambahkan elemen E ke dalam stack S
• Elemen yang baru masuk ini akan menempati posisi TOP jadi TOP(PUSH(E,S)) = E
• Akibat 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 )

 POP(S)
• Operator ini berfungsi untuk mengeluarkan satu elemen dari dalam stack, notasinya POP(S)
• 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 1 dan elemen pada posisi TOP akan berubah.
• Operator ini tidak dapat digunakan pada stack kosong, artinya POP(CREATE(S)) = error condition dan
POP(PUSH(E,S)) = S

Catatan : TOP(PUSH(E,S)) = E

Queue
Adalah suatu bentuk khusus dari linear list dengan operasi penyisipan (insertion) hanya pada salah satu sisi ( Rear/ belakang) dan operasi penghapusan (deletion) hanya diperbolehkan pada sisi lainnya (Front/ depan) dari list.

Antrean Q = [ Q1, Q2, Q3,……….., QT]
Front(Q) = bagian depan dari antrean Q
Rear(Q) = bagian belakang dari antrean Q
Noel(Q) = Jumlah elemen di dalam antrean ( berharga integer)
Jadi : Front(Q) = QT
Rear(Q) = Q1
Noel(Q) = T

Antrean beroperasi secara FIFO ( First In First Out) yang pertama masuk, yang pertama keluar.

 Operasi dasar pada Antrean :
1. CREATE(Q)
Operator untuk membentuk suatu antrean hampa
Q = [,…….,]
NOEL(CREATE(Q)) = 0
FRONT(CREATE(Q)) = tidak didefinisikan
REAR(CREATE(Q)) = tidak didefinisikan

2. ISEMPTY(Q)
Operator yang menentukan apakah antrean Q hampa atau tidak.
Operand dari operator ISEMPTY adalah antrean.
Hasilnya bertipe data Boolean
ISEMPTY(Q) =TRUE jika Q adalah antrean hampa (NOEL(Q) = 0)
FALSE jika Q bukan antrean kosong (NOEL(Q)  0)

3. INSERT(E,Q)
Operator yang menyisipkan elemen E ke dalam antrean Q
Catt : Elemen Q ditempatkan pada bagian belakang antrean dan antrean menjadi lebih panjang
Q = [ A, B, C, D]
REAR(INSERT(E,Q)) = E
FRONT(Q) = A
NOEL(Q) = 5
ISEMPTY(INSERT(E,Q)) = FALSE

4. REMOVE(Q)
Operator yang menghapus elemen bagian depan dari antrean Q dan antrean menjadi lebih pendek
Jika NOEL(Q) = 0 maka
REMOVE(Q) = ERROR ( UNDERFLOW)

 Penyajian dari antrean :
1. One way list
2. Array
 Menunjukkan bagaimana suatu antrean dalam array Queue dengan N elemen
1. Antrean mula-mula terdiri dari elemen AAA, BBB, CCC, DDD


1 2 3 4 5 6 7 8 9
FRONT(Q) = AAA : 1
REAR(Q) = DDD : 4


2. REMOVE(Q)


1 2 3 4 5 6 7 8 9

FRONT(Q) = BBB : 2
REAR(Q) = DDD : 4

3. INSERT(EEE,Q)
1 2 3 4 5 6 7 8 9
FRONT(Q) = BBB : 2
REAR(Q) = EEE : 5
KESIMPULAN :
Untuk setiap kali penghapusan nilai FRONT bertambah
Untuk setiap kali penambahan nilai REAR akan bertambah

 Antrean yang disimpan dalam array dengan 5 lokasi memori sebagai array Sirkular.

1. Pada Awal Hampa
FRONT = 0 REAR = 0 1 2 3 4 5

2. A dan B dimasukkan
FRONT : 1
REAR : 2 1 2 3 4 5


3. C, D , dan E dimasukkan
FRONT :1
REAR : 5
1 2 3 4 5
4. A, B, dan C dihapus
FRONT : 4
REAR :5
1 2 3 4 5
5. F dimasukkan
FRONT : 4
REAR : 1

1 2 3 4 5
6. D dihapus
FRONT : 5
REAR :1
1 2 3 4 5
7. G dan H dimasukkan
FRONT : 5
REAR : 3
1 2 3 4 5

8. E dihapus
FRONT :1
REAR : 3
1 2 3 4 5
 ALGORITMA QINSERT
QINSERT(QUEUE, N, FRONT, DATA)
1. {Apakah antrean penuh}
Jika FRONT = 1 dan REAR = N atau Jika FRONT = REAR+1, maka Write : OVERFLOW, return.
2. Jika FRONT = NULL maka FRONT := 1, REAR := 1
Dalam hal ini
Jika FRONT = N maka REAR := 1
Dalam hal lain
REAR := REAR + 1
3. QUEUE(REAR) := DATA ( masukkan elemen baru)
4. Return

 ALGORITMA QDELETE
QDELETE(QUEUE, N, FRONT, REAR, DATA)
1. {Apakah antrean kosong}
Jika FRONT = NULL, maka Write : UNDERFLOW, return.
2. DATA := QUEUE(FRONT)
3. (FRONT mendapat nilai baru)
Jika FRONT =REAR maka FRONT := NULL
REAR := NULL
Dalam hal ini
Jika FRONT := N maka FRONT := 1
Dalam hal lain
FRONT := FRONT + 1
4. Return



LINK LIST

PENDAHULUAN
 Dalam suatu linier list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.
 Misalkan ada 1500 item yang merupakan elemen dari suatu linier list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linier list tersebut. Tetapi elemen ke–57akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.

 Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data.

DEFINISI

 Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
 Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu:
 INFO berisi informasi tentang elemne data yang bersangkutan.
 NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.

Berikut ini sebuah contoh linked list yang terdiri atas 4 node:



Info next info next info next info next
Node ke-1 node ke-2 node ke-3 node ke-4
Pada node ke-4 field NEXT–nya berisi NULL , artinya node ke-4 tsb adalah node terakhir.

 Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini:
Info next
Info next

Info next

Info next


CATATAN :
 Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini,
yaitu:
1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.
2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.
 Sedangkan keuntungannya adalah :
1. Jenis data yang berbeda dapat di-link
2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah