Struktur data

Pertemuan 1 struktur data
Jenis -jenis data

Jenis –  jenis data

Tipe data tunggal (data primitif) atau sederhana

·         Interger, real, dan bolean .

Tipe data majemuk (data campuran)

·         String (Untai)

Tipe data terstruktur

·         Array

Interger

- Suatu interger adalah anggota dari himpunan bilangan

-  operasi : dasar yang ada dalam interger adalah penjumlahan, pengurangan, perkalian, pembagian, dsb.

-  Operator ayng bekerja terhsdsp sepasang interger (operand) disebut sebagai binery operator.

-  Operator yang bekerja pada satu operand saja disebut sebagai unary operator.

-   Contoh unary operator negasi berfungsi untuk mengubah tanda suatu operand

Operator	Operand
+	Penjumlahan
*	Perkalian
-	Pengurangan
Div	Hasil bagi bilangan bulat
Mod	Sisa Pembagian

Real

-  Data numeric yang bukan termasuk interger, digolongkan dalam data real.

-  Jenis data ini ditulis mengunakan titik desimal/koma.

-  Bilangan real dimasukkan ke dalam memory computer memakai sistem floting point, merupakan versi yang disebut scientific notation

-  Penyajiannya terdiri atas 2 bagian, yaitu : mantissa (pecahan ) dan eksponen

Example

Bilangan 456000 = 0,456*10⁶

Disini 0,456 adalah mantissa (pecahan )sedangkan 6 adalah eksponen secara umum suatu bilangan realx dituliskan M*R^E

Operator	Operand
+	Penjumlahan
-	Pengurangan
*	Perkalian
/	pembagian

Bolean

-  Jenis data data ini disebut juga jenis data logical

-  Elemen dari jenis data in mempunyai nilai salah satu dari true atau false

-  Operator yang dikenal adalah

-  Operator logika yaitu not, and, dan or

-  Operator or akan menghasilkan nilai true jika salah 1 / kedua operand bernilai true

-  Operator and akan menghasilkan nilai true jika kedua nilai operand bernilai true

-  Operator not akan menghasilkan nilai true jika operand bernilai false dan sebaliknya

-  Operator not merupakan precedence dari operator and dan or

-  Dalam suatu ekspresi yang tidak menggunakan tanda kurung, operator NOT  harus dieavaluasi sebelum operator AND dan OR.

-  Operator relasinal yaitu >, <, <=, >= <> dan =

P	Q	P and Q	P or Q	P not Q
T	T	T	T	F
T	F	F	T	T
F	T	F	T	F
F	F	F	F	T

Karakter

§  Jenis data karakter merupakan elemen dari suatu himpunan symbol aksara yang atas bilangan, abjad, dan smbol-simbol khusus

String (1)

-  Jenis data string merupakan jenis data campuran, karena elemen dibentuk dari karakter-karater.

-  String adalah barisan hingga symbol yang diambil dari himpunan karakter.

-  Karakter yang digunakan untuk membentuk suatu string disebut sebagai alphabet

-  Dalam penulisan suatu string berada dalam tanda aphasthrope

-  Missal diberikan himpunan alphabet a – {‘c’,’d’,’i’}

string yang dapat dibentuk dari alphabet diatas adalah ‘cda’,’cdd’,’ddc’,’cdci’,dsb, termasuk null string / empaty string

String (2)

-  Himpunan yang anggotanya adalah semua string yang dapat dibentuk dari suatu himpunan alphabetdisebut sebagai vocabulary.

-  Suatu vocabulary u yang dihasilkan himpunan alphabet a dinotasikan denga a*

-  Jika suatu string dibentuk dari alphabet {0,1} maka string yang terbentuk disebut dengan bit string.

String (3)

-  Secara umum,suatu strung yang dibentuk dari himpunan alphabet A dituliskan s = ‘ala2…n', dimana setiap karakter a_i anggota A untuk I < I < n

§  Dalam suatu struing terdapat beberapa operasi  utama yaitu :

Length                  : menghitung panjang string (interger)

Concatenation  : menggabungkan

Substring             : mengambil

Insert                    : menyisihkan

Delete                  : menghapus

Length

