Code demo chức năng Undo/Redo áp dụng Stack

Lời mở đầu

Một câu hỏi mà tôi rất hay hỏi khi phỏng vấn các bạn sinh viên ứng tuyển fresher và rất nhiều bạn không hiểu hoặc biết "sơ qua" đó là:

"Bạn có biết cấu trúc dữ liệu Stack có thể được áp dụng để giải quyết những bài toán gì trong thực tế không?"

Thỉnh thoảng tôi gặp các trường hợp khá tệ không hiểu bản chất, nhầm lẫn giữa Stack và Queue, trả lời Stack nhưng nội dung lại nói về Queue

Còn đa số các bạn nắm được khái niệm, nguyên lý hoạt động, nhưng lại chưa rõ ứng dụng cụ thể của nó sẽ như thế nào, chỉ biết trên trường các thầy dạy push, pop, top, ...

Đây là lỗ hổng cực kỳ phổ biến. Dù Stack là một trong những cấu trúc dữ liệu cơ bản và dễ học nhất, nhiều bạn có lẽ chỉ học để thi qua môn CTDL&GT (Cấu trúc dữ liệu và Giải ... trí), chứ không biết rằng sau này đi làm sẽ phải thường xuyên gặp nó

Vì thế, trong bài viết này tôi sẽ:

• Giúp bạn hiểu rõ Stack là gì một cách dễ hình dung
• Code demo chương trình C++ mô phỏng 2 chức năng rất phổ biến mà mọi người thường xuyên sử dụng đó là: Undo & Redo

1. Cấu trúc dữ liệu Stack là gì?

• Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên lý Vào Sau Ra Trước - Last In First Out (LIFO)

• Giống như việc xếp chồng sách lên nhau. Quyển sách nào được xếp vào sau cùng (push), thì sẽ được lấy ra đầu tiên (pop)

  

• Các thao tác chính:

  • push(x): Đưa phần tử x vào đỉnh Stack
  • pop(): Lấy phần tử ở đỉnh ra khỏi Stack
  • top(): Chỉ xem giá trị phần tử ở đỉnh Stack chứ không lấy ra
  • size(): Trả về số phần tử hiện có trong Stack
  • empty(): Kiểm tra Stack có rỗng hay không. Trả về true nếu Stack rỗng, trả về false nếu Stack có ít nhất 1 phần tử

2. Áp dụng Stack để làm chức năng Undo & Redo

Trong các phần mềm như Word, Excel, Photoshop, ... các bạn có thể thực hiện Undo (quay lại hành động trước đó) hoặc Redo (phục hồi thao tác vừa Undo)

Để thực hiện 2 chức năng này, chúng ta có thể sử dụng kết hợp 2 stack đó là:

1. undoStack: lưu các hành động đã thực hiện

2. redoStack: lưu các hành động vừa Undo

   

Khi người dùng thực hiện thao tác:

• ⌨️ Gõ chữ => Ta sẽ lưu string cũ vào undoStack, xóa redoStack
• 🔙 Nhấn chức năng Undo => Ta sẽ lấy string trên đỉnh undoStack đưa vào redoStack
• 🔁 Nhấn chức năng Redo => Ta sẽ lấy string trên đỉnh redoStack đưa lại undoStack

Những trường hợp ngoại lệ như undoStack rỗng, redoStack rỗng, tôi sẽ thể hiện cụ thể trong code demo bên dưới.

3. Code demo (Có comment giải thích trong code)

