Struktur Data - Stack

STACK

3.1 Deskripsi Stack

Stack sering disebut LIFO (Last In, First Out) yaitu elemen yang lebih akhir disisipkan menjadi elemen yang paling dulu diambil. Stack juga disebut pushdown 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 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).

Karakteristik pada stack adalah sebagai berikut :

1.      Elemen stack yaitu item-item data yang terdapat di elemen stack.

2.      Top (elemen puncak dari stack).

3.      Jumlah elemen pada stack.

4.      Status / kondisi stack.

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

Dibawah ini merupakan ilustrasi bagaimana tampilan dari stacks

 Stack akan berarti penuh jika jangkauan cell teratas disimbolkan dengan n-1. Jika nilai

teratas / top sama dengan -1, stack berarti kosong.

Operasi-operasi pokok stack adalah:

1.      CreateStack(S), menciptakan stack kosong S.

2.      InsertStack(S,x), memasukan elemen x sebagai elemen akhir di S.

3.      RemoveStack(S,x), mengambil elemen depan di stack S ke elemen x.

Operasi-operasi pengakses tambahan yang dapat dilakukan adalah :

1.      TopStack(S), mengirim elemen puncak tanpa menghapusnya.

2.      TailStack(S), mengirim elemen terakhir tanpa menghapusnya.

Operasi-operasi query tambahan yang dapat dilakukan adalah :

1.      isEmptyStack(S), mengirim apakah antrian S adalah kosong.

2.      isFullStack(S), mengirim apakah antrian S adalah penuh bila kapasitas antrian S didefinisikan.

3.      isOverflowStack(S), mengirim apakah antrian S telah mengalami overflow.

4.      isUnderflowStack(S), mengirim apakah antrian S telah mengalami underflow.

Operasi-operasi terhadap seluruh antrian S antara lain adalah :

1.      SizeStack(S), mengetahui jumlah elemen yang berada di antrian S.

2.      isEqualStack(S₁,S₂), mengirim apakah antrian S₁ dan S₂ adalah sama isinya.

Tujuh  operasi dasar yang berlaku pada stack :

1.      CREATE

2.      IS EMPTY

3.      PUSH

4.      POP

5.      PEEK

6.      EMPTY

7.      FULL

8.      CLEAR

CREATE adalah operator yang menunjukkan suatu stack kosong dengan nama S.

Jadi : NOEL(CREATE(S)) = 0

TOP(CREATE(S)) adalah TIDAK TERDEFINISI.

membuat sebuah stack baru yang masih kosong

void create()

{

top=-1;

}

spesifikasi:

-          Tujuan : mendefinisikan stack yang kosong

-          input : stack

-          syarat awal : tidak ada

-          output stack : - (kosong)‏

-          syarat akhir : stack dalam keadaan kosong

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.

fungsi untuk menentukan apakah stack dalam keadaan kosong atau tidak

int Empty()

{

return top==-1;

}

spesifikasi:

-          tujuan : mengecek apakah stack dalam keadaan kosong

-          input : stack

-          syarat awal : tidak ada

-          output : boolean

-          syarat akhir : stack kosong bernilai true jika stack dalam keadaan kosong

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).

menambahkan sebuah elemen kedalam stack.

void Push(DataType item)

{

if(Full())

{ cerr<<"stack overflow!"<<endl<<endl;}

else

{

top++;

stacklist[top]=item;

}

}

spesifikasi:

-          tujuan : menambahkan elemen, info baru pada stack pada posisi paling atas

-          input : stack dan Info baru

-          syarat awal : stack tidak penuh

-          output : stack

-          syarat akhir : stack bertambah satu elemen

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

mengambil elemen teratas dari stack

DataType Pop()

{

DataType temp;

if(Empty())

{cerr<<"Stack kosong "<<endl<<endl;}

else

{temp=stacklist[top]; top--;}

return temp;

}

spesifikasi:

-          tujuan : mengeluarkan elemen dari stack yang berada pada posisi paling atas

-          input : stack

-          syarat awal : stack tidak kosong

-          output : stack dalam info pop

-          syarat akhir : stack berkurang satu elemen

FULL adalah operator yang menunjukan suatu stack penuh

int Full()

{

return top == Maxstacksize-1;

}

spesifikasi:

-          tujuan : mengecek apakah stack dalam keadaan penuh

-          input : stack

-          syarat awal : tidak ada

-          output : boolean

-          syarat akhir : stack penuh bernilai true jika stack dalam keadaan penuh

CLEAR adalah operator yang digunakan untuk menghapus stack

void Clear()

{

top=-1;

}