PASCAL TENTANG STACK(MATERI KULIAH SEMESTER)

STACK (TUMPUKAN)

Stack  (tumpukan) dapat dikatakan sebagai list  ang operasi penghapusan dan pemyisipan elemennya dilakukan disatu ujung. Dalam kehidupan sehari-hari, terdapat banyak kejadian yang mempunyai sifat seperti stack, salah satunya adalah  cerita sdibawah ini:

Perhatuikan sebuah tumpukian piring disebuah warung makan. Piring-piring tersebut tewrsusun rapat dari atas ke bawah(membentuk barisan berurutan). Setiap kali ada pembeli dating, maka piring yang paling atas akan diambil(menghapus elemen) yang berarti mengurangi jumlah piring dalam tumpukan. Bila tumpukan






itu sudah habis atau tinggal sedikitmaka pegawai warung akan menambahkan piring lain yang masih bersih (menambah elemen) piring yang paling terakhir diletakkan pasti akan terletak ditumpukan paling atas dan piring yang terletak paling atas dalam tumpukan itu pasti merupakan tumpukan piring yang terakhir kali dimasukkan.

Kesimpulannya adalah penambahan dan penghapusan elemen hanya dapat dilakukan diujung atas tumpukan piring. Proses seperti itu bias disebut Last In Firs Out(LLIFO).

10.1  Definisi

Secara formal sebuah stack bertipe T didefinisikan sebagai sebuah barisan berhingga atas elemen-elemen bertipe T, bersama-sama dengan operasin berikut:

  1.      inisiasi stack menjadi kosong.

  2.      Mencari tau status stack kodong atau tidak

  3.      Mencari tahu stack penuh atau tidak.

  4.      Mencari panjang stack(jumlah elemen stack).

  5.      Memasukkan elemen baru pada stack, yaitu top stack jika stack tidak penuh.

  6.      Jika stack tidak kosong, mengambil elemen teratas(top stack).

10.2  Deklarasi

Stack dapat dideklarasikan sebuah record yang mempunyai sebuah array data untuk menyimpan elemen stack dan sebuah vafriabel top untuk menunjuk stack elemen atas (top element). Deklarasi selengkapnya sebagai berikut:

Tipestack = record

               Data  :  array[1..maks_stack] of tipe data

               Top   :  0..maks_stack;

        End.

Var S  : tipestack;

Tipestack adalah nama pengenal tipe untuk stack

Maks_stack merupakan jumlah meksimum elemen stack.

Data adalah array yang digunakan untuk menyimpan data-data stack. Array yang digunakan disini adalah model array linier. Indeks array dimulai dari s.d. maks_stack.

Tipedata adalah tipe data dari elemen-elemen stack.

Top dipakai untuk menunjuka elemen teratas dari stack. Nilai yang diizinkan adalah 0 s.d. maks-stack. Jika array diakses dari indeks kecil (1)  ke arah indeks besar (maks_stack), maka nilai ini akan bertambah 1 bila ada penambahan elemen; dan berkurang 1 jika ada penghapusan elemen.

S adalah nama variabel yang bertipe stack.

stack hanya diakses di suatu ujung saja. sehingga untuk menunjuk elemen ujung stack hanya diperlukan sebuah variabel, yaitu variabel top yang selalu menunjuak elemen paling atas atau yang terakhir kali masuk. Variabel ini berisi indeks array dan nilainya berubah-ubah dengan adanya elemen yang masuk dan keluar. Bila stack dalam keadaan kosong, maka top akan bernilai 0, yang tidak akan menunjuk satu ruang pada array.

10.3 operasi pada stack

1.    Instalasi . instalasi adalah proses untuk membuat stack dalam keadaan kosong. Proses ini dilakukan dengan mengisi variabel top dengan nilai yang tidak menunjuk salah satu elemen array. Pada model deklarasi di atas, maka top diisi dengan 0.

2.    Push. Push adalah proses memasukkan elemen baru kedalam stack. Prosesnya meliputi mengalokasikan ruang dengan mengubah nilai top untuk menunjuk ruang di sebelahnya, kemudian memasukan data ke dalam lokasi tersebut.

3.    Pop. Pop adalah proses untuk mengambil elemen dari stack. Prosesnya meliputi mengambil data dari elemen paling atas, kemudian menghapus elemen tersebut dengan cara mengubah nilai top untuk elemen dibawahnya.

4.    Size. Size adalah operasi untuk mengetahui jumlah elemen stack.

5.    Empty/Kosong. Empty adalah operasi untuk mengetahui status stack, kosong atau tidak.

6.    Full/Penuh. Full adalah operasi untuk mengetahui status stack, penuh atau tidak.

Bila stack  diimplementasikan dengan array yang diakses dari arah indeks terkecil ke arah indeks terbesar, maka operasi-operasi di atas dapat dituliskan dengan prosedur-prosedur berikut.

procedure inisialisasi ( var S : tipestack) ;

begin

       S. top := 0

End ;

Funcition penuh  (S : tipestack) : boolean ;

Begin

       Penuh :=  ( S. top = 0)

End ;

Function size (S : tipestack) : integer ;

Begin

       Size :=   S. top = 0

