Stack

Lusiana Agustien
Apa Itu Stack
Stack Dalam Struktur Data
o Stack adalah suatu Abstract Data Type, secara umum digunakan pada
kebanyakan Bahasa pemprograman
o Dinamakan stack karena berperilaku seperti halnya tumpukan dalam
dunia nyata
o Stack digunakan sebagai container untuk menampung object dan
mengeluarkannya kembali dengan urutan tertentu
Cara Operasi
Stack
Beropasi dengan cara Last In First Out
(LIFO)

o Push()
Operasi Penambahan item
diatas Tumpukan (Stack)
o Pop()
Operasi Pengambilan Atau
mengeluarkan item dari
tumpukan (Stack)
Implementasi Stack dengan Array
o Kondisi Stack ditentukan oleh posisi atau isi TOP.

Kondisi Stack Posisi TOP

KOSONG Top = -1
PENUH Top = n-1
BISA DIISI Top < n-1
ADA ISINYA Top > -1
 ILUSTRASI PUSH DAN POP
• Gambar dibawah hanya menunjukkan dalam tumpukan hanya
bisa menambah atau mengambil sebuah kotak lewat satu
ujung, yaitu ujung bagian atas

Deklarasi Struktur Data

Maximum Stack = Record
4 Isi [5]
Isi : array[1..n] of Tipe
3 Isi [4] Data
2 Isi [3] Atas : integer
1 Isi [2] End

0 Isi [1]

Stack S
Stack with Array of Struct
o Definisikan Stack dengan menggunakan suatu
struct
o Definisikan konstanta MAX_STACK untuk
menyimpan maksimum isi stack
o Elemen struct Stack adalah array data dan
SPuntuk menadakan posisi data teratas
o Buatlah variabel tumpukan sebagai
implementasi dari struct Stack
o Deklarasikan operasi-operasi/function di atas
dan buat implemetasinya
Program Stack
o Contoh deklarasi MAX_STACK
#define MAX_STACK 10

o Contoh deklarasi STACK dengan struct dan array data

typedef struct STACK{

int sp;

int s[10];

};

o Deklarasi/buat variabel dari struct

STACK tumpukan;
Program Stack (2)
Inisialisasi Stack
o Pada mulanya isi SP dengan -1, karena array dalam bahasa
C dimulai dari 0, yang berarti bahwa data stack adalah
KOSONG!
o SP adalah suatu variabel penanda dalam Stack yang
menunjukkan elemen teratas data Stack sekarang.
o Top Of Stack akan selalu bergerak hingga mencapai MAX of
STACK yang menyebabkan stack PENUH!
Inisialisasi stack
9 Max_Stack
8
7
6
5
4
3
2
1
0 SP = -1

Ilustrasi Stack pada saat inisialisasi!

FUNGSI PUSH
Operasi Push adalah menambah elemen kedalam
stack S, dimana penambahan dapat dilakukan jika
stack itu belum penuh.
Stack dikatakan penuh Jika posisi Top sudah
berada pada posisi n
(If jawaban == 0)
Push()
int Push(int nil)
If jawaban ==0 then
[Link]++
st.s[[Link]] = nil
Else
stack sudah penuh
sp = 0
Endif

stack s
PUSH()
int Push(int nil)
If jawaban ==0 then

[Link]++
st.s[[Link]] = nil
Else
top = 1
stack sudah penuh
Endif

stack s
Push()
int Push(int nil)
If jawaban ==0 then
[Link]++

st.s[[Link]] = nil
Else
top = 1
stack sudah penuh
endif

stack s
Push()
int Push(int nil)
If jawaban ==0 then

[Link]++
st.s[[Link]] = nil top = 2

Else
stack sudah penuh
Endif

Stack s
Push()
int Push(int nil)
If jawaban ==0 then
[Link]++

st.s[[Link]] = nil top = 2

Else
stack sudah penuh
endif

stack s
Push()
int Push(int nil)
If jawaban ==0 then
top = 3
[Link]++
st.s[[Link]] = nil
Else
stack sudah penuh
Endif

stack s
Push()
int Push(int nil)
If jawaban ==0 then
top = 3
[Link]++
st.s[[Link]] = nil
Else
stack sudah penuh
endif

stack s
Push() top = 5

int Push(int nil)

If jawaban ==0 then
[Link]++
st.s[[Link]] = nil
Else
stack sudah penuh
Endif

stack s
POP(s) o Pop(s) adalah menghapus
elemen dari stack, elemen yang
dihapus adalah elemen terakhir
int pop() masuk (LIFO=Last In First Out)
proses penghapusan dapat
{
dilakukan jika stack tidak dalam
int jawab;
keadaan Kosong
jawab=kosong(); o If jawaban == 0 then
if (jawab== 0)
stack tidak kosong
{
o Dimana setiap melakukan
penghapusan, maka posisi yang
printf("\n Element teratas pada tumpukan adalah \t%d", st.s[[Link]]); paling atas akan berkurang 1
([Link]--)
[Link]--;

}else

printf ("\n Tumpukan [Link] ada item yang dapat di hapus.");

return 0;

}
lanjut
o Untuk mengambil data stack yang terletak paling atas
tampilkan terlebih dahulu nilai elemen teratas stack dengan
mengakses indeksnya sesuai dengan Sp of stacknya, baru
dilakukan di-decrement nilai Tumpukan [sp] sehingga jumlah
elemen stack berkurang.
Pop(s) atas = 5