/* * Code mo phong chuc nang Undo/Redo * Author: Tran Minh Sang */ #include <iostream>
#include <stack>
#include <string>
using namespace std; int main() { stack<string> undoStack; stack<string> redoStack; string currentText = ""; int command; cout << "Chuong trinh mo phong chuc nang Undo/Redo\n"; cout << "Cac lenh ho tro:\n"; cout << "1. Go them noi dung\n"; cout << "2. Undo\n"; cout << "3. Redo\n"; cout << "4. Thoat"; while (true) { cout << "\n\n> Chon lenh muon thuc hien (1-4): "; cin >> command; switch (command) { case 1: { cout << "Nhap noi dung muon them: "; string newText; fflush(stdin); getline(cin, newText); // Luu string hien tai vao undoStack truoc khi thay doi undoStack.push(currentText); currentText = newText; // Xoa redoStack vi da co thay doi moi while (!redoStack.empty()) { redoStack.pop(); } cout << "Da them noi dung \"" << newText << "\" thanh cong!\n"; cout << "Noi dung van ban hien tai la: " << "\"" << currentText << "\""; break; } case 2: { if (!undoStack.empty()) { // Luu string hien tai vao redoStack truoc khi quay lai redoStack.push(currentText); currentText = undoStack.top(); undoStack.pop(); cout << "Da thuc hien Undo!\n"; cout << "Noi dung van ban hien tai la: " << "\"" << currentText << "\""; } else { cout << "Khong the Undo!"; } break; } case 3: { if (!redoStack.empty()) { // Luu string hien tai vao undoStack truoc khi phuc hoi undoStack.push(currentText); currentText = redoStack.top(); redoStack.pop(); cout << "Da thuc hien Redo!\n"; cout << "Noi dung van ban hien tai la: " << "\"" << currentText << "\""; } else { cout << "Khong the Redo!"; } break; } case 4: { // Thoat chuong trinh return 0; } default: { cout << "Lenh khong hop le. Vui long chon cac lenh tu 1 den 4!"; break; } } } return 0;
}

4. Kết quả khi chạy chương trình

Chuong trinh mo phong chuc nang Undo/Redo
Cac lenh ho tro:
1. Go them noi dung
2. Undo
3. Redo
4. Thoat > Chon lenh muon thuc hien (1-4): 1
Nhap noi dung muon them: abc
Da them noi dung "abc" thanh cong!
Noi dung van ban hien tai la: "abc" > Chon lenh muon thuc hien (1-4): 2
Da thuc hien Undo!
Noi dung van ban hien tai la: "" > Chon lenh muon thuc hien (1-4): 3
Da thuc hien Redo!
Noi dung van ban hien tai la: "abc" > Chon lenh muon thuc hien (1-4): 2
Da thuc hien Undo!
Noi dung van ban hien tai la: "" > Chon lenh muon thuc hien (1-4): 1
Nhap noi dung muon them: xyz
Da them noi dung "xyz" thanh cong!
Noi dung van ban hien tai la: "xyz" > Chon lenh muon thuc hien (1-4): 3
Khong the Redo! > Chon lenh muon thuc hien (1-4): 2
Da thuc hien Undo!
Noi dung van ban hien tai la: "" > Chon lenh muon thuc hien (1-4): 2
Khong the Undo! > Chon lenh muon thuc hien (1-4): 4 --------------------------------
Process exited after 36.67 seconds with return value 0
Press any key to continue . . .

5. Một số ví dụ khác về ứng dụng của Stack

• Một ví dụ khác mà trong thực tế anh em lập trình viên rất thường xuyên sử dụng Stack, đó là trong quá trình debug. Chúng ta thường sẽ quan sát cửa sổ CallStack để xem các hàm gọi đến nhau như thế nào. Những hàm nằm trên cùng của CallStack sẽ là những hàm trả ra kết quả đầu tiên.

  

• Khi chương trình gặp exception, bạn có thể đọc stack trace để truy ngược lại vị trí gây ra exception.

• Hoặc như khi code hàm đệ quy, mỗi lời gọi hàm sẽ đẩy trạng thái hiện tại vào call stack. Sau khi thực hiện xong thì kết quả của các lần gọi hàm sẽ được trả ngược về theo thứ tự LIFO. Đệ quy hoạt động được chính là nhờ Stack lưu trạng thái các lần gọi hàm.

  

Trên đây là bài viết về cấu trúc dữ liệu Stack, ứng dụng thực tế của nó và code demo chức năng Undo/Redo.

Hi vọng bài viết của tôi đã giúp các bạn giải đáp được những thắc mắc của bản thân và hiểu hơn về Stack.

Hẹn gặp lại các bạn ở các bài viết tiếp theo 👋

🙋🏻‍♂️ Một số kênh mạng xã hội khác mà tôi dùng để chia sẻ và trao đổi với anh em kiến thức về ngành CNTT và lập trình:

• Group "Khi nào giỏi lập trình thì đổi tên 🫢": https://www.facebook.com/groups/gioilaptrinhthidoiten

• Page "CLB Lập trình - THPT Ngọc Tảo": https://www.facebook.com/clb.it.ngoctao/

• TikTok "CLB Lập trình - THPT Ngọc Tảo": https://www.tiktok.com/@clb.it.ngoctao/

• Youtube "Tờ Mờ Sáng học Lập trình": https://www.youtube.com/@tmsanghoclaptrinh/