End ;

Procedure push (X ; tipedata; var S :

Tipestack);

Begin

       If  penuh (S) then

            Error

            {procedure untuk memberitahukan

            Stack penuh}

       else

       begin

            top := top + 1;

            S. data [top] := X;

       end;

endprocedure pop (var X ; tipedata; var S : tipestack) ;

begin

       if kosong (S) then

            Error {procedure untuk memberitahukan

                 Stack kosong}

       else

       Begin

            X := S.data [top] ;

       end;

end;

10.4 Contoh Program

Contoh 10.1: (program Membalik Urutan Angka)

Proses pada program ini diawali dengan meminta input angka dari keyboard. Proses ini akan terus dilakukan sampai data yang dibaca adalah 0. Data-data dapat dimasukkan sekaligus dengan menuliskan beberapa angka dan dipisahkan dengan spasi. Setelah selesai memasukan data, maka data-data tersebut akan dituliskan kembali dengan urutan terbalik. Hal ini dapat dilakukan dengan stack yang penjelasannya adalah setiap kali membaca angka, maka angka tersebut dimasukkan ke dalam stack, dan setelah selesai membaca, maka data-data diambil dari stack dan langsung dituliskan di layar.

{program balik angka oleh tim penyusun}

program Membalik_Urutan_angka;

uses crt;

const maks-stack = 10;

type tipedata = integer;

       tipestack = record

                                 top       : 0. .maks_stack;

                                 data     :

array [1. .maks_stack] of tipedata

                            end;

var  S          : tipestack;

       X         : tipedata;

       angka  : tipedata;

       lanjut   : boolean;

       temp    : char;

procedure error ;

begin

       write (‘stack penuh, angka terlalu banyak’);

       lanjut := false;

end;

{program utama}

begin

     repeat

       clrscr;

       writeln(‘membalik urutan angka’)

       writeln(‘memasukan barisan angka,

                      pisahkan dengan spasi

                     akhiri dengan angka 0’)

       write(‘ -> : ‘) ; read (angka);

       lanjut := true;

while lanjut and (angka < > 0) do

begin

  X := angka; push (X,S);

  Read (angka)

end;

write (‘ barisan angka dengan

              urutan terbalik’);

write (‘ <- : ‘);

while not (kosong (S)) do

begin

         pop (X,S) ; write (X, ‘   ‘) ;

end;

writeln (‘coba lagi dengan data yang lain (Y/N) ? [ ]’);

gotoxy (wherx-2, wherey) ; temp := readkey

until upcase (temp) = ‘N’

end.

Contoh 10.2: (MNW Recognizer)

Suatu bahasa pasti mempunyai kata-kata yang sah sesuai grammar-nya dan tidak sembarang susunan huruf akan mampunyai arti dalam bahasa itu. Misalkan ada suatu bahas –baik bahasa manusia atau bahasa pemograman --  menyatakan bahwa kata yang sah dan dapat diterima adalah kaka-kata yang mempunyai pola bentuk MNW, yaitu terdiri atas strimg yang dinotasikan dengan M, kemudian diikuti huruf ’N’ dan diikuti string yang dinotasikan dengan M,hanya saja susunannya terbalik

Misalkan kata-kata yang sah adalah iNi, SISIS, 1234N54321, sALAhNhALAs dan kata-kata yang tidak sah adalah 1234N432,1234N1234, SINISI.

Program ini akan melakukan pemeriksaan sah atau tidaknya suatu string yang dimasukkan, bberdasarkan aturanbahasa tersebut. Prosesnya meliputi membaca huruf-huruf dalam string M dan dimasukkan kedalam stack, kemudian membaca huruf-huruf dalam string W dan dicocokkan dengan huruf dalam stack. Bila semua hurufnya cocok dan urutannya juga tepat, maka kata yang diperiksa merupakan kata yang sah.

   {nama program :MNW Recognizer

               Oleh      :  tim penyusun}

   Program MNW_Recognizer;

Uses crt;

Cons make_stack = 10;

Tipe tipedata char;

          Tipestack = record;

          Top   : 0..maks_stack;

          Entry  :array[1..maks_stack] of  tipedata

  End;

Var    S          :  tipestack;

          X         :  tipedata;

          Kata    :  string;

Procedure periksa_kata(kata : strng);

Var index : integer;

          Sah  : Boolean;

Begin

          {merubah semua huruf menjadi huruf kapital}

          For index := 1 to leght (kata) do kata[index] : upcase(kata[index]);

          Sah := true;

          Index:= 1;

          Inisialisasi (S);

          {Memeriksa string M, huruf-huruf sebelum huruf N, dan dimasukkan ke satack}

          While (sah) and (index <= leght(kata)) and (kata[index]<> ‘N’) do

Begin

          X.data := kata[index];

          Push(X,S);

          Index :=index+1;

          If index = maks_stack+2 then

             Sah := false;

          End;

Index := index+1;

          {mengeset keposisi huruf setelah huruf N}

          {memeriksa string W, huruf setelah huruf N, dibandingkan dengan elemen di stack}

While (sah)

demilikian sedikit penjelasan tentang stack dari saya semoga bermanfaat.....