Stack và Queue trong C++

I. Stack trong C++

1. Mở đầu về Stack

Hãy thử tưởng tượng bạn được sếp thưởng một chuyến du lịch cùng gia đình, bạn đang bận rộn với việc xếp quần áo vào vali. Khi đến địa điểm du lịch, bạn mở vali ra, đương nhiên bạn sẽ thấy chiếc quần/áo cuối cùng bạn xếp vào sẽ nằm ở trên cùng. Như vậy bạn sẽ cần lên kế hoạch tỉ mỉ cho thứ tự các trang phục bạn mặc trong khoảng thời gian du lịch trước khi bạn xếp chúng vào vali (Đương nhiên mình không tính đến việc bạn cố tình cho tay xuống dưới cùng và vẫn lấy được bộ quần áo ưu thích!).

Việc xếp quần áo như trên chính là một ví dụ cho container Stack trong C++: đồ bạn xếp vào cuối cùng sẽ được lấy ra đầu tiên, ngược lại, đồ xếp đầu tiên sẽ được lấy ra sau cùng.

2. Sử dụng container Stack

Stack là một dạng cấu trúc dữ liệu được tạo ra nhằm hoạt động theo nguyên lí “vào sau ra trước” – LIFO (Last – In first – Out). Việc bổ sung cũng như loại bỏ các phần tử sẽ thực hiện ở cuối danh sách.

Để sử dụng container stack bạn cần khai báo:

#include<stack>

Để khai báo một biến kiểu stack, ta có công thức chung sau:

stack<kiểu dữ liệu> tên biến;

VD:

set<int> a;
set<char> b;
set<float> c;

3.Các phép toán cơ bản của stack

• Thêm một phần tử vào stack:

st.push(a); // thêm phần tử a vào stack st

• Loại bỏ phần tử ở đỉnh của stack:

st.pop();

• Lấy giá trị của phẩn tử ở đỉnh của stack:

st.top();

• Trả về kích thước của stack:

st.size();

• Kiểm tra stack rỗng hoặc không:

st.empty(); // true nếu stack rỗng, flase nếu không rỗng

• Lưu ý: các hàm trên đều có độ phức tạp thời gian là $O(1)$, và 1 biến stack có độ phức tạp không gian là $O(N)$ với $N$ là số phần tử được đưa vào stack.

4. Ứng dụng của stack

Do stack hoạt động theo nguyên tắc LIFO nên ta thường ứng dụng nó trong:

• Các bài toán liên quan đến việc đảo ngược, chuyển đổi cách biểu diễn.
• Sử dụng biến stack để lưu trữ tạm các dữ liệu, thực hiện biểu thức toán.
• Thực thi phương thức, chương trình con.
• Phân tích cú pháp của mã nguồn.

II. Queue trong C++

1. Mở đầu về Queue

Bên cạnh stack, chúng ta cũng có một kiểu dữ liệu khá tương tự đó là queue. Lúc này bạn đang là chủ một cửa hàng đồ ăn sáng rất đông khách. Để giữ trật tự cũng như có thể phục vụ đồ ăn sáng cho khách hiệu quả, bạn sẽ có một danh sách thứ tự các khách hàng đặt đồ, và cuối cùng bạn sẽ phục vụ theo thứ tự từ trên xuống dưới (tương ứng với khách hàng đặt sớm nhất và muộn nhất).

Đây là một ví dụ điển hình cho kiểu dữ liệu queue, phần tử vào trước sẽ ra trước. (nếu phục vụ khách hàng giống như kiểu stack thì chắc quán ăn đóng cửa sớm!)

2. Sử dụng container Queue

Queue là một dạng cấu trúc dữ liệu được tạo ra nhằm hoạt động theo nguyên lí “vào trước ra trước” – FIFO (First – In first – Out). Khác với stack, trong queue việc bổ sung được thực hiện ở cuối danh sách và việc loại bỏ các phần tử sẽ thực hiện ở đầu danh sách.

Để sử dụng container queue bạn cần khai báo:

#include<queue>

Để khai báo một biến kiểu stack, ta có công thức chung sau:

queue<kiểu dữ liệu> tên biến;

VD:

queue<int> a;
queue<char> b;
queue<float> q;

3.Các phép toán cơ bản của queue

• Thêm một phần tử vào queue:

q.push(a); // thêm phần tử a vào queue q

• Loại bỏ phần tử ở đầu của queue:

q.pop();

• Lấy giá trị của phẩn tử ở đầu của queue:

q.front();

• Lấy giá trị của phẩn tử ở cuối của queue:

q.back();

• Trả về kích thước của queue:

q.size();

• Kiểm tra queue rỗng hoặc không:

q.empty(); // true nếu queue rỗng, flase nếu không rỗng

• Lưu ý: các hàm trên đều có độ phức tạp thời gian là $O(1)$, và 1 biến queue có độ phức tạp không gian là $O(N)$ với $N$ là số phần tử được đưa vào queue.

4. Ứng dụng của queue

Do queue hoạt động theo nguyên tắc FIFO nên ta thường ứng dụng nó trong:

• Các bài toán liên quan đến việc đảo chuỗi tuần hoàn, chuyển đổi cách biểu diễn.
• Sử dụng biến queue để lưu trữ tạm các dữ liệu, thực hiện biểu thức toán.
• Lập trình CPU, phân phối thời gian xử lí của CPU.
• Ứng dụng trong việc in ấn.

III. Phân biệt giữa Stack và Queue

• Trong thao tác thêm và xóa các phần tử, Stack hoạt động theo cơ chế LIFO, trong khi Queue hoạt động theo cơ chế FIFO.
• Trong Stack, tại vị trí kết thúc được sử dụng để chèn và xóa các phần tử. Ngược lại, trong Queue, hai vị trí cuối cùng và đầu tiên được sử dụng để chèn và xóa các phần tử.
• Vì Stack chỉ có một kết thúc mở, đó là lý do chỉ sử dụng một con trỏ để chỉ đến đỉnh của Stack. Nhưng Queue sử dụng hai con trỏ để chỉ phía trước và phía sau.
• Stack thực hiện hai thao tác được gọi là đẩy và bật. Với Queue, các thao tác đó được gọi là enqueue và dequeue.
• Thao tác trong Stack dễ dàng hơn trong Queue.
• Hoàn cảnh sử dụng của hai thuật toán là khác nhau.
• Queue có các biến thể như hàng đợi tròn, hàng đợi ưu tiên, hàng đợi kết thúc gấp đôi, v.v … Ngược lại, Stack không có các biến thể.

IV. Tài liệu tham khảo

• https://vi.wikipedia.org/wiki/Ng%C4%83n_x%E1%BA%BFp
• https://en.wikipedia.org/wiki/Stack_(C%2B%2B)
• https://vi.wikipedia.org/wiki/H%C3%A0ng_%C4%91%E1%BB%A3i
• https://en.wikipedia.org/wiki/Queue_(abstract_data_type)