Ngăn xếp (Stack)
Stack hoạt động theo nguyên tắc LIFO (Last In, First Out) — phần tử vào sau sẽ ra trước.
Các thao tác cơ bản —
| Thao tác | Mô tả |
|---|---|
push(x) |
Thêm x vào đỉnh stack |
pop() |
Xóa phần tử ở đỉnh stack |
top() |
Xem phần tử ở đỉnh (không xóa) |
empty() |
Kiểm tra stack rỗng |
C++
#include <stack>
stack<int> st;
st.push(1); st.push(2); st.push(3);
cout << st.top(); // 3
st.pop();
cout << st.top(); // 2
Python
st = []
st.append(1); st.append(2); st.append(3)
print(st[-1]) # 3
st.pop()
print(st[-1]) # 2
Ứng dụng: Monotonic Stack
Tìm phần tử lớn hơn gần nhất bên phải mỗi phần tử — :
vector<int> nextGreater(vector<int>& a) {
int n = a.size();
vector<int> res(n, -1);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
res[st.top()] = a[i];
st.pop();
}
st.push(i);
}
return res;
}
Hàng đợi (Queue)
Queue hoạt động theo nguyên tắc FIFO (First In, First Out) — phần tử vào trước sẽ ra trước.
Các thao tác cơ bản —
| Thao tác | Mô tả |
|---|---|
push(x) |
Thêm x vào cuối hàng đợi |
pop() |
Xóa phần tử ở đầu hàng đợi |
front() |
Xem phần tử đầu hàng đợi |
empty() |
Kiểm tra hàng đợi rỗng |
C++
#include <queue>
queue<int> q;
q.push(1); q.push(2); q.push(3);
cout << q.front(); // 1
q.pop();
cout << q.front(); // 2
Python
from collections import deque
q = deque()
q.append(1); q.append(2); q.append(3)
print(q[0]) # 1
q.popleft()
print(q[0]) # 2
Ứng dụng: BFS
vector<int> bfs(int start, vector<vector<int>>& adj) {
int n = adj.size();
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
Deque (Double-ended Queue)
Deque hỗ trợ thêm/xóa ở cả hai đầu trong . Dùng trong kỹ thuật Sliding Window Maximum để tìm max/min trong cửa sổ trượt .
#include <deque>
deque<int> dq;
dq.push_front(1);
dq.push_back(2);
dq.pop_front();
dq.pop_back();
Bình luận