Senin, 04 Mei 2015

stack (tumpukan)


STACK (TUMPUKAN)

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 di dalam 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 COBOL DAN PASCAL

Cara yang paling sederhana adalah membentuk Stack dalam bentuk semacam Array.

Penempatan Stack dalam suatu Array mengakibatkan suatu keterbatasan, yakni bahwa elemen Stack harus homogen.

Keharusan pemrograman untuk menentukan batas atas dari subskrip Array, walaupun Stack sebenarnya tidak memiliki batas maksimum dalam jumlah elemen.

Yang membedakan Stack dengan Array adalah banyaknya elemen Stack dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah array selalu tetap.

Deklarasi dari Variabel S yang bertipe data Stack. Diasumsikan bahwa elemen dari S masing-masing bertipe data integer dan panjang Stack maksimum 100 elemen.
Kita mendeklarasikan sebuah Array yang dilengkapi dengan Variabel TOP-PTR. Variabel TOP-PTR ini menyatakan subkrip dari elemen TOP(S) dari Stack.

COBOL

01     STACK-STRUCT   ® kombinasi dari array dan indikator untuk TOP
         02        S OCCURS 100 TIMES PIC 9(5)
         02        TOP-PTR                       PIC 9(3)

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.


OPERASI PUSH & POP

PUSH

       IF TOP-PTR < NOEL-MAX
                 THEN COMPUTE TOP-PTR = TOP-PTR + 1
                            MOVE EON  TO S(TOP-PTR)
                 ELSE Overflow condition



POP

       IF TOP-PTR > 0
                 THEN MOVE S(TOP-PTR) TO EOFF
                            COMPUTE TOP-PTR = TOP-PTR  -  1
                 ELSE Underflow condition

EON : elemen yang di PUSH ke dalam S.
EOFF : elemen yang di POP ke luar S.
NOEL-MAX : panjang max stack.


PUSH

         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;


POP

         Procedure POP (var eoff : integer);
         Begin
               if (s.topptr > 0)
               then
                        Begin
                              eoff := s.stack [s.topptr];
                              s.topptr := s.topptr - 1;
                        End;
               else Underflow Condition
         End;


APLIKASI STACK

1.    Penjodohan Tanda Kurung/Matching Parantheses
       ALGORITMA
       a.  Amati barisan elemen dari kiri ke kanan
       b.  ·   bila bertemu ‘(‘, maka ‘(‘ di push ke dalam stack.
            ·   bila bertemu ‘)’, maka periksa stack hampa atau tidak.
                 bila hampa ® ada ‘)’ dan tidak ada ‘(‘ (error)
                 bila tidak hampa ® ada sepasang ‘(‘ & ‘)’ & POP elemen     keluar




2.    NOTASI POSTFIX
       ALGORITMA
       Amati barisan dari kiri ke kanan
       1.  Jika ‘(‘, maka PUSH ke dalam stack.
       2.  Jika ‘)’, POP elemen dalam stack sampai simbol ‘(‘. Semua di POP merupakan output kecuali ‘(‘ tadi.
       3.  Jika simbol operand, langsung merupakan output.
       4.  Jika simbol operator, maka :
            Jika elemen TOP stack dengan level >= maka POP sebagai output teruskan sampai ‘(‘.
            elemen TOP <, operator yang diamati di PUSH ke dalam stack.
       5.  Bila ‘;’ kita POP semua elemen dalam stack hingga hampa.

APLIKASI STACK

Notasi Postfix

Contoh :
Notasi Infix : ((A+B) * C/D+E^F)/G;


sumber : 
staffsite.gunadarma.ac.id
http://sisfo.binadarma.ac.id/upload/materi/8868_SD4-STACK%20(Tumpukan).pdf








stack (tumpukan) mata kuliah struktur data


STACK (TUMPUKAN)

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 di dalam 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 COBOL DAN PASCAL

Cara yang paling sederhana adalah membentuk Stack dalam bentuk semacam Array.

Penempatan Stack dalam suatu Array mengakibatkan suatu keterbatasan, yakni bahwa elemen Stack harus homogen.

Keharusan pemrograman untuk menentukan batas atas dari subskrip Array, walaupun Stack sebenarnya tidak memiliki batas maksimum dalam jumlah elemen.

Yang membedakan Stack dengan Array adalah banyaknya elemen Stack dapat bertambah atau berkurang setiap waktu, sementara banyaknya elemen sebuah array selalu tetap.

Deklarasi dari Variabel S yang bertipe data Stack. Diasumsikan bahwa elemen dari S masing-masing bertipe data integer dan panjang Stack maksimum 100 elemen.
Kita mendeklarasikan sebuah Array yang dilengkapi dengan Variabel TOP-PTR. Variabel TOP-PTR ini menyatakan subkrip dari elemen TOP(S) dari Stack.

COBOL

01     STACK-STRUCT   ® kombinasi dari array dan indikator untuk TOP
         02        S OCCURS 100 TIMES PIC 9(5)
         02        TOP-PTR                       PIC 9(3)

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.


OPERASI PUSH & POP

PUSH

       IF TOP-PTR < NOEL-MAX
                 THEN COMPUTE TOP-PTR = TOP-PTR + 1
                            MOVE EON  TO S(TOP-PTR)
                 ELSE Overflow condition


POP

       IF TOP-PTR > 0
                 THEN MOVE S(TOP-PTR) TO EOFF
                            COMPUTE TOP-PTR = TOP-PTR  -  1
                 ELSE Underflow condition

EON : elemen yang di PUSH ke dalam S.
EOFF : elemen yang di POP ke luar S.
NOEL-MAX : panjang max stack.


PUSH

         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;


POP

         Procedure POP (var eoff : integer);
         Begin
               if (s.topptr > 0)
               then
                        Begin
                              eoff := s.stack [s.topptr];
                              s.topptr := s.topptr - 1;
                        End;
               else Underflow Condition
         End;


APLIKASI STACK

1.    Penjodohan Tanda Kurung/Matching Parantheses
       ALGORITMA
       a.  Amati barisan elemen dari kiri ke kanan
       b.  ·   bila bertemu ‘(‘, maka ‘(‘ di push ke dalam stack.
            ·   bila bertemu ‘)’, maka periksa stack hampa atau tidak.
                 bila hampa ® ada ‘)’ dan tidak ada ‘(‘ (error)
                 bila tidak hampa ® ada sepasang ‘(‘ & ‘)’ & POP elemen     keluar




2.    NOTASI POSTFIX
       ALGORITMA
       Amati barisan dari kiri ke kanan
       1.  Jika ‘(‘, maka PUSH ke dalam stack.
       2.  Jika ‘)’, POP elemen dalam stack sampai simbol ‘(‘. Semua di POP merupakan output kecuali ‘(‘ tadi.
       3.  Jika simbol operand, langsung merupakan output.
       4.  Jika simbol operator, maka :
            Jika elemen TOP stack dengan level >= maka POP sebagai output teruskan sampai ‘(‘.
            elemen TOP <, operator yang diamati di PUSH ke dalam stack.
       5.  Bila ‘;’ kita POP semua elemen dalam stack hingga hampa.

APLIKASI STACK

Notasi Postfix

Contoh :
Notasi Infix : ((A+B) * C/D+E^F)/G;


sumber : 
staffsite.gunadarma.ac.id
http://sisfo.binadarma.ac.id/upload/materi/8868_SD4-STACK%20(Tumpukan).pdf