Solusi Leetcode - Implement Queue Using Stacks

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

Saya perlu mengimplementasikan queue dengan operasi-operasi ini:

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

Tapi saya cuma boleh pakai operasi stack: push, pop, peek, dan mengecek apakah kosong.

Awalnya saya bingung karena stack cuma memperlihatkan item paling atasnya. Memindahkan semua item dari stack inbox ke stack outbox bakal membalik urutannya, jadi item queue yang paling lama ada di paling atas. Pemindahan kedua nanti mengembalikan hubungan yang sama untuk item-item yang tersisa.

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.

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

Implementasi ini menunjukkan gimana satu struktur data bisa mensimulasikan struktur data lain kalau operasinya diatur ulang. Detail pentingnya adalah menunda pemindahan sampai outbox kosong, bukan memindahkan item di setiap operasi queue.

Dua stack mensimulasikan urutan FIFO dengan memisahkan write dari read. Inbox menjaga urutan masuk, sementara outbox membaliknya untuk penghapusan, dan lazy transfer menjaga amortized cost per operasi tetap konstan.