stack (tumpukan)

Stack (Tumpukan)

2

Definisi Stack (Tumpukan)

Stack adalah list linier yang: Dikenali elemen puncaknya (TOP) Aturan penyisipan dan penghapusan

elemennya tertentu Penyisipan selalu dilakukan di “atas”

(TOP) Penghapusan selalu dilakukan pada TOP

Stack tersusun secara LIFO (Last In First Out)

3

Definisi Stack

TOP

BOTTOM

4

Representasi Stack secara lojik digambarkan sebagai list linier yang setiap tipe elemennya adalahType ElmtS : <Info : Infotype, Next : address>

Alamat elemen terbaru (TOP) dan alamat elemen terlama (BOTTOM) juga dicatat. Namun dalam implementasi belum tentu BOTTOM digunakan.

5

Sehingga jika S adalah sebuah stack, danP adalah sebuah address maka: Top(S) adalah alamat elemen TOP,

dimana operasi penyisipan dan penghapusan dilakukan

Info(P) adalah informasi yang disimpan pada alamat P

Next(P) adalah alamat suksesor P

6

Traversal Pada Stack Pada stack jarang sekali dilakukan

operasi traversal, karena keunikan stack justru pada operasi yang hanya menyangkut elemen TOP.

Namun jika memang dibutuhkan traversal, misalnya untuk mencetak isi stack, maka skema traversal suatu stack persis sama dengan skema traversal list linier biasa, dengan mengganti First(L) menjadi TOP(S).

7

Operasi dan Fungsi dasar (Primitif) Pada Stack

Diberikan S adalah Stack dengan elemenS, maka definisi fungsional stack adalah : StackEmpty :S boolean {Test stack kosong, true jika kosong, false jika tidak} CreateStack: S {Membuat sebuah stack kosong} Push : Elmt x S S {Menambahkan sebuah ElmtS sebagai TOP. TOP

berubah nilainya} Pop : S S x ElmtS {Mengambil nilai elemen TOP, sehingga Top yang

baru adalah elemen yang datang sebelum elemen TOP, mungkin Stack menjad i kosong}

8

Test stack Kosong

Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong}

Kamus :

Algoritma (TOP(S) = Nil)

9

Pembuatan Stack Kosong

Procedure CreateEmptyS (Output S : Stack){Membuat sebuah stack kosong}{I.S : sembarang}{F.S : sebuah stack S kosong siap dipakai terdefinisi}

Kamus

Algoritma : TOP(S) Nil

10

Penambahan sebuah elemen pada Stack (Push)

Procedure Push@(Input/Output S : Stack Input P : address){Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya}

Kamus

Algoritma {insert sebagai elemen pertama} Next (P) TOP(S) TOP(S) P

11

Penambahan sebuah elemen pada Stack (Push)Procedure Push (Input/Output S : Stack Input E : Infotype){Menambahkan sebuah elemen baru pada TOP, dengan elemen yang diketahui informasinya}

Kamus P: address

Algoritma Alokasi (P) {alokasi selalu berhasil} Info(P) E Next (P) TOP(S) TOP(S) P

12

Penghapusan sebuah elemen pada Stack

Procedure PopStack@ (Input/Output S : Stack; Output P : address){I.S : stack tidak kosong}{F.S : alamt elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P}{Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong}

Kamus P :address

Algoritma P TOP(S) TOP(S) Next (TOP(S))

13

Penghapusan sebuah elemen pada Stack

Procedure PopStack (Input/Output S : Stack; Output E : Infotype){I.S : stack tidak kosong}{F.S : info elemen TOP disimpan pada E, alamat Top yang lama didealokasi}{Menghapus elemen stack, stack tidak boleh kosong dan mungkin setelah penghapusan stack menjadi kosong}

Kamus P : address

Algoritma P TOP(S); E Info(P) TOP(S) Next (TOP(S)) Dealokasi (P)

14

