Stack atau Tumpukan (Pengantar Struktur Data)

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:  

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:

1. Elemen Pertamanya, biasanya melalui alamat elemen pertama yang disebut: First
2. Alamat Elemen berikutnya (suksesor), yaitu suatu informasi alamat elemen berikutnya, biasanya disebut NEXT
3. Setiap elemennya memiliki alamat, yaitu tempat elemen disimpan dan diacu
4. 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:

1. Pemakaian memori yang dinamis, sehingga kita bisa melakukan penghematan memori tergantung proses yang dikerjakan
2. 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.