Question

Pada sebuah aplikasi pengolah dokumen, biasanya terdapat fasilitas untuk melakukan Undo dan Redo. Operasi Undo akan membatalkan langkah/ tindakan terakhir yang kita lakukan saat mengedit dokumen (misal, jika kita menyadari ada kesalahan pada langkah terakhir kita), sedangkan Redo digunakan untuk mengulang kembali operasi yang baru saja dibatalkan dengan sebuah Undo. Proses Undo dan Redo ini dapat dilakukan sampai dengan operasi pertama setelah sebuah dokumen dibuka/disimpan. Misalnya, terjadi rangkaian kejadian berikut:
a. Budi membuka dokumen A
b. Budi menambahkan judul pada dokumen A
c. Budi menulis sebuah paragraf pada dokumen A
d. Budi menambahkan sebuah tabel pada dokumen A
e. Budi menyisipkan sebuah gambar pada dokumen A
Apabila kemudian Budi menekan tombol Undo, operasi terakhir (yaitu penambahan gambar) akan dibatalkan sehingga gambar tersebut akan hilang dari dokumen. Jika kemudian Budi menekan tombol Undo sekali lagi, operasi terakhir sebelum itu (yaitu menambahkan tabel) juga akan dibatalkan sehingga tabel tersebut akan hilang dari dokumen. Jika kemudian Budi menekan tombol Redo, operasi Undo yang terakhir (yaitu yang menghilangkan tabel) akan dibatalkan sehingga tabel tersebut akan muncul kembali. Jelas bahwa aplikasi perlu untuk menyimpan data-data berupa tindakan/ operasi apa saja yang dilakukan oleh penggunanya dari awal sampai akhir, serta efeknya terhadap dokumen agar dapat memberikan fungsionalitas Undo dan Redo tersebut.

Manakah di antara stack dan queue yang lebih tepat digunakan untuk menyimpan operasi-operasi tersebut? BERIKAN ALASAN!​

Answer 1

Di antara stack dan queue, struktur data yang lebih tepat digunakan untuk menyimpan operasi-operasi pengolahan dokumen terkait dengan fitur Undo dan Redo, adalah STACK.

Secara singkat, alasannya adalah karena data (dalam hal ini langkah / tindakan) yang diproses oleh kedua operasi tersebut (undo dan redo) sama-sama merupakan data (langkah / tindakan) terakhir pada himpunan data masing-masing, sehingga prinsip dasar yang tepat digunakan adalah LIFO (Last In First Out), artinya elemen yang terakhir masuk adalah elemen yang pertama dikeluarkan atau diproses.
 

Pembahasan

Deskripsi persoalan pada pertanyaan di atas sudah sangat jelas mengulas fitur Undo dan Redo yang terdapat pada aplikasi pengolah dokumen.

• Operasi Undo akan membatalkan langkah/ tindakan terakhir yang pengguna lakukan.
• Operasi Redo digunakan untuk mengulang kembali operasi yang baru saja dibatalkan dengan sebuah Undo.

Konsekuensinya:

• Jika pengguna sudah melakukan beberapa kali operasi Undo, maka redo mengulang kembali langkah / tindakan terakhir yang di-undo.
• Sebaliknya, jika pengguna sudah melakukan beberapa kali operasi Redo, maka undo membatalkan langkah / tindakan terakhir yang di-redo.
• Operasi Undo hanya bisa dilakukan atau memiliki efek terhadap dokumen jika sudah ada langkah / tindakan yang dilakukan oleh pengguna, atau sudah ada langkah / tindakan yang di-redo oleh pengguna.
• Operasi Redo hanya bisa dilakukan atau memiliki efek terhadap dokumen jika sudah ada langkah / tindakan yang di-undo oleh pengguna.

Jadi, untuk kedua operasi tersebut, data (langkah / tindakan) yang diproses adalah data terakhir yang masuk ke dalam himpunan data masing-masing.

Berdasarkan hal tersebut, struktur data yang tepat digunakan adalah stack (tumpukan).

Agar lebih jelas, kita telusuri saja sesuai persoalan yang diulas pada pertanyaan. Untuk fitur Undo-Redo, aplikasi memerlukan setidaknya 2 himpunan data, yang dalam hal ini bertipe data stack. Jadi, terdapat stack Undo dan stack Redo. Setiap langkah yang dilakukan oleh Budi langsung dimasukkan (di-push) ke dalam stack Undo.

Penelusuran berikut ini hanya bersifat mendasar saja. Implementasi sesungguhnya pada aplikasi bersifat lebih kompleks, karena harus ada struktur data lain yang menyimpan "konten" dari setiap langkah / tindakan yang dilakukan pengguna.

5 langkah awal yang dilakukan Budi adalah:

1. Budi membuka dokumen A
2. Budi menambahkan judul pada dokumen A
3. Budi menulis sebuah paragraf pada dokumen A
4. Budi menambahkan sebuah tabel pada dokumen A
5. Budi menyisipkan sebuah gambar pada dokumen A

(nomor urut langkah dapat dianggap sebagai ID dari langkah)

Yang dilakukan oleh aplikasi pada stack Undo sesuai urutan langkah di atas adalah:

• push(UNDO, 1)
• push(UNDO, 2)
• push(UNDO, 3)
• push(UNDO, 4)
• push(UNDO, 5)

Kondisi stack saat ini:

Kemudian, Budi menekan tombol Undo.

Aplikasi akan membatalkan langkah 5, yaitu penyisipan sebuah gambar, dan meng-update stack Undo dan Redo.

• push(REDO, UNDO.top)
  ⇒ memasukkan elemen teratas (top) dari stack UNDO ke dalam stack REDO
• pop(UNDO)
  ⇒ mengeluarkan elemen teratas (top) dari stack UNDO.

Kondisi stack saat ini:

Lalu, Budi menekan tombol Undo lagi.

Aplikasi akan membatalkan langkah 4, yaitu penambahan sebuah tabel, dan meng-update stack Undo dan Redo.

• push(REDO, UNDO.top)
• pop(UNDO)

Kondisi stack saat ini:

Setelah itu, Budi menekan tombol Redo.

Aplikasi akan mengulangi langkah 4 dengan mengambil kembali "konten" dari langkah 4, yaitu tabel yang tadi sudah ditambahkan (yang sudah tersimpan di memori dengan struktur data tertentu), dan meng-update stack Undo dan Redo.

• push(UNDO, REDO.top)
  ⇒ memasukkan elemen teratas (top) dari stack REDO0 ke dalam stack UNDO
• pop(REDO)

Kondisi stack saat ini:

Dan seterusnya.