Representasi Berkait dengan Pointer KAMUS{Definisi sebuah stack S dgn representasi berkait dgn pointer} type infotype : ...{Type terdefinisi, menyimpan informasi elemen stack} type address : ^ElmtStack type Elmtstack : <Info : infotype, Next : address> type Stack : <Top : address> S : Stack{Cara penulisan Top(S) ditulis S.Top Info(P) ditulis P^.Info Next(P) ditulis P^.Next }

15

Test stack Kosong

Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong}

Kamus :

Algoritma (S.TOP = Nil)

16

Pembuatan Stack Kosong

Procedure CreateEmptyS (Output S : Stack){Membuat sebuah stack kosong}{I.S : sembarang}{F.S : sebuah stack S kosong siap dipakai terdefinisi}

Kamus

Algoritma : S.TOP Nil

17

Penambahan sebuah elemen pada Stack (Push)

Procedure Push@(Input/Output S : Stack Input P : address){Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya}

Kamus

Algoritma {insert sebagai elemen pertama} P^.Next S.TOP S.TOP P

18

Penghapusan sebuah elemen pada Stack

Procedure PopStack@ (Input/Output S : Stack; Output P : address){I.S : stack tidak kosong}{F.S : alamt elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P}{Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong}

Kamus P :address

Algoritma P S.TOP

S.TOP S.TOP^.Next

19

Representasi berkait dengan tabelKamus {Definisi sebuah stack S dengan representasi berkait}constant Nil : integer = 0Nmin : integer = 1Nmax : integer = 100type address : integer [Nmin..Nmax, Nil]type infotype : ...{terdefinisi}type ElmtS : <Info:infotype, next : address> type Stack : <TOP : address, TabElmt: array[Nmin..Nmax] of ElmtS>S:Stack{cara penulisan : Top(S) dituliskan S.Top Info(P) dituliskan S.TabElmt[P].Info Next(P) dituliskan S.TabElmt[P].Next Primitif Alokasi : AllocTab(P) Dealokasi : DeallocTab(p) }

20

Test stack Kosong

Function StackEmptyT (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong}

Kamus :

Algoritma → S.Top = Nil

21

Pembuatan Stack Kosong

Procedure CreateEmptyT (Output S : Stack){Membuat sebuah stack kosong}{I.S : sembarang}{F.S : sebuah stack S kosong siap dipakai terdefinisi}

Kamus

Algoritma : S.Top ← Nil

22

Penambahan sebuah elemen pada Stack (Push)

Procedure Push@(Input/Output S : Stack Input P : address){Menambahkan sebuah elemen baru pada TOP, dengan elemen yang telah diketahui alamatnya}

Kamus

Algoritma {insert sebagai elemen pertama} S.TabElmt[P].Next←S.TOP S.TOP ← P

23

Penghapusan sebuah elemen pada Stack

Procedure PopStack@ (Input/Output S : Stack; Output P : address){I.S : stack tidak kosong}{F.S : alamat elemen TOP disimpan pada P, sehingga informasinya dapat diakses melaui P}{Menghapus elemen stack, stack tidak boleh kosong dan mungkin seteleh penghapusan stack menjadi kosong}

Kamus P :address

Algoritma P ← S.TOP S.TOP ← S.TabElmt[S.TOP].Next {Jika menjadi kosong, S.TOP = Nil}

24

Representasi kontigu Karena kemudahan

operasinya, biasanya stack lebih banyak direpresentasikan sebagai tabel kontigu, dengan TOP adalah salah satu nilai ekstrem indeks terdefinisi.

Stack direpresentasikan oleh sebuah tabel {1..Nmax} dengan NMax adalah kostanta yang diperkirakan sebagai jumlah maksimum elemen yang ditampung stack.

23.00 12.5 0.00 34.8

TOP

1

2

3

4

NMax

25

