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 belakangpop(): Menghapus elemen dari depanpeek(): Melihat elemen terdepan tanpa menghapusnyaempty(): 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.
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:
- push(1): inbox = [1], outbox = []
- push(2): inbox = [1, 2], outbox = []
- push(3): inbox = [1, 2, 3], outbox = []
- pop(): Pindahkan inbox ke outbox → outbox = [3, 2, 1], inbox = []
- Pop dari outbox → mengembalikan 1 (benar! first in, first out)
- push(4): inbox = [4], outbox = [3, 2]
- 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.

Memuat komentar...