-  Nilaidari suatu operasi iniadalh suatu interger yang menunjukan panjang dari suatu string. Panjang or dari string didefnisikan sebagai banyaknya karakter / dapat ditulis S = N / length = N

-  Contoh

Jika diberikan string s = ‘ala2…n’ maka length (s) = n

Jika diberikan string s = ‘assdrtfghb’ maka length (s) = 10

Concatenation

-  Operasi ini bekerja terhadap dua string dan hasilnya merukpakan resultan dari kedua string tersebut.

-  Operasi ini hampir sama denga operasi gabungan

-  Jika s1 dan s2 masing-masing adalha suatu string, maka bentuk operasi concateration dinotasikan dengan concat (s1,s2)

Maka concat (s1 s2 = ‘a1a2….an b1b2…bn’)

Panjang string yang baru merupakan jumlah panjang dari masing-masing string atau length (concat (s1,s2)) = length (s1) + length (s2)

Substring

§  Operasi ini adalah operasi membentuk string baru, yang merupakan bagian dari string yang dketahui.

§  Notasinya adalah SUBSTR (s,i,j)

Dimana :

S = string diketahui

I dan J adalah interger

I = posisi awal substring  o < i < length (s)

J =banyak karakter yang diambil o < j < length (s) dan o < I + j – I < length (s)

Catatan

1.       Length (substr (s,I,j)) = j

2.       Substr (concat (s1,s2), 1, length (s1)) = s1

3.       Substr (concat (s1,s2), length (s1)+1, length (s2)) =s2

Contoh :

S1 = singo

S2 = edan

                Substring concat (singo, edan), 1, length (edan)

                Substring (singo edan), 1, 9 ) = singo (terbukti)

Insert

-  Operasi ini adalah untuk menyisipkan suatu string ke dalam string lain

-  Bentuk umum adalah : insert (s1, s2, i)

-  S1 dan s2 masing-masing adalah suatu strng dan I adalah posisi awal s2 pada s1

Misalkan

S1 = ‘a1a2…an’

S2 = ‘b1b2…bm’

Insert (s1, s2, 3) = a1a2b1b2…b4a3a4…an

Contoh

S1 = singo

S2 = edan

Inset (s1,s2,2)

E singo dan

Delete

-  Operasi ini digunakan untuk menghapuskan sebagian karakter dalam suatu string.

-  Bentuk umum adalah delete(s,I,j)

-  Maksudnya adalah menghapuskan sebagian karakter dalam string s, mulai dari posisi i dengan panjang j.

-  Contoh

Diberikan string  s = ‘a1a2…an’

Delete (s,3,4) = ‘a1a2a7a8…an’

Deklarasi  data dalam bahasa pemrograman

Pascal

Var count : interger ;

                Switch : Boolean ;

                Betha : char ;

                Alamat : packed array [1…5] of char ;

Pemetaan interger ke storage

Bentuk mapping ke storage dari int dapat dilakukan dengan beberapa cara yaitu :

-  Skema sign dan magnitude (bentuk konvensional)

-  Skema one’s complement

-  Skema two’s complement

Skema sign dan magnitude

Merupakan bentuk konvensional yang dgunakan untuk menyatakan suatu blangan dalam bentuk biner, disin representasi bilangan positif dan negatif hanya dibedakan dengan tanda – saja, basanya tanda positif / negative ditunjukan oleh digit terdepan dari bentuk binernya, untuk reprensetasikan dengan jumlah digit tertentu.

Contoh

+7  --> + 111 representasi dengan 4 digit 0111

-7  --> - 111 representasik dengan 4 digit 1111

Skema 2 complement dan one complement

·         Kedua skema ini merupakan cara yang digunakan untuk mengatasi kesulitan yang telah  disebutkan diatas.

·         Diberiakan bilangan int non negasi x,x’ dan r dari defident bahwa

x’ adalah komponen dar x terhadap r jika x+x’=r

x disebut sebagai bentuk true sedangkan x’=r-x disebut bentuk complement

·         Bentuk complement x’=r-x menyatakan bilangan nterger negatf x, sedankan bentuk trie x menyatakan interger positif x

·         Skema 2 complement menggunakan r=2ⁿ

·         Skema 1 complement menggunakan r=2ⁿ-1

