Deque

Deque (double-ended queue) melonggarkan satu-satunya batasan antrian, yaitu elemen boleh masuk dan keluar dari dua ujung. Keempat operasinya, push dan pop dari kiri maupun kanan, semuanya berbiaya $O(1)$. Topik ini membangun deque dari nol dengan doubly linked list, kemudian menunjukkan versi bawaan Python dan Java yang siap dipakai, dan diakhiri pratinjau deque monotonik untuk soal jendela maksimum.

Dua ujung yang sama cepatnya#

Stack membatasi operasi pada satu ujung, antrian memisahkan masuk dan keluar ke dua ujung, sedangkan deque mengizinkan keempat kombinasinya. Nama panjangnya double-ended queue, dan pelafalannya lazim sebagai dek, seperti pada dek kartu. Yang penting dari namanya hanyalah kontraknya, yaitu dua ujung yang masing-masing melayani masuk dan keluar dengan biaya konstan.

Kemampuan dua arah menjadikan deque struktur linear paling fleksibel di keluarganya. Dipakai dari satu ujung saja, deque berperilaku sebagai stack. Masuk dari satu ujung dan keluar dari ujung lain mengembalikannya menjadi antrian, sedangkan pemakaian penuh kedua ujung membuka pola seperti jendela geser yang elemennya keluar dari dua sisi. Diagram berikut memperlihatkan keempat arah operasi pada satu baris elemen.

Setiap ujung melayani masuk dan keluar secara mandiri, dan tidak ada operasi yang perlu menyentuh tengah deque. Pada implementasi berantai, masing-masing ujung memiliki penunjuknya sendiri sehingga tidak ada operasi yang saling menunggu.

Implementasi dari nol#

Struktur bahan yang pas adalah doubly linked list, yaitu rantai node yang masing-masing menyimpan rujukan ke tetangga sebelum dan sesudahnya. Dua penunjuk luar bernama kepala dan ekor mengunci kedua ujung rantai. push_kiri menyisipkan node baru sebelum kepala, push_kanan menambahkan sesudah ekor, dan kedua pop melepaskan node dari ujungnya. Semua rujukan yang tersentuh hanya milik node ujung, sehingga keempat operasi tetap $O(1)$ berapa pun panjang deque.

Kasus yang paling mudah salah adalah deque yang baru saja menjadi kosong. Ketika node terakhir dilepas, kepala dan ekor harus sama-sama diatur kembali ke None, bukan hanya salah satunya, agar operasi berikutnya tidak menyimpan rujukan ke node yang sudah dibuang. Kode berikut menangani kedua sisi itu secara eksplisit.

