My first Magazine pemrograman-kompetitif-dasar | Page 96

8 Struktur Data Dasar
procedure PUSH (item)
topO f Stack ← topO f Stack + 1
7:
stack[topO f Stack] ← item
8: end procedure
5:
6:
procedure POP ()
topO f Stack ← topO f Stack − 1
11: end procedure
9:
10:
function TOP ()
return stack[topO f Stack]
14: end function
12:
13:
15:
16:
17:
18:
19:
20:
21:
function IS E MPTY ()
if topO f Stack = 0 then
return true
else
return f alse
end if
end function
Saat mengimplementasikan kode di atas, pastikan nilai maxSize sama dengan maksimal
operasi push yang mungkin dilakukan. Dalam pemrograman kompetitif, biasanya banyaknya
operasi push yang mungkin dapat diperkirakan dari soal yang diberikan. Perhatikan juga bahwa
pada operasi pop, kita tidak benar-benar menghapus elemennya, melainkan hanya variabel
penunjuknya yang "dimundurkan".
Contoh Soal 8.2: Pencarian string
Anda diberikan sebuah string, misalnya acaabcbcd. Cari string abc dalam string tersebut.
Jika ditemukan maka hapus string abc tersebut, lalu ulangi pencarian. Pencarian berakhir
ketika tidak terdapat string abc lagi. Anda diminta untuk menentukan total penghapusan
yang berhasil dilakukan.
Contoh
Pada string acaabcbcd terdapat sebuah string abc, dan hapus string tersebut menjadi
acabcd. Lalu, ditemukan lagi string abc dan hapus menjadi acd. Karena tidak ditemukan lagi
string abc, maka jawabannya adalah 2.
Soal tersebut dapat diselesaikan dengan cara berikut:
•
•
•
•
Lakukan iterasi setiap karakter pada string tersebut.
Untuk setiap karakter, push ke dalam stack .
Cek 3 karakter teratas pada stack .
Jika 3 karakter teratas merupakan abc, artinya terdapat 1 penghapusan. Lalu pop ketiga
huruf tersebut dari stack .
Pada soal ini, Anda harus dapat memodifikasi struktur data stack agar Anda dapat melaku-
kan operasi top pada 3 elemen teratas. Kompleksitas total adalah O(N), dengan N merupakan
86