·          ,isal dibeikan interger = 7 akan dicari bentuk biner dengan 2 complement, representasi 4 digit x=7, r=2⁴

X+x’       = r

X’            = r-x

                = 2⁴ -7

                = 16 -7

                = 9 dalam biner 1001

Pemetaan karakter ke storage

·         Saat ini banyak sekali skema yang digunakan untuka repersentasikan karakter dalam storage.

·         Pada umumnya skema yang palaing bayak digunakan adalah exterded binary coded decmal interchange code (ebcdic) American standard code for infromatiom interchange (ascii)

·         Pada skema BCDIC digunakan kode 8 bit untuk menyatakan sebuah karakter, jika dihitun, kemungkinana kombinasi seluruhnya adalah 28.

·         Sedangkan skema ASCII menggunakan kode 7bit untu menyatakan suatu karakter, skema ini mempunyai jumlah kemungkina kombinasi yang lebih sedikit jika dibandingkan dengan skema FBCDIC.

·         Selan kedua skema tersebut, ada skema yang disebut denga kode Huffman. Pada cara ini,jumlah bit yang digunakan tergantung frekuensi penggunaan suatu karakter.

Pemetaan string ke storage

Untuk mengetahui bentuk mapping pada storage dari suatu string, perlu diketahui beberapa hal menyangkut ruang untuk string yang bersangkutan antara lain.

·         Letak posisi awal start dan posisi akhir (terminal)

·         Suatu ponter yang menunjukkan lokasi pada storage.

Ada 3 cara yang umum yang digunakan untuk mapping suatu string pada storage.

Cara 1

Jika diberikan informasi tentang nama strng , starting address, panjang string

nama	start	panjang string
String 1	Ptr 1	7
String 2	Ptr 2	3

A             B             C             D             E              F              G

Ptr1        ptr2

Cara 2

Info sama

nama	start	terminal
String 1	Ptr 1s	ptr7t
String 2	Ptr 2s	ptr3t

A             B             C             D             F              G             B             C             D

Ptr1s                                                      ptr1t                      ptr2s                      ptr2t

Cara 3

Info, nama, starting, batas string

Nama string	Start
String 1	Ptr1
String 2	Ptr2

A             B             C             D             E#G#     B             C             D#

Ptr1                                                                     ptr2

·         Selain caran diatas representasi suatu string pada storage dapat dalam bentuk packed / unpucked

·         Suatu string yang direpresentasikan dalam bentuk packed atas beberapa word.

·         Banyaknya karakter untuk masing-masing word tergantung dari kode yang digunakan oleh mesin (bitnya)

·         Secara umum jumlah word yang digunakan untuk merepresentasikan string s dalam storage dengan r karakter perword adalah

[Length(s)/k] notasi [] disebut dengan ceiling fuction

Pertemuan 2 struktur data

ARRY DAN RECORD

Definsi Array

v  Array hanya dapat menyimpan data bertipe sama

v  Sebuah array dapat dikatakan sebagai suatu himpunan terurut  dengan elemen-elemen homogenya.

v  Terurut, dimaksudkan bahan elemen pertama, elemen kedua dst masing-masing dapat didefinisikan.

v  Homogen  : masing-masing elemen tersebut mempunyai tipe dat yang sama

v  Array dapat dkelompokkan atas 2 bagian yaitu :

1.       Array satu dimensi

2.       Array multi dimensi

Array 1 Dimensi (1)

- Bentuk array yang paling sederhana

-  Array jenis ini dapat dainggap sebagai sebuah vector.

-  Suatu array A berdimensi 1 dengan N buah elemen, secara fisik dapat digambarkan sebagai berikut .

A1

A2

…

A(N)

Array 1 Dimensi(2)

-  Indeks dari elemen suatu array menyatakan posisinya dalam suatu urutan secara umum , suatu array berjenis data T yang mempunyai indeks dari L sampai dengan U dituliskan sebagai berikut : A(L:U)={A(1)}

-  Untuk 1=L, L+1, L+2, …, U-1,U, dimana masing-masing A(1) Berjenis data T,

-  L disebut sebagai batas bawah  dari indeks A dan U sebagai batas atas dari A.

-  Jumlah elemen dalam suatu array disebut sebagai range, range dari array A(L:U) adalah U-L+T

Array Multi Dimensi (1)

-  Array 2 dimensi adalah salah satu contoh dari array multi dimensi.

-  Array ini elemen-elemennya merupakan array pula .

-  Bentuk yang dianggap dapat mewakili array 2 dimensi ini adalah matriks

Array Multi Dimensi (2)

-  Array ini dituliskan : B(I:M,I:N)={B(I,J)}

untuk I = 1, 2, …, M

J = 1, 2, …, M

-  Jumlah elemen (range) dari array B ini adalah B

-  Secara umum, array 2 dimensi B dengan batas bawah indeks pertama L1, batas indeks pertama U1, batas bawah indeks kedua, batas atas indeks kedua dituliskan :

B(L1:U1,L2:U2) = {B(J,I)}

Cross Section

-  Yang dimaksud dengan cross section dari array 2 dimensi adalah suatu himpunan yang anggotanya adalh elemen-elemen dalam suatu baris saja atau kolom saja,

-  Notasinya menggunakan tanda *

-  Misal diberikan array B(L:M,I:N)

B(4,*) = {B(4,1),B(4,2),…,B(4,N)}

B(*,4) = {B(1,4),B(2,4),…,B(N,4)}

A(3,*)=A(3,1),A(3,2),(3,3)

Tranpose

-  tranpose dari suatu array 2 dimensi adalah suatu array  2 dimensi pula denagan menukar indeksnya
-  Transpose dari array berukuran M x N adalah suatu array berukuran N x M

-  Transpose dari suatu array B dinotasikan dengan BT dan didefinisikan : B(I,J) = BT (J,I)

-  Secara umum, suatu array A berdimensi A dapat dituliskan sbb :

  -A(L1:U1,L2:U2,…,LN:UN)

- Jumlah elemen array ini adalah

-  (U1-L1+1)(U2-L2+1)…(Un-Ln+1) à II (Uk-Uk+1)

-  Sebagai contoh perhatikan sebuah array 3 dimensi yang menggambarakan (jumlah ) mahasiswa Stimik Asia untk kelas eksekutif

-  Array ini dapat digambarkan sebagai berikut :

Variabel Asia (i,j,k)

I = jenis kelamin (p,w)

J = jenis kelas (reg,eks)

K = jumlah kelas (A:D)

Pemetaan array 1 dimensi ke storage

·         Ada beberapa cara untuk menyatakan suatu array pada storage, tetapi konsepnya sama dengan dengan apa yang ada pada data fungsi

·         Missal diberikan array 1 dimensi dengan  nama A yang mempunyai indek I s/d N, yaitu A (A:N)

·         Secara fisik array A(A:N) dapat dgaimbarkan sebagai berikut :

A(1)

A(2)

A(3)

…..

A(5)

…..

A(N)

·         Yang perlu kita ketahui disini adalah letak elemen ke1 dari array A(I:N), letak masing-masing elemen array pada storage.

·         Letak suatu elemen biasanya disebut sebagai starting address / starting locaton / base location.

·         Untuk mengetahui starting addres suatu elemen array, perlu diketahui lebih dari a.l.

1.       Starting address dari array yang bersangkutan.\

2.       Ukuran masing-masing lelemen array / ruang yang digunakan masing-masing elemen array.

Peraan array multi dimensi ke storage

·         Prinsip yang digunakan disini tetap didasarkan array  1 dimensi.

·         Oleh karena itu untuk array multi dimensi, linearisasinya dapat dilakukan berdasarkan baris/kolom.

·         Contoh , missal diberikan array A (1:3.1:4) array ini secara fisik dapat digambarakan sebagai berikut

·         Linierisasinya menurut baris akan mengakibatkan bentuk diatas menjadi.

                                1                                              2                                                              3

·         Starting addres A(2,4)

=B+(2-1)*4*5+4(4-1)*5

=B+7*5

·         Secara umum elemen A(l,j) dari array A(I:U,L:U) mempunyai starting addres

B+(1-L1)*(U2-L2+1)*S+(J-L2)*S

·         Alternaatif lain untuk linierisasi adalah dengan menggunakan cara kolom jika diberikan array A(1:3,1:4) diatas, maka baik linerisasinya

Kolom1                                                 kolom2                                 kolom3

Record

·         Record adalah himpunan dari elemen-elemen yang heterogen.

·         Heterogen adalah elemen-elemennya dapat mempunyai tipe data yang berbeda

·         Bebarapa hal yang perlu diketahui dalam record sebagai berikut.

·         Elementary item adalah suatu field yang tidak mempunyai subfield

·         Group hem adalah suatu field yang mempunyai subfield.

·         Tupelo adalah gabungan atribut yang menjadi suatu informasi diproses basis data

Contoh :

Table database karyawan

Nama	Job tittle	No karyawan	Gaji	telepon
String	String	String	Real	String

Lebih dari 1 tipe data

File

·         Record-record yang sama tipenya disebut file

·         Untuk menyatakan suatu data dalam record yang mempunyai identifikasi yang khusus, maka harus punya 1 field khusus yang disebut key (kunci field).

Contoh :

Golongan	Gaji pokok	Tunjangan istr
1	1500	500
2	2500	750
3	2500	1000

Table dibawah dicocokkan dengan table diatas

Golongan	Nama	Job tittle	No karyawan	Gaji	Telepon
1	A
2	B
3	C

Deklarasi record dalam bahasa pemograman .

Program dalam pascal

Type

                Pegawai = record;

                                Job_tittle = string [20];

                                Emp_no = string [8];

                                Pay_rate = real;

                                Nama = string [25];

                                Telp_no = string [7];

                End;

TUGASSS !!!!

Array berdimensi 3 yang menggambarkan jumlah JKONTRAKAN untuk yang kaya dan yang miskin.

Keterangan :

Klg = keluarga

SPA = sudah punya anak

BPA = belum punya anak

Variabelnya (x,y,z)

X = jenis keluarga

Y = jenis belum/sudah punya anak

Z = jumlah keluarga

PERTEMUAN 3 STRUKTUR DATA

STACK dan QUEUE

STACK

Linear List adalah suatu struktur data yang merupakan himpunan terurut. 

v  Misal didefinisikan  suatu linear list A yang terdiri atas T buah elemen sebagai berikut :

A = [a1, a2, .........., aT]

v  Jika T = 0, maka A dikatakan sebagai “Null List”.

v  Suatu elemen dari sembarang posisi pada linear list A dapat dihilangkan.
Sebaliknya, suatu elemen baru dapat dimasukkan ke dalam list dan dapat
menempati sembarang posisi pada list tersebut.

v  Jadi suatu linear list dapat berkurang atau bertambah setiap saat.

DEFINISI STACK

Stack adalah suatu bentuk khusus dari linear list di mana operasi penyisipan dan penghapusan atas elemen-elemennyahanya dapat dilakukan pada satu sisi saja yang disebut sebagai “TOP”.

·         Misal diberikan Stack S sebagai berikut : S = [ S1, S2, .........., ST ] maka TOP(S) = ST

·         Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL.

·         Dari stack di atas, maka NOEL(S) = T.

elanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack S ini

dapat digambarkan sebagai berikut :

ILUSTRASI STACK

          Salah satu analogi yang dapat dikemukakan di sini adalah tumpukan piring atau barang lain. Pada saat kita hendak menumpuk piring-piring tersebut tentulah yang kita lakukan adalah meletakkan piring pertama pada tempatnya, selanjutnya meletakkan piring kedua di atas piring

Pertama dan demikian seterusnya. Pada saat kita akan mengambil satu piring maka yang diambil piring yang paling atas.

ILUSTRASI STACK-CONT

OPERASI PADA STACK

2 operasi dasar yang dapat dilaksanakan pada sebuah stack, yaitu :

#Operasi Push (menyisipkan data) memasukkan data ke dalam stack.

#Opersi Pop (menghapus data) menghapus elemen yang terletak pada posisi paling atas dari sebuah stack.

Contoh pemakaian operasi pust dan pop dan isi stack untuk setiap selesai eksekusi satu operasi.

Operasi yang dilakukan	Isi stack	Keterangan
Kondisi awal	Kosong	-
PUSH (‘A’,S)	A	-
PUSH (‘B’,S)	AB	-
PUSH (‘C’,S)	ABC	-
POP (Data,S)	AB	Data Berisi ‘C’
PUSH (‘D’,S)	ABD	-
POP (Data,S)	AB	Data Berisi ‘D’
POP (Data,S)	A	Data Berisi ‘B’

