Bài 11: STL cơ bản trong C++ và Python: vector, stack, queue, set, map (kèm bài kiểm tra dấu ngoặc, Josephus)
Lời mở đầu
Đến giờ, mọi thứ ta đều tự cài đặt bằng mảng. Điều đó rất tốt để hiểu bản chất, nhưng khi thi, tự viết lại những thứ quen thuộc vừa mất thời gian vừa dễ sai. C++ có sẵn STL (Standard Template Library): một thư viện các cấu trúc dữ liệu và hàm đã được tối ưu, dùng chỉ bằng một dòng #include <bits/stdc++.h>. Bài này giới thiệu 5 “món đồ nghề” dùng nhiều nhất: vector, stack, queue, set, map. Với mỗi món, em sẽ học nó lưu dữ liệu ra sao, các thao tác chính và độ phức tạp của chúng (đã học ở bài 9), kèm cách viết tương ứng trong Python.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1vector: mảng tự co giãn
Ta đã làm quen vector ở bài 6. Đây là bảng tóm tắt các thao tác hay dùng nhất, đối chiếu với list của Python. Hãy để ý cột độ phức tạp: thêm/xóa ở cuối rất nhanh $O(1)$, còn thêm/xóa ở giữa phải dịch cả đoạn phía sau nên mất $O(n)$, giống hệt mảng tự cài đặt.
| Việc cần làm | C++ (vector<int> v) | Python (list v) | Độ phức tạp |
|---|---|---|---|
| Thêm vào cuối | v.push_back(x) | v.append(x) | $O(1)$ |
| Xóa phần tử cuối | v.pop_back() | v.pop() | $O(1)$ |
| Phần tử đầu / cuối | v.front(), v.back() | v[0], v[-1] | $O(1)$ |
| Số phần tử, kiểm tra rỗng | v.size(), v.empty() | len(v), not v | $O(1)$ |
| Chèn / xóa ở vị trí k | v.insert(v.begin() + k, x), v.erase(v.begin() + k) | v.insert(k, x), v.pop(k) | $O(n)$ |
| Sắp xếp, đảo ngược | sort(v.begin(), v.end()), reverse(…) | v.sort(), v.reverse() | $O(n \log n)$, $O(n)$ |
| Duyệt mọi phần tử | for(int x : v) | for x in v: | $O(n)$ |
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> v; // rỗng
int n; cin >> n;
for(int i = 0; i < n; i++){ int x; cin >> x; v.push_back(x); }
sort(v.begin(), v.end());
for(int x : v) cout << x << " "; // duyệt kiểu "for-each"
cout << "\nMin = " << v.front() << ", Max = " << v.back();
vector<int> w(5, 0); // vector 5 phần tử, đều bằng 0
vector<vector<int>> g(3, vector<int>(4)); // ma trận 3 x 4 (bài 7)
return 0;
}n = int(input())
v = list(map(int, input().split()))
v.sort()
print(*v)
print("Min =", v[0], ", Max =", v[-1])
w = [0] * 5
g = [[0] * 4 for _ in range(3)]Phần 2stack: ngăn xếp, vào sau ra trước
Hãy tưởng tượng một chồng đĩa: đĩa đặt vào sau cùng nằm trên đỉnh, và khi lấy ra cũng chỉ lấy được đĩa trên đỉnh. Đó là stack (ngăn xếp), nguyên tắc LIFO (Last In, First Out: vào sau, ra trước). Ba thao tác chính đều $O(1)$: push(x) đặt lên đỉnh, top() xem đỉnh, pop() bỏ đỉnh. Nút “Quay lại” (Undo) của trình soạn thảo, ngăn xếp lời gọi hàm đệ quy ở bài 5 đều hoạt động theo kiểu stack.
Bài kinh điển: dãy ngoặc đúng. Cho xâu chỉ gồm các dấu ( ) [ ] { }. Xâu là “đúng” nếu mỗi dấu mở đều được đóng bằng đúng loại, theo đúng thứ tự lồng nhau, ví dụ ([]{}) đúng còn ([)] sai. Ý tưởng: duyệt từng ký tự; gặp dấu mở thì push vào stack; gặp dấu đóng thì dấu mở gần nhất chưa được đóng phải nằm ở đỉnh stack và phải cùng loại.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
stack<char> st;
bool ok = true;
for(char c : s){
if(c == '(' || c == '[' || c == '{'){
st.push(c);
} else {
if(st.empty()){ ok = false; break; }
char m = st.top();
if((c == ')' && m != '(') || (c == ']' && m != '[') || (c == '}' && m != '{')){
ok = false; break;
}
st.pop();
}
}
if(!st.empty()) ok = false;
cout << (ok ? "YES" : "NO");
return 0;
}s = input().strip()
st = []
cap = {')': '(', ']': '[', '}': '{'}
ok = True
for c in s:
if c in '([{':
st.append(c) # push
else:
if not st or st[-1] != cap[c]:
ok = False
break
st.pop() # pop
if st:
ok = False
print("YES" if ok else "NO")Mô phỏng trực quan. Vì sao kiểm tra dấu ngoặc lại cần đúng một cái stack? Em bấm Tiếp để xem stack lớn lên khi gặp ngoặc mở, co lại khi gặp ngoặc đóng; rồi thử các dãy sai như ([)], ((), ()) để thấy ba kiểu sai khác nhau được phát hiện ở đâu.
Phần 3queue: hàng đợi, vào trước ra trước
queue (hàng đợi) giống hàng người xếp mua vé: ai đến trước được phục vụ trước, nguyên tắc FIFO (First In, First Out). Các thao tác đều $O(1)$: push(x) thêm vào cuối hàng, front() xem người đầu hàng, pop() cho người đầu hàng đi. Trong Python không nên dùng list.pop(0) (mất $O(n)$) mà dùng collections.deque với popleft(). Queue là trái tim của thuật toán tìm đường đi ngắn nhất BFS mà em sẽ học sau này.
Bài toán Josephus. $n$ người đứng thành vòng tròn, đánh số 1 tới $n$. Bắt đầu đếm từ người số 1, cứ đếm đến người thứ $k$ thì người đó bị loại, rồi đếm tiếp từ người kế bên. Hỏi thứ tự bị loại? Dùng queue: mỗi lần đếm, người đầu hàng đi xuống cuối hàng (pop rồi push lại), đến người thứ $k$ thì pop hẳn.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
queue<int> q;
for(int i = 1; i <= n; i++) q.push(i);
while(!q.empty()){
for(int t = 1; t < k; t++){
q.push(q.front());
q.pop();
}
cout << q.front() << " ";
q.pop();
}
return 0;
}from collections import deque
n, k = map(int, input().split())
q = deque(range(1, n + 1))
kq = []
while q:
q.rotate(-(k - 1)) # đưa k-1 người đầu xuống cuối hàng
kq.append(q.popleft()) # người thứ k bị loại
print(*kq)Mô phỏng trực quan. Bài Josephus dùng queue thay cho vòng tròn: ai chưa bị loại thì đi từ đầu xuống cuối hàng. Em nhập n, k rồi bấm Tiếp để xem từng lần pop – push và tự kiểm tra lại kết quả chạy tay của mình.
Phần 4set: tập hợp không trùng lặp, tự sắp xếp
set lưu các phần tử khác nhau và luôn giữ chúng theo thứ tự tăng dần. Thêm một phần tử đã có thì set không thay đổi. Mọi thao tác thêm (insert), xóa (erase), kiểm tra có hay không (count hoặc find) đều mất $O(\log n)$, nhanh hơn hẳn việc dò tuần tự $O(n)$ trên mảng. Python cũng có set, nhưng không tự sắp xếp (khi cần thứ tự thì dùng sorted(s)).
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
set<int> s;
for(int i = 0; i < n; i++){
int x; cin >> x;
s.insert(x);
}
cout << s.size() << "\n";
for(int x : s) cout << x << " ";
return 0;
}n = int(input())
a = list(map(int, input().split()))
s = set(a)
print(len(s))
print(*sorted(s))Các thao tác khác của set
set<int> s = {5, 1, 9};
s.insert(3); // {1, 3, 5, 9}
s.erase(5); // {1, 3, 9}
if(s.count(3)) cout << "co 3\n"; // count trả về 1 nếu có, 0 nếu không
cout << *s.begin() << " " << *s.rbegin(); // phần tử nhỏ nhất, lớn nhất: 1 9
multiset<int> ms = {2, 2, 7}; // multiset: giống set nhưng cho phép trùngs = {5, 1, 9}
s.add(3)
s.discard(5) # xóa, không báo lỗi nếu không có
if 3 in s:
print("co 3")
print(min(s), max(s))Phần 5map: từ điển khóa → giá trị
map lưu các cặp khóa → giá trị, giống quyển từ điển: tra “khóa” (từ) để lấy “giá trị” (nghĩa). Khác mảng chỉ dùng chỉ số $0..n-1$, khóa của map có thể là bất kỳ: số rất lớn như $10^9$, số âm, xâu ký tự… Ứng dụng số 1 là đếm tần suất: dem[x]++. Truy cập một khóa chưa có thì map tự tạo khóa đó với giá trị 0. Các khóa được giữ tăng dần, thao tác mất $O(\log n)$. Python dùng dict (hoặc collections.Counter để đếm).
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
map<string, int> dem;
for(int i = 0; i < n; i++){
string w; cin >> w;
dem[w]++;
}
for(auto p : dem)
cout << p.first << " " << p.second << "\n";
return 0;
}from collections import Counter
n = int(input())
dem = Counter(input().split())
for w in sorted(dem):
print(w, dem[w])Thử ngay: chọn một cấu trúc, gõ giá trị và bấm các nút thao tác để thấy dữ liệu thay đổi thế nào. Dòng nhật ký ghi lại câu lệnh C++ tương ứng với mỗi thao tác.
Bài tậpLuyện STL
Mỗi bài hãy viết bằng cấu trúc STL thích hợp, rồi tự hỏi: nếu chỉ dùng mảng và vòng lặp thì độ phức tạp là bao nhiêu? Giới hạn chung $n, q \le 10^5$.
Cho dãy $n$ số, in dãy theo thứ tự ngược lại. Hãy làm bằng stack.
5
1 2 3 4 55 4 3 2 1💡 Gợi ý
top() và pop(). Số vào sau cùng ra trước tiên nên thứ tự bị đảo ngược.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
stack<int> st;
for(int i = 0; i < n; i++){ int x; cin >> x; st.push(x); }
while(!st.empty()){
cout << st.top() << " ";
st.pop();
}
return 0;
}n = int(input())
st = list(map(int, input().split()))
out = []
while st:
out.append(st.pop())
print(*out)Dòng đầu là $t$, mỗi dòng sau là một xâu gồm các dấu ngoặc ()[]{}. Với mỗi xâu in YES nếu là dãy ngoặc đúng, ngược lại in NO.
3
([]{})
([)]
((YES
NO
NO💡 Gợi ý
bool dung(string s) rồi gọi $t$ lần. Nhớ tạo stack mới (rỗng) cho mỗi xâu.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool dung(const string &s){
stack<char> st;
for(char c : s){
if(c == '(' || c == '[' || c == '{') st.push(c);
else {
if(st.empty()) return false;
char m = st.top(); st.pop();
if((c == ')' && m != '(') || (c == ']' && m != '[') || (c == '}' && m != '{')) return false;
}
}
return st.empty();
}
int main(){
int t;
cin >> t;
while(t--){
string s; cin >> s;
cout << (dung(s) ? "YES" : "NO") << "\n";
}
return 0;
}def dung(s):
st, cap = [], {')': '(', ']': '[', '}': '{'}
for c in s:
if c in '([{':
st.append(c)
elif not st or st.pop() != cap[c]:
return False
return not st
t = int(input())
for _ in range(t):
print("YES" if dung(input().strip()) else "NO")Cho dãy $n$ số nguyên ($|a_i| \le 10^9$). Đếm số giá trị khác nhau.
7
4 1 4 2 1 9 44💡 Gợi ý
set rồi in s.size(), độ phức tạp $O(n \log n)$. Không dùng được mảng đánh dấu vì giá trị tới $10^9$ (và có thể âm). Python: len(set(a)).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
set<int> s;
for(int i = 0; i < n; i++){ int x; cin >> x; s.insert(x); }
cout << s.size();
return 0;
}n = int(input())
print(len(set(map(int, input().split()))))Cho dãy $n$ số nguyên. In số xuất hiện nhiều lần nhất và số lần xuất hiện của nó; nếu có nhiều số cùng nhiều nhất, in số nhỏ nhất.
8
3 1 3 2 1 3 2 22 3💡 Gợi ý
map<int, int> dem. Duyệt map theo thứ tự khóa tăng dần, chỉ cập nhật khi số lần lớn hơn hẳn kỷ lục hiện tại, như vậy khi bằng nhau sẽ giữ lại số nhỏ hơn.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
map<int, int> dem;
for(int i = 0; i < n; i++){ int x; cin >> x; dem[x]++; }
int best = 0, sl = 0;
for(auto p : dem){
if(p.second > sl){ sl = p.second; best = p.first; }
}
cout << best << " " << sl;
return 0;
}from collections import Counter
n = int(input())
dem = Counter(map(int, input().split()))
best = min(dem, key=lambda x: (-dem[x], x))
print(best, dem[best])Cho $n$ và $n$ từ. In mỗi từ khác nhau kèm số lần xuất hiện, theo thứ tự từ điển.
8
the cat and the hat and the batand 2
bat 1
cat 1
hat 1
the 3💡 Gợi ý
map<string, int> tự giữ các khóa theo thứ tự từ điển nên chỉ cần duyệt và in.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
map<string, int> dem;
for(int i = 0; i < n; i++){ string w; cin >> w; dem[w]++; }
for(auto p : dem) cout << p.first << " " << p.second << "\n";
return 0;
}from collections import Counter
n = int(input())
dem = Counter(input().split())
for w in sorted(dem):
print(w, dem[w])Cho $n, k$ ($n, k \le 1000$). In thứ tự bị loại trong trò chơi Josephus ở phần 3.
7 33 6 2 7 5 1 4💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
queue<int> q;
for(int i = 1; i <= n; i++) q.push(i);
while(!q.empty()){
for(int t = 1; t < k; t++){ q.push(q.front()); q.pop(); }
cout << q.front() << " ";
q.pop();
}
return 0;
}from collections import deque
n, k = map(int, input().split())
q = deque(range(1, n + 1))
kq = []
while q:
q.rotate(-(k - 1))
kq.append(q.popleft())
print(*kq)Cho dãy $n$ số nguyên và số $x$. Có tồn tại hai chỉ số $i \lt j$ với $a_i + a_j = x$ không? In YES hoặc NO.
5 9
2 7 11 15 1YES💡 Gợi ý
set chứa các số đã gặp. Tại $a_j$, nếu $x - a_j$ đã có trong set thì có cặp. Rồi mới thêm $a_j$ vào set (để không ghép một số với chính nó). Độ phức tạp $O(n \log n)$ thay vì $O(n^2)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
long long x;
cin >> n >> x;
set<long long> da;
bool co = false;
for(int i = 0; i < n; i++){
long long a; cin >> a;
if(da.count(x - a)) co = true;
da.insert(a);
}
cout << (co ? "YES" : "NO");
return 0;
}n, x = map(int, input().split())
a = list(map(int, input().split()))
da, co = set(), False
for v in a:
if x - v in da:
co = True
da.add(v)
print("YES" if co else "NO")Ban đầu tập hợp rỗng. Có $q$ truy vấn, mỗi truy vấn một dòng: 1 x thêm $x$, 2 x xóa $x$ (nếu có), 3 x hỏi $x$ có trong tập không (in YES/NO).
6
1 5
1 3
3 5
2 5
3 5
3 3YES
NO
YES💡 Gợi ý
set: insert, erase, count, mỗi truy vấn $O(\log n)$. Nếu dùng mảng dò tuần tự thì mỗi truy vấn mất $O(n)$, tổng $10^{10}$ → TLE.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
set<int> s;
while(q--){
int t, x; cin >> t >> x;
if(t == 1) s.insert(x);
else if(t == 2) s.erase(x);
else cout << (s.count(x) ? "YES" : "NO") << "\n";
}
return 0;
}import sys
data = sys.stdin.read().split()
q = int(data[0])
s, out = set(), []
for i in range(q):
t, x = int(data[1 + 2 * i]), int(data[2 + 2 * i])
if t == 1:
s.add(x)
elif t == 2:
s.discard(x)
else:
out.append("YES" if x in s else "NO")
print('\n'.join(out))
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét