Stack (Tumpukan)

Download materi persentasi disini

LINIER LIST
Suatu struktur data umum yang berisi suatu kumpulan terurut dari elemen; jumlah elemen di dalam list dapat berubah-ubah.

Linier list A yang terdiri dari T elemen pada waktu t, dinotasikan sebagai :
    A = [ A1, A2, ..., AT]
Jika T = 0, maka A disebut “Empty List” atau “Null List”

Suatu elemen dapat dihilangkan/dihapus dari sembarang posisi dalam linier list, dan dapat pula dimasukkan elemen baru sebagai anggota list.
Contoh :

1. File, dengan elemennya berupa record
2. Buku telepon
3. Stack
4. Queue
5. Linear link list

STACK
Stack adalah suatu bentuk khusus dari linier list, dengan operasi penyisipan dan penghapusan dibatasi hanya pada satu sisinya, yaitu puncak stack (TOP).

Elemen teratas dari stack dinotasikan sebagai TOP(S).
Untuk stack S, dengan S = [S1, S2, S3, ..., ST] maka TOP(S) = ST

Jumlah elemen didalam stack kita notasikan dengan NOEL(S).
NOEL(S) menghasilkan nilai integer untuk stack S = [S1, S2, S3, ..., ST] maka            NOEL (S) = T.

Operator penyisipan (insertion) : PUSH
Operator penghapusan (deletion) : POP
Operasi stack : LIFO (Last In First Out), yaitu : yang terakhir masuk yang pertama keluar.

Jika ada NOEL elemen didalam stack, maka elemen ke NOEL merupakan elemen puncak (TOP).

Stack secara umum :
    S = [S1, S2, ..., SNOEL]
bahwa : SI berada di atas elemen SJ, untuk I > J
              SI akan dikeluarkan lebih dulu dari elemen di bawahnya.

Contoh stack : Tumpukan baki dalam cafetaria

Empat operasi dasar yang berlaku pada stack :
1. CREATE(stack)
2. ISEMPTY(stack)
3. PUSH(elemen, stack)
4. POP(stack)


CREATE
adalah operator yang menunjukkan suatu stack kosong dengan nama S.
Jadi :     NOEL(CREATE(S)) = 0
    TOP(CREATE(S)) adalah TIDAK TERDEFINISI.

ISEMPTY
adalah operator yang menentukan apakah stack S kosong.
Operandnya terdiri dari type data stack. Hasilnya merupakan type data Boolean:
ISEMPTY(S) = True. Jika S hampa, yakni bila NOEL(S) = 0.

PUSH
adalah operator yang menambahkan elemen E pada puncak stack S.
Hasilnya merupakan stack yang lebih besar.
PUSH(E,S). E ditempatkan sebagai TOP(S).

POP(stack)
adalah operator yang menghapus sebuah elemen dari puncak stack S.
Hasilnya merupakan stack yang lebih kecil.
POP(S)  mengurangi NOEL(S)
POP(CREATE(S))   ®  kondisi error
POP(PUSH(E,S)) = S

DEKLARASI STACK DALAM PASCAL

    TYPE STACKSTRUCT   =     RECORD

                STACK : ARRAY [1..100] of integer;

                TOPPTR : integer;

                END;

    VAR  S :  STACKSTRUCT;

NOEL(S) = TOP-PTR, ISEMPTY(S) = true, bila TOP-PTR = 0.