IMPLEMENTASI STACK DALAM BAHASA PEMOGRAMAN

·                     Implementasi dalam bahasa Pascal dapat dilakukan denagnmemanfaatkan struktur data record dan array. Arraydipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array yang sekaligus menggunakan IOS.

Pada Implementasi di bawah Ini :

·                     Konstanta maxelm menyatakan banyaknya elemen maksimum yang dapat ditampung oleh stack.

·                     Typeelemen adalah tipe data yang akan disimpan di dalam stack (bisa integer, word, real, boolean, char, string, atau lainnya). Banyak field yang menyatakan elemen dalam stack saat itu, yang sekaligus menyatakan TOS (Top of the stack)

DEKLARASI TIPE UNTUK TUMPUKAN (STACK)

            Type tumpukan = record

                        Banyak : 0..max_elm;

                        Elemen : array[1..max_elm] of typeelemen;

            End;

CONT

·                     Selain prosedur untuk POP dan PUSH, kita dapat pula menambahkan sejumlah fungsi untuk membantu penanganan kesalahan diantaranya adalah fungsi PENUHS (untuk mengecek apakah stack penuh) fungsi KOSONGS (untuk mengecek apakah stack kosong) fungsi SIZES (untuk mengetahui banyaknya elemen di dalam stack). Masing-masing sub program di atas dapat disajikan pseudocode-nya sebagai berikut :

#PSEUDOCODE

·                      Procedure Inisialisasi(var S : tumpukan);

begin

S. banyak--0

end;

·                     Function PENUHS(S : tumpukan): boolean;

begin

Jika S.banyak = maxelm maka PENUHS -- true

else PENUHS -- false

end;

#PSEUDOCODE CONT

·                     Function KOSONGS(S : tumpukan):boolean;

begin

If S.banyak = 0 then KOSONGS -- true

else KOSONGS -- false

end;

·                     Procedure PUSH(data : tipelemen; var S : tumpukan);

begin

If not KOSONGS(S) then

begin

            S.banyak -- S.banyak + 1

            S.elemen[S.banyak]-- data

end

else

Tampilan pesan kesalahan “Stack Penuh”

end;

·                     Procedure POP(var S : tumpukan; var data : typeelemen);

begin

if not KOSONGS(S) then

begin

            data -- S.elemen[S.banyak]

            S.banyak -- S.banyak -1

end

else

Tampilan pesan kesalahan “Stack Kosong”

End:

PENJELASAN OPERASI PADA STACK 

·                     Buat stack (stack) – create

           Membuat sebuah stack baru yang masih kosong.

Spesifikasi

ü  Tujuan           : mendefinisikan stack yang kosong

ü  Input              : stack

ü  Syarat awal   : tidak ada

ü  Output stack  : - (kosong)

ü  Syarat aktif    : stack dalam keadaan kosong

·                      Stack kosong (stack) – empty

            Fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak.

Spesifikasi

ü  Tujuan          : mengecek apakah stack dalam keadaan kosong

ü  Input             : stack

ü  Syarat awlal : tidak ada

ü  Output          : boolean

ü  Syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong.

·                     Stack penuh (stack) – full

           Fungsi untuk memeriksa apakah stack yang ada sudah penuh.

Spesifikasi

v  Tujuan          : mengecek apakah stack dalam keadaan penuh

v  Input             : stack

v  Syarat awlal : tidak ada

v  Output          : boolean

v  Syarat akhir : stack kosong bernilai true jika stack dalam keadaan penuh.

·                     Push (stack, info baru)

           Menambahkan sebuah elemen ke dalam stack       

Spesifikasi

v  Tujuan          : menambahkan elemen, info baru pada stack pada posisi paling atas.

v  Input             : stack dan info baru

v  Syarat awlal : stack tidak penuh

v  Output          : stack

v  Syarat akhir : stack bertambah satu elemen.

QUEUE (ANTRIAN)

Implementasi dalam bahasa Pascal dapat dilakukan dengan memanfaatkan struktur data record dan array. Array dipergunakan untuk menyimpan elemen-elemen yang dimasukkan. Selain itu diperlukan pula suatu variabel untuk mencatat banyaknya elemen yang ada di dalam array.