"""Deque dua ujung dari nol: doubly linked list dengan kepala dan ekor."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.prev = None
        self.next = None

class DequeGanda:
    def __init__(self):
        self.kepala = None
        self.ekor = None
        self.jumlah = 0

    def kosong(self):
        return self.jumlah == 0

    def push_kiri(self, nilai):          # sisip di depan, O(1)
        node = Node(nilai)
        node.next = self.kepala
        if self.kepala is not None:
            self.kepala.prev = node
        self.kepala = node
        if self.ekor is None:
            self.ekor = node
        self.jumlah += 1

    def push_kanan(self, nilai):         # sisip di belakang, O(1)
        node = Node(nilai)
        node.prev = self.ekor
        if self.ekor is not None:
            self.ekor.next = node
        self.ekor = node
        if self.kepala is None:
            self.kepala = node
        self.jumlah += 1

    def pop_kiri(self):                  # hapus dari depan, O(1)
        if self.kosong():
            raise IndexError("deque kosong")
        node = self.kepala
        self.kepala = node.next
        if self.kepala is not None:
            self.kepala.prev = None
        else:
            self.ekor = None
        self.jumlah -= 1
        return node.nilai

    def pop_kanan(self):                 # hapus dari belakang, O(1)
        if self.kosong():
            raise IndexError("deque kosong")
        node = self.ekor
        self.ekor = node.prev
        if self.ekor is not None:
            self.ekor.next = None
        else:
            self.kepala = None
        self.jumlah -= 1
        return node.nilai

    def __repr__(self):
        isi = []
        node = self.kepala
        while node is not None:
            isi.append(str(node.nilai))
            node = node.next
        return "deque: [" + ", ".join(isi) + "]"


if __name__ == "__main__":
    d = DequeGanda()
    d.push_kanan(2)
    d.push_kanan(3)
    d.push_kiri(1)
    print(d)
    print("pop_kanan :", d.pop_kanan())
    print("pop_kiri  :", d.pop_kiri())
    d.push_kiri(0)
    d.push_kanan(9)
    print(d)

deque: [1, 2, 3]
pop_kanan : 3
pop_kiri  : 1
deque: [0, 2, 9]

Keluarannya memperlihatkan isi yang tercetak rapi dari kepala ke ekor meskipun elemennya masuk dari dua arah berbeda. Setelah dua pop, nilai 2 tetap tinggal di tengah, lalu 0 dan 9 menyusul dari ujung yang berlawanan. Struktur ini identik dengan yang dilakukan versi bawaan, hanya tanpa penanganan memori tingkat rendah yang sudah diurus Python.

collections.deque pada Python#

Python membungkus deque berbahasa C yang efisien pada modul collections. Konstruktor deque() menyediakan append dan pop untuk ujung kanan, appendleft dan popleft untuk ujung kiri, semuanya $O(1)$. Dibandingkan list, popleft pada deque tidak menggeser apa pun, sehingga pola antrian yang ramai di ujung depan tidak lagi berbiaya $O(n)$. Akses indeks tetap tersedia, tetapi biayanya $O(n)$ karena elemen deque tidak berdampingan di memori.

from collections import deque

d = deque()
d.append(2)          # masuk dari kanan
d.append(3)
d.appendleft(1)      # masuk dari kiri
print("isi      :", d)
print("pop      :", d.pop())        # keluar dari kanan
print("popleft  :", d.popleft())    # keluar dari kiri
print("sisa     :", d)

isi      : deque([1, 2, 3])
pop      : 3
popleft  : 1
sisa     : deque([2])

Keempat metode di atas mencakup hampir seluruh kebutuhan sehari-hari. Untuk kebutuhan khusus, collections.deque juga menyediakan rotate untuk memutar isi dan parameter maxlen yang memangkas elemen lama secara otomatis, berguna untuk riwayat berukuran tetap.

ArrayDeque pada Java#

Sisi Java menyediakan pasangannya dengan nama yang serupa. java.util.ArrayDeque adalah deque berbasis buffer melingkar yang tumbuh otomatis, diakses lewat tipe Deque dengan metode addFirst, addLast, removeFirst, dan removeLast. Dokumentasinya menyatakan kelas ini biasanya lebih cepat daripada java.util.Stack ketika dipakai sebagai stack, dan lebih cepat daripada java.util.LinkedList ketika dipakai sebagai antrian.

import java.util.ArrayDeque;
import java.util.Deque;

public class DemoDeque {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(2);                  // masuk dari kanan
        d.addLast(3);
        d.addFirst(1);                 // masuk dari kiri
        System.out.println("isi    : " + d);
        System.out.println("last   : " + d.removeLast());  // keluar dari kanan
        System.out.println("first  : " + d.removeFirst()); // keluar dari kiri
        System.out.println("sisa   : " + d);
    }
}

isi    : [1, 2, 3]
last   : 3
first  : 1
sisa   : [2]

Keluaran Java dan Python saling meniru karena kedua pustaka menyajikan deque dengan kontrak yang sama, hanya penamaan metodenya berbeda. Perlu diingat bahwa removeFirst dan removeLast melempar exception saat deque kosong, sehingga pemeriksaan isEmpty tetap diperlukan sebelum pop.

Pratinjau deque monotonik#

Aplikasi deque yang paling terkenal pada kompetisi pemrograman adalah menjaga jendela geser tetap teratur. Untuk mencari nilai maksimum pada setiap jendela berukuran $k$, deque menyimpan indeks kandidat yang nilainya menurun dari depan ke belakang. Elemen baru membuang semua kandidat di belakang yang nilainya lebih kecil, karena kandidat itu sudah kalah dan tidak mungkin menjadi maksimum lagi. Kandidat terdepan yang terlewat dari jendela dilepas dari sisi lain.

Kode berikut menunjukkan bentuk akhirnya tanpa membahas pembuktian lengkapnya, karena teknik ini termasuk keluarga stack monotonik. Yang perlu diperhatikan di sini adalah peran kedua ujung, kandidat baru masuk dari belakang, kandidat yang kalah keluar dari belakang, dan kandidat yang keluar dari jendela lewat depan. Tanpa deque dua arah, pola ini sulit ditulis serapi itu.

from collections import deque

def maksimum_jendela(data, k):
    d = deque()               # menyimpan indeks, nilainya menurun
    hasil = []
    for i, x in enumerate(data):
        while d and data[d[-1]] <= x:
            d.pop()           # buang kandidat yang kalah dari x
        d.append(i)
        if d[0] <= i - k:
            d.popleft()       # kandidat terdepan keluar dari jendela
        if i >= k - 1:
            hasil.append(data[d[0]])
    return hasil

print(maksimum_jendela([4, 3, 5, 2, 6, 1], 3))

[5, 5, 6, 6]

Hasilnya empat nilai maksimum untuk empat posisi jendela pada data enam elemen. Setiap indeks masuk dan keluar dari deque paling banyak satu kali, sehingga total pekerjaannya tetap $O(n)$ meskipun ada perulangan while di dalamnya. Alasan mendetailnya dibahas bersama keluarga stack monotonik, dan soal Sliding Window Maximum meminta teknik yang persis sama.

Ringkasan#

• Deque mengizinkan push dan pop di dua ujung, semuanya $O(1)$ pada implementasi doubly linked list maupun buffer melingkar.
• collections.deque dan ArrayDeque adalah versi bawaan yang siap pakai, dengan popleft dan removeFirst yang tidak menggeser elemen.
• Dipakai dengan disiplin tertentu, deque dua ujung menyelesaikan maksimum jendela geser dan menjadi gerbang menuju deque monotonik.

Referensi#

• collections — Container datatypes — Python Software Foundation — dokumentasi deque beserta rotate dan maxlen.
• Double-ended queue — Wikipedia — definisi deque serta variasi implementasinya.
• Algorithms, 4th Edition — Princeton University — materi deque dan antrian Princeton sebagai bahan verifikasi kontrak operasi.