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.