LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Implement Queue Using Stacks

Pakai dua stack untuk menjaga urutan queue dan bikin setiap operasi berjalan dalam amortized constant time.

Di artikel ini 4 bagian

Implementasi queue pakai dua stack bisa jalan karena memindahkan semua item ke stack kedua bakal membalik urutannya. Satu stack menerima item baru, dan stack satunya lagi menyodorkan item yang paling lama saat ada yang perlu dibaca.

Kontrak queue

Queue ini perlu empat operasi:

  • push(x): Menambahkan elemen ke ujung belakang
  • pop(): Menghapus elemen dari depan
  • peek(): Melihat elemen terdepan tanpa menghapusnya
  • empty(): Mengecek apakah queue kosong

Implementasinya cuma boleh memakai operasi stack: push, pop, peek, dan pengecekan kosong.

Memindahkan semua item dari satu stack ke stack lain menaruh item terlama di atas. Aku pakai inbox untuk item baru dan outbox untuk item yang menunggu dikeluarkan.

Aturan pemindahan dan implementasinya

Inbox menerima setiap item baru. pop atau peek mengecek outbox dulu. Kalau outbox kosong, implementasinya memindahkan semua item inbox ke sana. Bagian depan queue lalu ada di puncak outbox.

javascript
class MyQueue {
  constructor() {
    this.inbox = []; // Stack for incoming elements
    this.outbox = []; // Stack for outgoing elements
  }

  push(x) {
    // Just push to inbox - simple!
    this.inbox.push(x);
  }

  pop() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Pop from outbox (this is the front of the queue)
    return this.outbox.pop();
  }

  peek() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Look at top of outbox without removing
    return this.outbox[this.outbox.length - 1];
  }

  empty() {
    // Queue is empty if both stacks are empty
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  // Helper: transfer inbox to outbox when outbox is empty
  moveInboxToOutbox() {
    if (this.outbox.length === 0) {
      // Transfer all elements from inbox to outbox
      // This reverses the order, so first-in becomes first-out!
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
  }
}

Perubahan state dan amortized cost

Untuk urutan di bawah ini, stack-stack-nya berubah seperti ini:

  1. push(1): inbox = [1], outbox = []
  2. push(2): inbox = [1, 2], outbox = []
  3. push(3): inbox = [1, 2, 3], outbox = []
  4. pop(): Pindahkan inbox ke outbox → outbox = [3, 2, 1], inbox = []
    • Pop dari outbox → mengembalikan 1 (benar! first in, first out)
  5. push(4): inbox = [4], outbox = [3, 2]
  6. pop(): outbox nggak kosong, jadi pop → mengembalikan 2 (benar!)

Pemindahan cuma terjadi saat outbox kosong. push itu O(1). Satu kali pop bisa memindahkan O(n) item. Tapi implementasi ini memindahkan setiap item dari inbox ke outbox paling banyak sekali sebelum item itu dihapus. Jadi, pop dan peek masing-masing punya amortized cost O(1). Kedua stack totalnya memakai space O(n).

Kenapa lazy transfer ini bisa jalan

Item di outbox lebih lama daripada semua item di inbox. Memindahkan item baru ke atasnya bakal merusak urutan queue, jadi outbox harus kosong sebelum pemindahan berikutnya.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan