Stack và Queue
Tác giả: Đỗ Trung Hiếu, học viên khóa 2022-2025
Lời tựa
Chào các bạn, mình tên là Đỗ Trung Hiếu, hiện nay là một học sinh lớp 10 ở thành phố Hà Nội. Nhân dịp câu lạc bộ FCT tổ chức cho các thí sinh viết bài chia sẻ kinh nghiệm bản thân, mình muốn viết bài viết này để nói về một số điều hay ho về stack và queue, 2 cấu trúc dữ liệu cơ bản nhưng cũng rất quan trọng trong lập trình thi đấu cũng như được ứng dụng nhiều trong các sản phẩm thực tế.
Stack (ngăn xếp)
Theo cách nói thông thường, ngăn xếp là một đống đồ vật thường được sắp xếp theo lớp – ví dụ: chồng sách trên bàn của bạn hoặc chồng khay trong nhà ăn của trường. Theo cách nói của khoa học máy tính, ngăn xếp là một tập hợp tuần tự các đối tượng với một thuộc tính cụ thể, trong đó, đối tượng cuối cùng được đặt vào ngăn xếp sẽ là đối tượng đầu tiên bị loại bỏ. Thuộc tính này thường được gọi là nhập sau xuất trước hoặc LIFO. Máy bán kẹo, khoai tây chiên và thuốc lá tự động hoạt động theo cùng một nguyên tắc; mục cuối cùng được nạp vào giá sẽ được phân phát trước.
Theo thuật ngữ trừu tượng, ngăn xếp là một danh sách tuyến tính gồm các phần tử trong đó tất cả các phần bổ sung (“push”) và phần xóa (“pop”) danh sách được giới hạn ở một đầu – được định nghĩa là “đỉnh” (của ngăn xếp). ). Các hoạt động cơ bản xác định ngăn xếp là:
- khởi tạo – tạo ngăn xếp.
- đẩy – thêm một mục vào đầu ngăn xếp.
- loại bỏ – loại bỏ mục cuối cùng được thêm vào đầu ngăn xếp.
- lấy đỉnh – nhìn vào mục trên cùng của ngăn xếp mà không lấy nó ra.
- có trống – trả về nếu ngăn xếp không chứa thêm mục nào.
*Độ phức tạp thời gian cho mọi thao tác trên là O(1).
Một ngăn xếp cũng có thể được thực hiện để có dung lượng tối đa. Nếu ngăn xếp đầy và không chứa đủ các vị trí để chấp nhận các đối tượng mới, thì đó được gọi là tràn – do đó có cụm từ “stack overflow”. Tương tự như vậy, nếu một thao tác loại bỏ được thực hiện trên một ngăn xếp trống thì sẽ xảy ra “stack underflow”.
Biết rằng ngăn xếp của chúng ta được xác định bởi thuộc tính LIFO và một số thao tác cơ bản, đặc biệt là thao tác đẩy và bật, chúng ta có thể dễ dàng triển khai ngăn xếp bằng cách sử dụng mảng vì mảng đã cung cấp các thao tác đẩy và bật.
Đây là ngăn xếp đơn giản của chúng ta được viết bằng C++:
‘’’
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> stack;
stack.push(21);
stack.push(22);
stack.push(24);
stack.push(25);
stack.pop();
stack.pop();
while (!stack.empty()) {
cout << stack.top() <<” “;
stack.pop();
}
}
‘’’
Sau đây là một số bài tập cơ bản về Stack bạn có thể tham khảo: https://www.geeksforgeeks.org/stack-data-structure/#standard
Queue (hàng đợi)
Nếu bạn đã từng xếp hàng tại quầy thanh toán ở siêu thị, thì bạn sẽ biết rằng người xếp hàng đầu tiên sẽ được phục vụ trước. Trong thuật ngữ máy tính, hàng đợi là một kiểu dữ liệu trừu tượng khác, hoạt động trên cơ sở vào trước ra trước hoặc FIFO. Hàng tồn kho cũng được quản lý trên cơ sở FIFO, đặc biệt nếu các mặt hàng đó thuộc loại dễ hỏng.
Các hoạt động cơ bản xác định hàng đợi là:
- khởi tạo – tạo hàng đợi.
- đẩy – thêm một mục vào cuối hàng đợi.
- loại bỏ – loại bỏ mục đầu tiên trong hàng đợi.
- lấy đầu – nhìn vào mục đầu tiên trong hàng đợi mà không lấy nó ra
- có trống – trả về nếu hàng đợi không chứa thêm mục nào.
*Độ phức tạp thời gian cho mọi thao tác trên là O(1).
Đây là hàng đợi đơn giản của chúng ta được viết bằng C++:
‘’’
#include <iostream>
#include <queue>
using namespace std;
// Print the queue
void print_queue(queue<int> q)
{
queue<int> temp = q;
while (!temp.empty()) {
cout << temp.front()<<” “;
temp.pop();
}
cout << ‘\n’;
}
// Driver Code
int main()
{
queue<int> q1;
q1.push(1);
q1.push(2);
q1.push(3);
cout << “The first queue is : “;
print_queue(q1);
queue<int> q2;
q2.push(4);
q2.push(5);
q2.push(6);
cout << “The second queue is : “;
print_queue(q2);
q1.swap(q2);
cout << “After swapping, the first queue is : “;
print_queue(q1);
cout << “After swapping the second queue is : “;
print_queue(q2);
cout<<q1.empty(); //returns false since q1 is not empty
return 0;
}
‘’’
Sau đây là một số bài tập cơ bản về Queue: https://www.geeksforgeeks.org/queue-data-structure/#standard
Bonus
1. Deque (hàng đợi hai đầu)
Hàng đợi hai đầu (deque) là cấu trúc dữ liệu chứa 0 hoặc nhiều phần tử có cùng kiểu dữ liệu và được biểu diễn bằng một hàng có phần tử đầu (front) và phần tử cuối (last). Deque hỗ trợ 4 thao tác như sau:
- Thêm một phần tử vào cuối deque. (Push back)
- Thêm một phần tử vào đầu deque. (Push front)
- Bỏ đi phần tử ở cuối deque, trả về giá trị của phần tử đó. (Pop back)
- Bỏ đi phần tử ở đầu deque, trả về giá trị của phần tử đó. (Pop front)
Về ứng dụng, ta sẽ bổ sung thêm một số thao tác sau:
- Xây dưng một deque rỗng. (Construct)
- Sao chép deque này sang một deque khác. (Copy)
- Lấy giá trị của phần tử cuối mà không xóa nó. (Peek back)
- Lấy giá trị của phần tử đầu mà không xóa nó. (Peek front)
- Xóa sạch một deque đang có phần tử. (Empty)
- Tìm số lượng phần tử trong deque. (Find size)
- Kiểm tra xem deque có rỗng hay không. (Test empty)
*Độ phức tạp thời gian cho mọi thao tác trên là O(1).
Hai thao tác lấy giá trị thật sự không cần thiết, bởi lấy giá trị phần tử đầu deque (peek front) tương đương với việc xóa đi phần tử đó (pop front) rồi lại thêm nó vào (push front), và tương tự với lấy giá trị phần tử cuối (peek last). Cũng như kiểm tra rỗng (Test empty) thật ra cũng chỉ là kiểm tra xem số lượng phần tử của deque có bằng 0 hay không.
Bạn có thể hiểu Deque là kết hợp giữa Stack và Queue vậy, nên nó có thể làm bất cứ thứ gì mà Stack và Queue có thể làm. Nếu bạn lười không biết nên sử dụng stack hay queue cho vấn đề của mình thì có thể dùng Deque cho nhanh nhé.
Đây là code C++ cho Deque:
‘’’
// CPP Program to implement Deque in STL
#include <deque>
#include <iostream>
using namespace std;
void showdq(deque<int> g)
{
deque<int>::iterator it;
for (it = g.begin(); it != g.end(); ++it)
cout << ‘\t’ << *it;
cout << ‘\n’;
}
int main()
{
deque<int> gquiz;
gquiz.push_back(10);
gquiz.push_front(20);
gquiz.push_back(30);
gquiz.push_front(15);
cout << “The deque gquiz is : “;
showdq(gquiz);
cout << “\ngquiz.size() : ” << gquiz.size();
cout << “\ngquiz.max_size() : ” << gquiz.max_size();
cout << “\ngquiz.at(2) : ” << gquiz.at(2);
cout << “\ngquiz.front() : ” << gquiz.front();
cout << “\ngquiz.back() : ” << gquiz.back();
cout << “\ngquiz.pop_front() : “;
gquiz.pop_front();
showdq(gquiz);
cout << “\ngquiz.pop_back() : “;
gquiz.pop_back();
showdq(gquiz);
return 0;
}
‘’’
2. Monostack(ngăn xếp đơn điệu)
Đây là ứng dụng khá hay của stack để giảm độ phức tạp thời gian của các thuật toán xuống. Ngăn xếp đơn điệu là ngăn xếp có các phần tử tăng hoặc giảm đơn điệu.
Đôi khi, chúng tôi lưu trữ chỉ mục của các phần tử trong ngăn xếp và đảm bảo rằng các phần tử tương ứng với các chỉ mục đó trong ngăn xếp tạo thành một chuỗi đơn điệu.
Ví dụ một stack đơn điệu giảm.
*Lưu ý:
Đối với ngăn xếp giảm dần:
- Chúng ta cần loại bỏ các phần tử nhỏ hơn phần tử mới trước khi đẩy phần tử mới vào.
- Nó tiếp tục thắt chặt kết quả càng lớn về mặt từ điển càng tốt. (Bởi vì chúng ta tiếp tục loại bỏ các phần tử nhỏ hơn và giữ lại các phần tử lớn hơn).
Tương tự với ngăn xếp tăng dần.
Đây là code ví dụ cho bài tập Largest Rectangle in Histogram. Nếu các bạn không giải được bài này thì tự tìm hiểu nhé vì mình lười viết =)). Còn ở đây mình sẽ có code minh họa sử dụng ngăn xếp đơn điệu. (https://leetcode.com/problems/largest-rectangle-in-histogram/)
‘’’
// OJ: https://leetcode.com/problems/largest-rectangle-in-histogram/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
int largestRectangleArea(vector<int>& A) {
A.push_back(0); // append a zero at the end so that we can pop all elements from the stack and calculate the corresponding areas
int N = A.size(), ans = 0;
stack<int> s; // strictly-increasing mono-stack
for (int i = 0; i < N; ++i) {
while (s.size() && A[i] <= A[s.top()]) { // Take `A[i]` as the right edge
int height = A[s.top()]; // Take the popped element as the height
s.pop();
int left = s.size() ? s.top() : -1; // Take the element left on the stack as the left edge
ans = max(ans, (i – left – 1) * height);
}
s.push(i);
}
return ans;
}
};
‘’’
Một số bài tập tham khảo và không quá dễ:
1.https://leetcode.com/problems/remove-k-digits/
2.https://leetcode.com/problems/next-greater-element-i/
3.https://leetcode.com/problems/next-greater-node-in-linked-list/
4.https://leetcode.com/problems/next-greater-element-ii/
5.https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/
6.https://leetcode.com/problems/maximal-rectangle/
7.https://leetcode.com/problems/count-submatrices-with-all-ones/
2,122 total views, 7 views today