Stack dan Queue
Stack adalah struktur data yang mengikuti prinsip Last-In-First-Out atau LIFO, mirip seperti tumpukan piring di mana piring terakhir yang ditaruh adalah yang pertama diambil. Bayangkan Anda memasukkan buku ke dalam kotak vertikal, buku terakhir yang masuk akan berada di atas dan diambil pertama kali.
Queue mengikuti prinsip First-In-First-Out atau FIFO, seperti antrian di kasir supermarket. Orang yang datang pertama akan dilayani pertama. Dalam programming, queue sering digunakan untuk task scheduling, breadth-first search, dan buffering.
Kompleksitas Operasi
Untuk stack, operasi push (menambah elemen) dan pop (mengambil elemen) keduanya memiliki kompleksitas O(1) karena kita selalu beroperasi di ujung yang sama. Peek (melihat elemen teratas tanpa menghapus) juga O(1). Sama halnya dengan queue, enqueue (menambah di belakang) dan dequeue (mengambil dari depan) adalah O(1) jika diimplementasikan dengan benar menggunakan linked list atau circular array.
Contoh Implementasi Stack
package main
import (
"errors"
"fmt"
)
// Stack menggunakan slice sebagai underlying storage
type Stack struct {
items []int
}
// Push menambahkan elemen ke top stack
// Kompleksitas Waktu: O(1) amortized - slice di Go otomatis expand
// Kompleksitas Ruang: O(1) per operasi
func (s *Stack) Push(value int) {
s.items = append(s.items, value)
}
// Pop menghapus dan mengembalikan elemen dari top
// Kompleksitas Waktu: O(1)
// Kompleksitas Ruang: O(1)
func (s *Stack) Pop() (int, error) {
if s.IsEmpty() {
return 0, errors.New("stack is empty")
}
// Ambil elemen terakhir
index := len(s.items) - 1
value := s.items[index]
// Hapus elemen terakhir dengan slicing
s.items = s.items[:index]
return value, nil
}
// Peek melihat elemen top tanpa menghapus
// Kompleksitas Waktu: O(1)
// Kompleksitas Ruang: O(1)
func (s *Stack) Peek() (int, error) {
if s.IsEmpty() {
return 0, errors.New("stack is empty")
}
return s.items[len(s.items)-1], nil
}
// IsEmpty mengecek apakah stack kosong
func (s *Stack) IsEmpty() bool {
return len(s.items) == 0
}
// Size mengembalikan jumlah elemen
func (s *Stack) Size() int {
return len(s.items)
}Studi Kasus: Valid Parentheses
Problem ini sangat umum dan mendemonstrasikan penggunaan stack yang sempurna. Bayangkan Anda sedang memeriksa kode programming untuk memastikan setiap kurung buka memiliki pasangan kurung tutup yang sesuai.
// IsValidParentheses memeriksa apakah tanda kurung seimbang
// Kompleksitas Waktu: O(n) - satu pass melalui string
// Kompleksitas Ruang: O(n) - dalam kasus terburuk semua karakter adalah '('
func IsValidParentheses(s string) bool {
// Map untuk pasangan kurung yang valid
pairs := map[rune]rune{
')': '(',
'}': '{',
']': '[',
}
stack := &Stack{}
// Iterate melalui setiap karakter
for _, char := range s {
// Jika karakter adalah kurung tutup
if opening, isClosing := pairs[char]; isClosing {
// Cek apakah stack kosong atau top tidak match
if stack.IsEmpty() {
return false
}
top, _ := stack.Pop()
// Convert int back to rune untuk comparison
if rune(top) != opening {
return false
}
} else {
// Karakter adalah kurung buka, push ke stack
stack.Push(int(char))
}
}
// Valid hanya jika semua kurung sudah berpasangan (stack kosong)
return stack.IsEmpty()
}Contoh Implementasi Queue
// Queue menggunakan slice dengan front dan rear pointers
type Queue struct {
items []int
}
// Enqueue menambahkan elemen ke belakang queue
// Kompleksitas Waktu: O(1) amortized
// Kompleksitas Ruang: O(1) per operasi
func (q *Queue) Enqueue(value int) {
q.items = append(q.items, value)
}
// Dequeue menghapus dan mengembalikan elemen dari depan
// Kompleksitas Waktu: O(n) karena slicing - bisa dioptimasi dengan circular buffer
// Kompleksitas Ruang: O(1)
func (q *Queue) Dequeue() (int, error) {
if q.IsEmpty() {
return 0, errors.New("queue is empty")
}
value := q.items[0]
q.items = q.items[1:]
return value, nil
}
// Front melihat elemen depan tanpa menghapus
func (q *Queue) Front() (int, error) {
if q.IsEmpty() {
return 0, errors.New("queue is empty")
}
return q.items[0], nil
}
// IsEmpty mengecek apakah queue kosong
func (q *Queue) IsEmpty() bool {
return len(q.items) == 0
}
// Size mengembalikan jumlah elemen
func (q *Queue) Size() int {
return len(q.items)
}Studi Kasus: Implement Queue using Stacks
Ini adalah problem interview klasik yang menguji pemahaman Anda tentang kedua struktur data. Idenya adalah menggunakan dua stack untuk mensimulasikan behavior queue.
// QueueUsingStacks mengimplementasikan queue menggunakan dua stack
type QueueUsingStacks struct {
stackIn *Stack // Stack untuk operasi enqueue
stackOut *Stack // Stack untuk operasi dequeue
}
// NewQueueUsingStacks membuat queue baru
func NewQueueUsingStacks() *QueueUsingStacks {
return &QueueUsingStacks{
stackIn: &Stack{},
stackOut: &Stack{},
}
}
// Enqueue menambahkan elemen
// Kompleksitas Waktu: O(1)
// Kompleksitas Ruang: O(1)
func (q *QueueUsingStacks) Enqueue(value int) {
// Selalu push ke stackIn
q.stackIn.Push(value)
}
// Dequeue menghapus elemen dari depan
// Kompleksitas Waktu: O(1) amortized, O(n) worst case
// Kompleksitas Ruang: O(1)
func (q *QueueUsingStacks) Dequeue() (int, error) {
// Jika stackOut kosong, transfer semua elemen dari stackIn
// Ini membalik urutan sehingga elemen pertama ada di top
if q.stackOut.IsEmpty() {
for !q.stackIn.IsEmpty() {
val, _ := q.stackIn.Pop()
q.stackOut.Push(val)
}
}
// Jika masih kosong, queue memang kosong
if q.stackOut.IsEmpty() {
return 0, errors.New("queue is empty")
}
return q.stackOut.Pop()
}
func main() {
// Test Stack dengan Valid Parentheses
fmt.Println("Valid Parentheses Tests:")
fmt.Printf("'()[]{}': %v\n", IsValidParentheses("()[]{}")) // true
fmt.Printf("'([)]': %v\n", IsValidParentheses("([)]")) // false
fmt.Printf("'{[()]}': %v\n", IsValidParentheses("{[()]}")) // true
// Test Queue
q := &Queue{}
q.Enqueue(1)
q.Enqueue(2)
q.Enqueue(3)
fmt.Println("\nQueue Operations:")
val, _ := q.Dequeue()
fmt.Printf("Dequeued: %d\n", val) // 1
// Test Queue using Stacks
qStack := NewQueueUsingStacks()
qStack.Enqueue(1)
qStack.Enqueue(2)
qStack.Enqueue(3)
fmt.Println("\nQueue using Stacks:")
val, _ = qStack.Dequeue()
fmt.Printf("Dequeued: %d\n", val) // 1
}Penjelasan Kompleksitas Queue using Stacks
Meskipun operasi dequeue bisa memerlukan O(n) dalam satu pemanggilan (ketika harus transfer semua elemen), kompleksitas amortized tetap O(1). Ini karena setiap elemen hanya dipindahkan dari stackIn ke stackOut sekali saja. Jika Anda melakukan n operasi enqueue diikuti n operasi dequeue, total work adalah 3n operasi (n push ke stackIn, n transfer ke stackOut, n pop dari stackOut), yang memberikan average O(1) per operasi.
Last updated