Struktur data pada umumnya berisi 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”
Elemen dapat dihapus dari 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 atau tumpukan adalah suatu struktur
data yang seolah-olah terlihat seperti data yang
tersusun secara ‘menumpuk’, dimana ada data
yang terletak diatas data yang lainnya.
Bersifat LIFO (Last In First Out), berarti data yang
masuk terakhir akan keluar pertama.
Operasi pada Stack :
IsFull : mengecek apakah STACK sudah penuh
IsEmpty : mengecek apakah STACK sudah
kosong
Push : menambah data pada STACK
Pop : mengambil data pada STACK
Clear : digunakan untuk mengosongkan stack
Print : Mencetak stack
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
History pada web browser.
Undo Log pada text editor.
Pemrosesan struktur bersarang (nested)
: loop, rekursi, fungsi, dll.
Algoritma back tracking – Artificial
Intelegence
• Dari gambar disamping kita bisa
mengatakan bahwa kotak B ada
diatas kotak A dan ada dibawah
kotak C.
D • Gambar di samping
menunjukkan bahwa dalam
tumpukan, kita hanya bisa
C menambah atau mengambil
sebuah kotak lewat satu ujung,
B yaitu ujung bagian atas
A
• Gambar dibawah hanya menunjukkan dalam tumpukan hanya
bisa menambah atau mengambil sebuah kotak lewat satu
ujung, yaitu ujung bagian atas
Deklarasi Struktur Data
Maximum
4 Isi [5] Stack = Record
3 Isi : array[1..n] of Tipe
Isi [4]
Data
2 Isi [3] Atas : integer
1 Isi [2] End
0 Isi [1]
Stack S
Definisikan Stack dengan menggunakan
suatu struct
Definisikan konstanta MAX_STACK untuk
menyimpan maksimum isi stack
Elemen struct Stack adalah array data dan
top untuk menadakan posisi data teratas
Buatlah variabel tumpuk sebagai
implementasi dari struct Stack
Deklarasikan operasi-operasi/function di atas
dan buat implemetasinya
Contoh deklarasi MAX_STACK
#define MAX_STACK 10
Contoh deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
int data[10];
};
Deklarasi/buat variabel dari struct
STACK tumpuk;
Inisialisasi Stack
Pada mulanya isi top dengan -1, karena
array dalam bahasa C dimulai dari 0, yang
berarti bahwa data stack adalah KOSONG!
Top adalah suatu variabel penanda
dalam Stack yang menunjukkan elemen
teratas data Stack sekarang.
Top Of Stack akan selalu bergerak
hingga mencapai MAX of STACK yang
menyebabkan stack PENUH!
9 Max_Stack
8
7
6
5
4
3
2
1
0 Top = -1
Ilustrasi Stack pada saat inisialisasi!
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 [Link] = n then stack penuh)
Push( x,s) adalah Memasukkan x kedalam
Stack S
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link]= [Link]+1
[Link][[Link]] = x
Else
stack sudah penuh top = 0
Endif
stack s
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link] = [Link] + 1
[Link][[Link]] = x
top = 1
Else
stack sudah penuh
endif
stack s
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link]= [Link]+1
[Link][[Link]] = k
top = 1
Else
stack sudah penuh
endif
stack s
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link] = [Link] + 1 top = 2
[Link][[Link]] = x
Else
stack sudah penuh
endif
Stack s
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link]= [Link]+1 top = 2
[Link][[Link]] = k
Else
stack sudah penuh
endif
stack s
Procedure Push(x :Tipe
data, s : stack)
top = 3
If [Link]< n then
[Link] = [Link] + 1
[Link][[Link]] = x
Else
stack sudah penuh
endif
stack s
Procedure Push(x :Tipe
data, s : stack)
top = 3
If [Link]< n then
[Link]= [Link]+1
[Link][[Link]] = k
Else
stack sudah penuh
Endif
stack s
top = 5
Procedure Push(x :Tipe
data, s : stack)
If [Link]< n then
[Link]= [Link]+1
[Link][[Link]] = k
Else
stack sudah penuh
Endif
stack s
Pop(s) adalah menghapus elemen dari stack, elemen yang
dihapus adalah elemen terakhir masuk (LIFO=Last In
First Out) proses penghapusan dapat dilakukan jika stack
tidak dalam keadaan Kosong
If [Link] > 0 then stack tidak kosong
Dimana setiap melakukan penghapusan, maka posisi yang
paling atas akan berkurang 1 ([Link] = [Link] -1)
Procedure Pop( s: stack)
If [Link]>0 then
Write [Link][[Link]]
[Link]= [Link] – 1
Else
stack Kosong
endif
Untuk mengambil data stack yang terletak
paling atas (data yang ditunjuk oleh ToS),
tampilkan terlebih dahulu nilai elemen
teratas stack dengan mengakses indeksnya
sesuai dengan top of stacknya, baru
dilakukan di-decrement nilai top of
stacknya sehingga jumlah elemen stack
berkurang.
atas = 5
Procedure Pop( s:
stack)
If [Link]>0 then
Write [Link][[Link]]
[Link]= [Link] – 1
Else
stack kosong
Endif
stack s
Procedure Pop( s: atas = 4
stack)
If [Link]>0 then
Write [Link][[Link]]
[Link]= [Link] – 1
Else
stack kosong
Endif
stack s
Procedure Pop( s:
stack)
atas = 3
If [Link]>0 then
Write [Link][[Link]]
[Link]= [Link] – 1
Else
stack kosong
Endif
stack s
Procedure Pop( s:
stack)
If [Link]>0 then
Write [Link][[Link]]
[Link]= [Link] – 1
Else
stack kosong atas = 0
endif
stack s
Untuk mengetahui stack sudah penuh
Dengan membaca top of stack, jika
sudah sama dengan MAX_STACK-1
maka full, jika belum (masih lebih kecil
dari MAX_STACK maka belum full
Ilustrasi Stack pada kondisi
Full 9 HARDISK Max_Stack
Top
8 MOUSE
7 SPEAKER
6 MEJA
5 KEYBOARD
4 LAPTOP
3 PRINTER
2 MONITOR
1 VCD
0 TV
Untuk memeriksa apakah data Stack
masih kosong
Dengan cara memeriksa top of
stack, jika masih -1 maka berarti
data Stack masih kosong!
Data yang diinputkan selalu menjadi
elemen teratas Stack (yang ditunjuk
oleh To S)
Jika data belum penuh
Tambah satu (increment) nilai top of stack
lebih dahulu setiap kali ada penambahan ke
dalam array data Stack.
Isikan data baru ke stack berdasarkan
indeks top of stack yang telah di-increment
sebelumnya.
Jika tidak, outputkan “Penuh”
Untuk menampilkan semua
elemen-elemen data Stack
Dengan cara me-loop semua nilai
array secara terbalik, karena kita
harus mengakses dari indeks
array tertinggi terlebih dahulu
baru ke indeks yang lebih kecil!
Digunakan untuk melihat top of stack