Stack

Stack (tumpukan) merupakan struktur data yang meniru bagaimana proses menyimpan dan mengambil suatu benda pada tumpukan.

Konsep stack : LIFO (Last In First Out)
artinya benda yang terakhir disimpan pada tumpukan (paling atas) adalah benda pertama yang diambil.
Implementasi stack:
type stack : record
<
       top : integer;
       isi : array [1 .. maks] of item;
>
Isi : array yang memuat data dalam tumpukan
Item : tipe data yang disimpan datam stack, misal int, char, dan sebagainya
Top : posisi teratas dari tumpukan
Top = 0, jika stack kosong
Top = maks, jika stack penuh
Setiap mengisi data, top bertambah 1, setiap menambil data top berkurang 1.

Proses utama dalam stack :
#  Push : proses menyimpan
#  Pop : proses mengambil
Proses tambahan :
#  Initialize : proses memulai, yaitu menciptakan stack kosong
#  Peek : melihat elemen teratas
#  IsEmpty : memeriksa apakah suatu tumpukan kosong

1. Push (Penyimpanan Data)

Prosedur push (input x : item; in-out s : stack)
{prosedur menempatkan item pada posisi top
dari stack}

Definisi Variabel
int atas;

Rincian Langkah
if s.top = maks
       then write ("sudah penuh");
else
       s.top ← s.top + 1;
       atas ← s.top;
       s.isi[atas] ← x;
endif

2. Pop (Pengambilan Data)

Prosedur pop (output x : item; in-out s : stack)
{prosedur mengambil data dari tumpukan pada
posisi top dari stack}

Definisi Variabel
int atas;

Rincian Langkah
if s.top = 0;
       then write ("tumpukan kosong");
else
       atas ← s.top;
       x ← s.isi[atas];
       s.top ← s.top - 1;
endif

3. Initialize (Memulai)

Prosedur initialize (in-out s : stack)
{memulai suatu stack}

Definisi Variabel
{tidak ada}

Rincian Langkah
       s.top ← 0;

4. Peek

Fungsi peek (in s : stack) → item
{fungsi untuk melihat elemen teratas dari suatu stack}

Definisi Variabel
item x;
int  atas;

Rincian Langkah
       atas ← s.top;

       x ← s.isi[atas];
       return x;

5. IsEmpty

Fungsi IsEmpty (in s : stack) → boolean
{fungsi untuk memeriksa apakah stack kosong}

Definisi Variabel
{tidak ada}

Rincian Langkah
if (s.top = 0)
       then return true;
else
       return false;
endif

Soal 1
Membalik suatu kalimat yang dimasukkan lewat keyboard. Misalkan inputnya "program tumpukan" maka outputnya "nakupmut margorp".

Jawaban :
1. Setiap huruf mulai dari kiri dimasukkan ke dalam stack s (proses push), hingga seluruhnya ada di dalam s
2. Satu per satu huruf diambil dari s (proses pop)

Algoritma balik_kalimat
{membalikkan kalimat yang diinput dengan memakai stack}

Definisi Variabel
int maks = 128;
char item;
type stack : record;
<
        top : integer;
        isi : array[1 .. maks] of item;
>
stack s;
Prosedur push(input x : item; in-out s : stack);
Prosedur pop(input x : item; in-out s : stack);
Prosedur initialize(in-out s : stack);
string kalimat;
int panjang, i;
char x;

Rincian Langkah
initialize(s);
write("masukkan 1 kalimat : ");
read(kalimat);
panjang ← len(kalimat);
{masukkan huruf per huruf ke stack}
for (i = 1 to panjang step 1)
        x ← substr(kalimat, i, 1);
        push(x, s);
endfor
{baca kembali huruf per huruf dari stack}
for (i = 1 to panjang step 1)
        pop(x, s);
        write(s);
endfor

Soal 2 (UAS Struktur Data 2013/2014 Informatika UNDIP)
Misalkan data 5, 7, 10, 11, dan 3 di push ke stack yang kosong dengan urutan tesebut, kemudian di pop empat kali, hasil poppedelement di push lagi dengan urutan terbalik (yang di pop terakhir di push pertama). Maka top elemen dari stack adalah...

Jawaban :