Definisi

·                     Queue adlah suatu linear lish dimana operasi DELETE terjadi pada sisi depan (FRONT) dan operasi INSERT terjadi pada sisi belakang(REAR).

Jika diberikan suatu Queue Q dengan elemen-elemennya yang terdiri atas Q₁, Q₂, ...., Q_T maka queue Q dituliskan :

            Q = [ Q₁, Q₂, ...., Q_T ]

Ø  FRONT (Q) = Q₁

Ø  REAR (Q) = Q_T

·                     Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasi NOEL (Q). 

·                     Catatan : Satu pengoperasian berlaku hanya untuk satu elemen.

CONT.

·                     Pada queue prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (Firs In Firs Out).

·                     Data-data di dalam antrian dapat bertipe integer, real, record

OPERASI-OPERASI PADA QUEUE (Q)

·         Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :

1.      CREATE

2.      ISEMPTY

3.      INSERT

4.      REMOVE

PENJELASAN :

CREATE

Bentuk umum            : CREATE (Queue)

Suatu operasi CREATE (Q) akan menghasilkan suatu queue kosong dengan nama Q, dan didefinisikan bahwa :

            NOEL (CREATE (Q))              = 0

            FRONT (CREATE (Q))           = tidak terdefinisi

            REAR  (CREATE (Q))             = tidak terdefinisi

ISEMPTY

Bentuk umumnya adalah : INEMPTY (queue)

Jika Q adalah Queue, maka ISEMPTY(Q) adalah suatu operasi yang digunakan untuk memeriksa apakah Queue Q adalah queue kosong. Jika hasil dari operasi ini akan berjenis data boolean (true/false),dengan bentuk sebagai berikut :

            ISEMPTY(Q)   = True, jika Q adalah queue kosong

                                       = False, jika Q bukan queue kosong

INSERT

Bentuk Umumnya : INSERT (Elemen, Queue)

INSERT(E,Q), dimana E = elemen dan Q = queue, adalah suatu operasi yang digunakan untuk memasukkan elemen E ke dalam queue Q.

Didefinisikan, bahwa elemen E akan menjadi elemen yang berada pada posisi REAR dan queue Q. Akibat dari operasi ini adalah :

-          REAR(insert(E,Q)) = E

-          NOEL(Q) bertambah satu dan Q_NOEL adalah E

jika Q adalah queue kosong maka, maka :

            ISEMPTY(INSERT(E,Q)) = False

Dalam bentuk statemen Pascal, biasanya dituliskan :

            IF ISEMPTY(Q) Then front (insert(E,Q)) = E

                        Else front(insert(E,Q = front(Q);

REMOVE

Bentuk umum : REMOVE(elemen, queue)

REMOVE(Q) berarti mengeluarkan elemen Q yang berada pada posisi FRONT. Akibat dari operasi ini, elemen Q akan berkurang satu dan elemen kedua (elemen yang berada disebelahnya) akan menjadi elemen yang berada pada posisi FRONT dari queue Q ini.

Selanjutnya, jika Q adalah queue kosong, maka REMOVE(Q) akanmenghasilkan suatu Error.

            IF NOEL(Q) = 0 Then Remove(Q) = erroe_condition

            Remove(create(Q)) = error_condition

DEKLARASI QUEUE DALAM PASCAL

Dalam bahasa pemrograman biasanya tidak ada fasilitas queue (built in queue). Untuk itu setiap programmer harus mendefinisikan sendiri dengan bantuan fasilitas yang ada. Pada umumnya fasilitas yang digunakan untuk mendeklarasikan queue adalah Array, Bentuk deklarasinya dalam bahasa sebagai berikut :

            TYPE StrukQueue = Record

                        Q : Array[1...100] of integer;

            Front, Rear : Integer;

            End;

VAR Q : StrukQueue;

PERTEMUAN 4
TUMPUKAN

Narasi infik
contoh= x+y
- operator di tulis di antara operan
sebagai contoh A* ()btc /d yang biasa berarti tambahan Bdan c terlebih dahulu dan kalikan dng A stelah itu bagi dng p
- notasi infix membutuhkan informasi extra
-rule mengenai operator providence
asosiation dan tanda kurang