Stack
atau Tumpukan
DEFINISI
LINIER LIST
Apa itu list linier? List Linier
adalah suatu kumpulan yang terdiri dari beberapa elemen yang mempunya keturutan
tertentu, dimana setiap elemennya mengandung 2 bagian yaitu, informasi mengenai
tipe elemen tersebut dan alamat suksesor (next elemen).
Setiap elemennya terdiri dari 2 bagian:
Setiap elemennya terdiri dari 2 bagian:
type ElemenList: <info: Infotype,
Next: address>
Dengan infotype yaitu tipe terdefinisi yang menyimpan data, sedangkan next adalah address alamat berikutnya.
Sebuah list linier dapat dikenali dengan:
Sebuah list linier dapat dikenali dengan:
- Elemen Pertamanya, biasanya melalui alamat elemen pertama yang disebut: First
- Alamat Elemen berikutnya (suksesor), yaitu suatu informasi alamat elemen berikutnya, biasanya disebut NEXT
- Setiap elemennya memiliki alamat, yaitu tempat elemen disimpan dan diacu
- Elemen terakhir, suatu alamat elemen yang berada di akhir
Berikut ini contoh pengalamatan
elemen:
Alamat elemen pertama list L dapat diacu dengan notasi: FIRST(L)
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi Selektor: Info(P), Next(P)
Kelebihan dari menggunakan tipe data list adalah:
Alamat elemen pertama list L dapat diacu dengan notasi: FIRST(L)
Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi Selektor: Info(P), Next(P)
Kelebihan dari menggunakan tipe data list adalah:
- Pemakaian memori yang dinamis, sehingga kita bisa melakukan penghematan memori tergantung proses yang dikerjakan
- Untuk melakukan proses insert atau delete di list sangat sederhana
DEFINISI STACK
Stack adalah suatu bentuk khusus
dari linear list di mana operasi penyisipan dan penghapusan atas
elemen-elemennya hanya 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.
OPERASI DASAR PADA STACK
Ada empat operasi dasar yang didefinisikan pada stack, yaitu :
1. CREATE(stack)
2. ISEMPTY(stack)
3. PUSH(elemen,stack)
4. POP(stack)
CREATE
Operator ini berfungsi untuk membuat sebuah stack kosong dan
didefinisikan bahwa :
NOEL(CREATE(S)) = 0 dan TOP(CREATE(S)) = null
ISEMPTY
Operator ini berfungsi untuk menentukan apakah suatu stack adalah stack kosong.Operasinya
akan bernilai boolean, dengan definisi sebagai berikut :
ISEMPTY(S) = true, jika S adalah stack
kosong
= false,
jika S bukan stack kosong
atau
ISEMPTY(S) = true, jika NOEL(S) = 0
= false,
jika NOEL(S) 0
Catatan : ISEMPTY(CREATE(S)) = true.
PUSH
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
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 dan elemen pada posisi TOP
akan berubah. Operator POP ini tidak dapat digunakan pada stack kosong, artinya
:
POP(CREATE(S)) = error condition
Catatan : TOP(PUSH(E,S)) =
E
DEKLARASI
STACK PADA BAHASA PEMROGRAMAN
Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi nama STACK_STRUCT. Kemudian didefinisikan bahwa :
NOEL(S) = TOP_PTR
ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan
FALSE, jika TOP_PTR > 0.
Maka bentuk deklarasinya dalam PASCAL adalah :
TYPE Stack_Struct = Record
Stack : array[1..100] of integer
TopPtr : integer;
End;
VAR S : Stack_Struct;
Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu prosedur tersendiri, yaitu :
PROCEDURE PUSH(Eon : integer);
Begin
If (S.TopPtr < NoelMax) Then Begin
S.TopPtr := S.TopPtr + 1;
S.Stack [S.TopPtr] := Eon
End
Else Overflow_Condition
End;
PROCEDURE POP(Eoff : integer);
Begin
If (S.TopPtr > 0) Then Begin
Eoff := S.Stack[S.TopPtr];
S.TopPtr := S.TopPtr - 1
End
Else Underflow_Condition
End;
Catatan :
Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita melakukan operasi POP terhadap stack kosong. Eon adalah elemen yang akan dimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari dalam stack.
Dalam bahasa pemrograman, untuk menempatkan stack biasanya digunakan sebuah array. Tetapi perlu diingat di sini bahwa stack dan array adalah dua hal yang berbeda. Misalkan suatu variabel S adalah sebuah stack dengan 100 elemen. Diasumsikan elemen S adalah integer dan jumlah elemennya maksimum adalah 100 elemen. Untuk mendeklarasikan stack dengan menggunakan array, harus dideklarasikan pula variabel lain yaitu TOP_PTR yang merupakan indeks dari array. Variabel TOP_PTR ini digunakan untuk menyatakan elemen yang berada pada posisi TOP dalam stack tersebut. Selanjutnya gabungan kedua variabel ini diberi nama STACK_STRUCT. Kemudian didefinisikan bahwa :
NOEL(S) = TOP_PTR
ISEMPTY(S) = TRUE, jika TOP_PTR = 0 dan
FALSE, jika TOP_PTR > 0.
Maka bentuk deklarasinya dalam PASCAL adalah :
TYPE Stack_Struct = Record
Stack : array[1..100] of integer
TopPtr : integer;
End;
VAR S : Stack_Struct;
Selanjutnya, untuk keperluan operasi PUSH dan POP harus dibuat suatu prosedur tersendiri, yaitu :
PROCEDURE PUSH(Eon : integer);
Begin
If (S.TopPtr < NoelMax) Then Begin
S.TopPtr := S.TopPtr + 1;
S.Stack [S.TopPtr] := Eon
End
Else Overflow_Condition
End;
PROCEDURE POP(Eoff : integer);
Begin
If (S.TopPtr > 0) Then Begin
Eoff := S.Stack[S.TopPtr];
S.TopPtr := S.TopPtr - 1
End
Else Underflow_Condition
End;
Catatan :
Overflow adalah suatu keadaan di mana kita melakukan operasi PUSH terhadap stack dalam keadaan penuh. Underflow adalah keadaan di mana kita melakukan operasi POP terhadap stack kosong. Eon adalah elemen yang akan dimasukkan ke dalam stack dan Eoff adalah elemen yang akan dikeluarkan dari dalam stack.
Tidak ada komentar:
Posting Komentar