Int Pop( )

if (jawab== 0)

printf("\n Element teratas pada tumpukan adalah \t%d", st.s[[Link]]);

[Link]--;

}else

printf ("\n Tumpukan [Link] ada item yang dapat di hapus.");

return 0;

stack s
Pop(s)
Int Pop( )
atas = 4
if (jawab== 0)

printf("\n Element teratas pada tumpukan adalah

\t%d", st.s[[Link]]);

[Link]--;

}else

printf ("\n Tumpukan [Link] ada item yang

dapat di hapus.");

return 0;

stack s
Pop(s)
Int Pop( )

if (jawab== 0)

{ atas = 3
printf("\n Element teratas pada tumpukan adalah
\t%d", st.s[[Link]]);

[Link]--;

}else

printf ("\n Tumpukan [Link] ada item yang

dapat di hapus.");

return 0;

stack s
Pop(s)
Int Pop( )

if (jawab== 0)

printf("\n Element teratas pada tumpukan adalah

\t%d", st.s[[Link]]);

[Link]--;

}else

printf ("\n Tumpukan [Link] ada item yang

dapat di hapus."); atas = 0
}

return 0;

stack s
Fungsi IsFull
o Untuk mengetahui stack sudah penuh
o Dengan membaca SP of stack, jika sudah
sama dengan MAKS-1 maka full, jika belum
(masih lebih kecil dari MAKS maka belum full
lanjut
Ilustrasi Stack pada kondisi Full
Max_Stack
9 HARDISK
Top
8 MOUSE
7 SPEAKER
6 MEJA
5 KEYBOARD
4 LAPTOP
3 PRINTER
2 MONITOR
1 VCD
0 TV
Fungsi IsEmpty
o Untuk memeriksa apakah data Stack
masih kosong
o Dengan cara memeriksa SP of stack,
jika masih -1 maka berarti data Stack
masih kosong!
struct Tumpukan {
int data;
Tumpukan *brktnya;
};
Implementasi Stack
top
NUL
dengan
7 8 9
L Single Linked-list

Keuntungannya dibandingkan dg
array adalah alokasi memory yg
dinamis

29
 Contoh STACK LL

CREATE( )
POP( *e )
HEAD NULL HEAD
PUSH( 50 )
P HEAD 30 50 NULL

50 NULL CLEAR( )
PUSH( 30 ) HEAD NULL
P HEAD

30 50 NULL

PUSH( 80 )
P HEAD

80 30 50 NULL

30
Implementasi Stack
(Notasi Polish)

Prefix, infix, postfix

Ungkapan Aritmatika
o Prefix adalah metode penulisan dengan
meletakkan operator di depan operand dan
tanpa menuliskan tanda kurung.
Contoh : +AB, – +ABC, * + AB – CD.
o Infix adalah cara penulisan ungkapan dengan
meletakkan operator di antara dua
operand dalam hal ini pemakaian tanda kurung
sangat menentukan hasil operasi.
Contoh : A+B, A+B-C, (A+B)*(C-D).
o Postfix adalah metode penulisan dengan
menuliskan operator setelah operand dan tanpa
menuliskan tanda kurung.
Contoh : A B +
Notasi infix menjadi postfix
 Contoh :
[Link] A + B + C 2. Infix A+B * C
Prefix Prefix
+AB + C
A+*BC
++ABC
+A*BC
Postfix
AB+ +C Postfix A+ BC*
AB+C+ ABC*+
Derajat Operator Operator Logika :
1. (..) 1. NOT
2. AND
2. ^ 3. OR
3. * dan /
4. + dan -
Infix A*B + C*D
Prefix Postfix
*AB + C * D
AB* + C*D
*AB + *CD
AB* + CD*
+*AB*CD
AB*CD*+
Infix : A + B * (C – D) / E

Prefix Postfix

A + B * -CD / E A + B * CD- / E

A + *B-CD / E A + BCD-* / E

A + /*B-CDE A + BCD-*E/

+A/*B-CDE ABCD-*E/+

Contoh :
1. Infix (A+B)*C^D/E-F+G
2. Infix (A+B*C)*(D+E)/F*G
 Bagaimana jika (2+3)*4 kedalam
Konversi 2+3*4 kedalam POSTFIX
POSTFIX

2+3*4 pada notasi infix identic

dengan 234*+ pada postfix
Contoh infix menjadi postfix
Q = A+B*C

Simbol Prioritas Stack Karakter StringPostfix

(Diambil dari
StringInfix
A 0 ( A
+ 3 (+ A
B 0 (+ AB
* 4 (+* AB
C 0 (+* ABC
) 2 (+ * ABC*
( + ABC*+
( ABC*+