Kamus :{Definisi sebuah stack S dengan representasi kontigu}constant Nil : integer = 0Nmax : integer = 100type address : integer [0..Nmax]type ElmtS : ...{terdefinisi, terdiri dari Info saja}type Stack : <TOP : address, TabElmt: array[1..Nmax] of ElmtS>S:Stack{cara penulisan : Top(S) dituliskan S.Top Info(P) dituliskan S.TabElmt[P] Next(P) dituliskan P←P-1 Primitif Alokasi : AllocTab(P) Dealokasi : DeallocTab(P) }

26

Test stack Kosong

Function StackEmpty (S: STACK) boolean {Test stack kosong : mengirim true jika tumpukan kosong, false jika tumpukan tidak kosong}

Kamus :

Algoritma → S.Top = Nil

27

Pembuatan Stack Kosong

Procedure CreateEmpty (Output S : Stack){Membuat sebuah stack kosong}{I.S : sembarang}{F.S : sebuah stack S kosong siap dipakai terdefinisi}

Kamus

Algoritma : S.Top ← Nil

28

Penambahan sebuah elemen pada Stack (Push)

Procedure PushTab(input/output S: Stack, input E : ElmtS){menambah sebuah elemen baru pada TOP sebuah stack, dengan elemen yang diketahui informasinya}{IS : Stack mungkin kosong, E terdefinisi, alokasi alamat selalu berhasil:S.TOP<NMax FS : TOP(S) berisi E}

Kamus

Algoritma :S.TOP ← S.TOP+1S.TabElmt[S.TOP]←E

29

Penghapusan sebuah elemen pada Stack

procedure PopStack (input/output S: Stack, output E : ElmtS){menghapus elemen Stack, Stack tidak boleh kosong dan mungkin menjadi kosong}{IS : Stack tidak kosong FS : elemen TOP disimpan pada E}

Kamus

Algoritma :E←S.TabElmt[S.TOP]S.TOP ← S.TOP - 1{tidak perlu dealokasi sebab direpresentasi dengan tabel kontigu}

30

Studi Kasus Stack Ekspresi Matematika dengan notasipostfix (Polish) Diberikan sebuah ekpresi matematika postfix dengan

operator [‘ * ’, ’ / ’, ‘+’,’-’,’^’] Operan dari ekspresi dapat berupa sebuah karakter

abjad [‘A’..’Z’] atau sebuah nilai yang terdiri dari satu angka [‘0’..’9’]

Contoh Ekspresi Arti AB*/ (A*B) /C ABC^/DE*+AC*- (A / (B^C) +

(D*E) – (A*C)

31

Studi Kasus Stack

Catatan Dalam penulisan ekspresi yang tidak

disederhanakan, tiap operan atau operator disebut token.

Didefinisikan token adalah sebuah ‘kata’ (deretan karakter yang tidak mengandung blank), dan diantara dua kata dipisahkan satu atau beberapa operator

32

Studi Kasus StackProgram Ekspresi{Menghitung sebuah ekspresi matematika yang ditulis secara posfix, dengan memperhatikan urutan evaluasi berdasarkan operator}

Kamus type infotype : character type address : ^ElmtStack type Elmtstack : <Info : infotype, Next : address> type Stack : <Top : address> S : Stack CT,OP1,OP2 : character Type token : ……… {terdefinisi} Procedure first-token {mengirim token yang pertama}

33

Studi Kasus StackProcedure Next-token {mengirim token yang berikutnya}Function EndToken boolean {true jika proses akuisisi mendapatkan Token kosong. Merupakan akhir ekpresi. Model dengan mark}Function operator (CT : token) tokenFunction hitung (OP1,OP2, operator : token) token{menghitung ekspresi, mengkonversi menjadi token}

34

Studi Kasus StackAlgoritma First-token If (end-token) then Otuput (‘ekspresi kosong’) Else Repeat Depend on (CT) {CT adalah current token} Not operator (CT): push(CT,S) Operator (CT): {CT adalah operator} Pop(S,OP2) Pop(S,OP1) Push(S,hitung(OP1,OP2,CT)) Next-Token(CT) Until (End-token){tuliskan hasil}