Stack, Queue, Deque
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Mảng 1 chiều
- Chủ đề
- dequequeuestack
- Trạng thái
Kiến thức cơ bản
Vì sao cần stack và queue
Có những việc người ta luôn làm theo một quy tắc cố định: lấy chiếc đĩa trên cùng của chồng đĩa, hoặc phục vụ người đứng đầu hàng. Nếu dùng vector, em phải tự nhớ vị trí cần lấy, rất dễ nhầm. C++ có sẵn hai “cấu trúc dữ liệu” giữ đúng quy tắc ấy: stack và queue. Mỗi thao tác của chúng chỉ mất một bước (một cái chớp mắt dù có 105 phần tử).
Để dùng, em thêm thư viện: #include <stack> và #include <queue>. Các đoạn code dưới đây là phần thân hàm main.
Cấu trúc dữ liệu Stack (chồng)
Stack giống một chồng đĩa: đĩa đặt vào sau cùng thì được lấy ra đầu tiên. Quy tắc này gọi là vào sau, ra trước (LIFO). Ta chỉ được nhìn và lấy chiếc đĩa trên cùng (đỉnh).
push(1), push(2), push(3) pop()
| 3 | <- đỉnh (top) | 2 | <- đỉnh mới
| 2 | | 1 |
| 1 | +---+
+---+
Khai báo stack
stack<data_type> st; (ví dụ: stack<int> st;)
stack<int> st;
st.push(1); st.push(2); st.push(3); // chồng từ dưới lên: 1 2 3
cout << st.top() << endl; // 3: chỉ nhìn thấy đĩa trên cùng
st.pop(); // bỏ đĩa 3
cout << st.top() << " " << st.size() << endl; // 2 2
while (!st.empty()) { // lấy lần lượt ra: 2 rồi 1
cout << st.top() << " ";
st.pop();
}
Các tính chất của stack
- Stack không có chỉ số: không viết được st[0] và không duyệt bằng for như vector. Muốn xem hết, ta lấy ra từng phần tử bằng vòng while như trên.
- top() chỉ nhìn, pop() mới bỏ đi, và pop() không trả về giá trị. Muốn lấy đĩa trên cùng ra dùng thì viết x = st.top(); rồi st.pop();
- Luôn kiểm tra st.empty() trước khi gọi top() hoặc pop(). Gọi khi chồng rỗng làm chương trình lỗi.
Một số hàm của stack
| push(x) | Đặt x lên đỉnh chồng. |
|---|---|
| top() | Xem phần tử ở đỉnh chồng (không lấy ra). Chồng rỗng mà gọi top() là lỗi. |
| pop() | Bỏ phần tử ở đỉnh chồng. Hàm này chỉ bỏ đi, không trả về giá trị. Chồng rỗng mà gọi pop() là lỗi. |
| size() | Số phần tử trong chồng. |
| empty() | Kiểm tra chồng rỗng: đúng trả về true, sai trả về false. |
Cấu trúc dữ liệu Queue (hàng đợi)
Queue giống một hàng xếp mua vé: ai đến trước được phục vụ trước. Quy tắc này gọi là vào trước, ra trước (FIFO). Người mới đứng vào cuối hàng, người ở đầu hàng được phục vụ xong thì rời đi.
cuối hàng (back) đầu hàng (front)
push(x) -> [ 5 ] [ 3 ] [ 8 ] [ 2 ] -> pop()
(người đầu hàng rời đi)
Khai báo queue
queue<data_type> q; (ví dụ: queue<int> q;)
queue<int> q;
q.push(5); q.push(3); q.push(8); // hàng: 5 3 8 (5 đứng đầu)
cout << q.front() << " " << q.back() << endl; // 5 8
q.pop(); // người đầu hàng (5) rời đi
cout << q.front() << " " << q.size() << endl; // 3 2
while (!q.empty()) { // phục vụ lần lượt: 3 rồi 8
cout << q.front() << " ";
q.pop();
}
Các tính chất của queue
- Queue cũng không có chỉ số. Ta chỉ nhìn được hai đầu: front() và back().
- Cũng như stack: pop() chỉ bỏ đi và không trả về giá trị; nhớ kiểm tra empty() trước khi gọi front() hoặc pop().
Một số hàm của queue
| push(x) | Cho x vào cuối hàng. |
|---|---|
| front() | Xem phần tử ở đầu hàng (không lấy ra). Hàng rỗng mà gọi front() là lỗi. |
| back() | Xem phần tử ở cuối hàng. |
| pop() | Cho người đầu hàng rời đi. Hàm này chỉ bỏ đi, không trả về giá trị. Hàng rỗng mà gọi pop() là lỗi. |
| size() | Số phần tử trong hàng. |
| empty() | Kiểm tra hàng rỗng: đúng trả về true, sai trả về false. |
Mẫu 1: Kiểm tra dãy ngoặc đúng (stack)
Bài toán: cho xâu chỉ gồm dấu ( và ). Hỏi xâu có “đúng” không, tức là mỗi dấu đóng ghép được với một dấu mở đứng trước và không còn dấu mở nào thừa? Mỗi dấu mở là một chiếc đĩa đang chờ ghép; gặp dấu đóng thì lấy chiếc đĩa trên cùng ra ghép.
Xâu: ( ( ) ( ) )
gặp ( -> push chồng: (
gặp ( -> push chồng: ( (
gặp ) -> pop chồng: (
gặp ( -> push chồng: ( (
gặp ) -> pop chồng: (
gặp ) -> pop chồng: rỗng -> ĐÚNG
string s;
cin >> s;
stack<char> st;
bool ok = true;
for (char c : s) {
if (c == '(') st.push(c); // dấu mở: cất vào chồng
else { // dấu đóng: cần một dấu mở đang chờ
if (st.empty()) { ok = false; break; }
st.pop();
}
}
if (!st.empty()) ok = false; // còn dấu mở chưa được đóng
cout << (ok ? "YES" : "NO");
Mẫu 2: Mô phỏng xếp hàng (queue)
Bài toán: n bạn đứng vòng tròn, đếm từ bạn số 1: cứ đếm đến bạn thứ k thì bạn đó rời vòng. Hỏi ai ở lại cuối cùng? Ta xếp các bạn thành một hàng. Đếm đến bạn nào chưa phải thứ k thì bạn đó đi xuống cuối hàng (đứng lại vòng), còn bạn thứ k thì rời hẳn.
queue<int> q;
for (int i = 1; i <= n; i++) q.push(i);
while (q.size() > 1) {
for (int t = 1; t < k; t++) { // k - 1 bạn đầu hàng xuống đứng cuối hàng
q.push(q.front());
q.pop();
}
q.pop(); // bạn thứ k rời vòng
}
cout << q.front();
Với n và k cỡ 1000, vòng for chạy tối đa khoảng n × k = 106 lần, máy tính chạy chỉ trong một cái chớp mắt.
Mẫu 3: Phần tử lớn hơn gần nhất bên phải (stack lưu chỉ số)
Bài toán: với mỗi a[i], tìm số đầu tiên đứng bên phải a[i] mà lớn hơn a[i]. Cách chậm: với mỗi i duyệt sang phải, mất n × n = 1010 phép tính khi n = 105. Cách nhanh: các bạn chưa tìm được “người cao hơn” cùng xếp vào một chồng. Bạn mới đến, nếu cao hơn những bạn đang ở đỉnh chồng thì chính là người họ đang chờ, và những bạn đó được bỏ ra khỏi chồng. Mỗi bạn vào chồng một lần và ra một lần nên tổng cộng chỉ khoảng 2n bước.
a = 4 5 2 25 7 8
i=0: chồng {} push 4
i=1: 5 > 4 -> 4 tìm được 5, pop; push 5
i=2: 2 < 5 -> không pop; push 2 chồng: 5 2
i=3: 25 > 2 và 25 > 5 -> cả hai tìm được 25; push 25
i=4: 7 < 25; push 7 chồng: 25 7
i=5: 8 > 7 -> 7 tìm được 8; push 8
Còn lại 25, 8 trong chồng: không có số lớn hơn -> -1
vector<int> res(n, -1);
stack<int> st; // lưu CHỈ SỐ các bạn chưa tìm được người cao hơn
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
res[st.top()] = a[i]; // a[i] là số lớn hơn đầu tiên bên phải
st.pop();
}
st.push(i);
}
Mở rộng (không bắt buộc): deque
deque (đọc là “đéc”) là hàng đợi hai đầu: thêm và bớt được ở cả đầu lẫn cuối, lại có chỉ số như vector. Cần thêm #include <deque>.
deque<int> dq;
dq.push_back(1); dq.push_front(2); // {2, 1}
dq.push_back(3); // {2, 1, 3}
dq.pop_front(); // {1, 3}
cout << dq.front() << " " << dq.back() << " " << dq[1]; // 1 3 3
| push_back(x), push_front(x) | Thêm x vào cuối, hoặc vào đầu. |
|---|---|
| pop_back(), pop_front() | Bỏ phần tử ở cuối, hoặc ở đầu. |
| front(), back() | Xem phần tử ở đầu, ở cuối. |
| dq[i] | Truy cập theo chỉ số như vector (deque có chỉ số, stack và queue thì không). |
Nhận dạng đề bài
| Dấu hiệu trong đề | Công cụ | Cách làm |
|---|---|---|
| Việc đến sau làm trước; “quay lui”, hoàn tác, đảo ngược | stack | push khi gặp, pop khi cần lấy lại phần tử gần nhất |
| Ngoặc đúng, xóa cặp liền kề, tính biểu thức | stack | Gặp dấu đóng thì ghép với dấu mở trên đỉnh |
| Với mỗi phần tử, tìm phần tử lớn hơn (nhỏ hơn) gần nhất bên phải hoặc bên trái | stack lưu chỉ số | Phần tử mới “giải phóng” những phần tử nhỏ hơn đang chờ trên đỉnh |
| Xếp hàng, đến trước phục vụ trước, đếm vòng tròn | queue | push người mới ở cuối, pop người ở đầu |
| Thêm hoặc bớt ở cả hai đầu, cửa sổ trượt lớn nhất | deque (không bắt buộc) | Giữ các ứng viên tốt nhất ở đầu deque |
Luyện tập
Bài 1. Chồng đĩa của Gấu Po
Gấu Po có một chồng đĩa, ban đầu chưa có chiếc nào. Mỗi chiếc đĩa ghi một số. Gấu Po thực hiện q thao tác: đặt một đĩa lên đỉnh chồng, bỏ chiếc đĩa trên đỉnh, hoặc nhìn xem số ghi trên chiếc đĩa ở đỉnh. Hãy giúp Gấu Po trả lời các lần nhìn.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong ba dạng: 1 x: đặt đĩa ghi số x lên đỉnh (1 ≤ x ≤ 109). 2: bỏ đĩa trên đỉnh (nếu chồng rỗng thì bỏ qua). 3: nhìn đĩa trên đỉnh. | |
|---|---|---|
| Đầu ra | Với mỗi thao tác loại 3, in số ghi trên đĩa ở đỉnh, hoặc in -1 nếu chồng rỗng. | |
| Test | Input | Output |
| 1 | 7 1 5 1 8 3 2 3 2 3 | 8 5 -1 |
| 2 | 4 2 3 1 7 3 | -1 7 |
Bài 2. Đọc ngược dãy số
Thỏ viết n số lên băng giấy rồi muốn đọc chúng theo thứ tự ngược lại, từ số viết sau cùng đến số viết đầu tiên. Hãy dùng stack giúp Thỏ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các số theo thứ tự ngược lại, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 1 2 3 4 5 | 5 4 3 2 1 |
| 2 | 1 9 | 9 |
Bài 3. Dãy ngoặc của Hổ
Hổ viết một dãy chỉ gồm dấu mở ngoặc ( và dấu đóng ngoặc ). Dãy được gọi là đúng nếu mỗi dấu đóng ghép được với một dấu mở đứng trước nó, và không còn dấu mở nào thừa. Hỏi dãy của Hổ có đúng không?
| Đầu vào | Một dòng duy nhất là xâu s gồm các dấu ( và ), dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | In YES nếu dãy đúng, ngược lại in NO. | |
| Test | Input | Output |
| 1 | (()()) | YES |
| 2 | ())( | NO |
Bài 4. Hàng mua vé
Quầy vé của rừng xanh có một hàng người xếp hàng. Mỗi khách có một mã số. Có q sự kiện: một khách mới đứng vào cuối hàng, khách đứng đầu hàng mua vé xong và rời đi, hoặc nhân viên đếm số người đang xếp hàng.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong ba dạng: 1 x: khách có mã x đứng vào cuối hàng (1 ≤ x ≤ 109). 2: khách đứng đầu hàng mua xong và rời đi. 3: đếm số người đang xếp hàng. | |
|---|---|---|
| Đầu ra | Với mỗi sự kiện loại 2, in mã của khách vừa rời đi, hoặc in -1 nếu hàng đang rỗng. Với mỗi sự kiện loại 3, in số người trong hàng. | |
| Test | Input | Output |
| 1 | 7 1 10 1 20 3 2 1 30 2 2 | 2 10 20 30 |
| 2 | 2 2 3 | -1 0 |
Bài 5. Chia kẹo vòng tròn
Có n bạn đứng thành vòng tròn, đánh số từ 1 đến n theo chiều kim đồng hồ. Thỏ đếm từ bạn số 1: 1, 2, ..., k. Bạn được đếm đến số k sẽ rời vòng tròn nhận kẹo. Thỏ lại đếm tiếp từ bạn đứng ngay sau bạn vừa rời đi, và cứ thế cho đến khi chỉ còn một bạn ở lại. Hỏi bạn ở lại cuối cùng là bạn số mấy?
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ n, k ≤ 1000). | |
|---|---|---|
| Đầu ra | Số thứ tự của bạn ở lại cuối cùng. | |
| Test | Input | Output |
| 1 | 7 3 | 4 |
| 2 | 5 2 | 3 |
Bài 6. Ba loại ngoặc
Hổ được đưa một dãy chỉ gồm ba loại ngoặc: ( ), [ ] và { }. Dãy được gọi là đúng nếu mỗi dấu đóng ghép được với dấu mở cùng loại đứng gần nhất chưa được ghép, và không còn dấu mở nào thừa. Hỏi dãy có đúng không?
| Đầu vào | Một dòng duy nhất là xâu s gồm các ký tự ( ) [ ] { }, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | In YES nếu dãy đúng, ngược lại in NO. | |
| Test | Input | Output |
| 1 | {[()]} | YES |
| 2 | ([)] | NO |
Bài 7. Xóa cặp giống nhau
Gấu Po có một xâu chữ cái thường. Mỗi lượt, Gấu Po chọn hai chữ cái giống nhau đứng cạnh nhau và xóa cả hai, hai phần còn lại được nối liền. Gấu Po làm đến khi không xóa được nữa. Hãy cho biết xâu cuối cùng (kết quả không phụ thuộc cách chọn).
| Đầu vào | Một dòng duy nhất là xâu s gồm chữ cái thường, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Xâu sau khi xóa hết các cặp, hoặc in EMPTY nếu xâu rỗng. | |
| Test | Input | Output |
| 1 | abbaca | ca |
| 2 | aabb | EMPTY |
Bài 8. Máy tính của Thỏ
Thỏ viết biểu thức theo kiểu hậu tố: viết hai số trước, rồi mới viết phép tính. Ví dụ 3 4 + nghĩa là 3 + 4. Máy tính của Thỏ đọc từng ký hiệu từ trái sang phải: gặp số thì cất vào chồng, gặp phép tính thì lấy hai số trên cùng ra tính rồi cất kết quả vào lại chồng. Hãy tính giá trị của biểu thức.
| Đầu vào | Dòng 1: số nguyên m (1 ≤ m ≤ 105) là số ký hiệu. Dòng 2: m ký hiệu cách nhau một dấu cách, mỗi ký hiệu là một số nguyên không âm không quá 1000 hoặc một trong các dấu + - *. Biểu thức luôn hợp lệ và mọi kết quả trung gian có giá trị tuyệt đối không quá 1018. | |
|---|---|---|
| Đầu ra | Giá trị của biểu thức. | |
| Test | Input | Output |
| 1 | 5 3 4 + 2 * | 14 |
| 2 | 7 2 3 4 * + 5 - | 9 |
Bài 9. Người cao hơn gần nhất
Hổ cho n bạn đứng thành một hàng ngang, bạn thứ i cao a[i]. Mỗi bạn nhìn sang bên phải và muốn biết bạn đầu tiên cao hơn mình là bạn cao bao nhiêu.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách, số thứ i là chiều cao của bạn đầu tiên đứng bên phải bạn i và cao hơn bạn i, hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 6 4 5 2 25 7 8 | 5 25 25 -1 8 -1 |
| 2 | 4 9 7 5 3 | -1 -1 -1 -1 |
Bài tập tự luyện
Bài 1. Bài ảo thuật thẻ bài
Gấu Po có n thẻ bài đánh số từ 1 đến n, xếp thành một chồng, thẻ 1 ở trên cùng và thẻ n ở dưới cùng. Gấu Po lặp lại: bỏ thẻ trên cùng ra ngoài, rồi chuyển thẻ trên cùng kế tiếp xuống dưới đáy chồng. Gấu Po làm đến khi chỉ còn đúng một thẻ. Hãy cho biết thứ tự các thẻ bị bỏ ra và thẻ còn lại.
| Đầu vào | Một dòng gồm số nguyên n (2 ≤ n ≤ 105). | |
|---|---|---|
| Đầu ra | Dòng 1: các thẻ bị bỏ ra theo thứ tự, cách nhau một dấu cách. Dòng 2: thẻ còn lại cuối cùng. | |
| Test | Input | Output |
| 1 | 7 | 1 3 5 7 4 2 6 |
| 2 | 2 | 1 2 |
Bài 2. Đảo từng từ
Thỏ có một câu gồm n từ. Thỏ muốn đảo ngược thứ tự các chữ cái của từng từ, nhưng giữ nguyên thứ tự các từ trong câu. Hãy dùng stack để giúp Thỏ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n từ, mỗi từ chỉ gồm chữ cái thường và dài không quá 100 ký tự. | |
|---|---|---|
| Đầu ra | Câu sau khi đảo từng từ, các từ cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 3 hello gau po | olleh uag op |
| 2 | 1 abc | cba |
Bài 3. Nút hoàn tác
Gấu Po gõ chữ vào máy tính có nút hoàn tác. Có q thao tác: gõ thêm một chữ cái vào cuối văn bản, hoặc bấm hoàn tác để xóa chữ cái gõ sau cùng (nếu văn bản đang rỗng thì không có gì xảy ra). Hãy cho biết văn bản cuối cùng.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong hai dạng: 1 c: gõ chữ cái thường c vào cuối văn bản. 2: bấm hoàn tác. | |
|---|---|---|
| Đầu ra | Văn bản cuối cùng, hoặc in EMPTY nếu văn bản rỗng. | |
| Test | Input | Output |
| 1 | 6 1 a 1 b 1 c 2 1 d 2 | ab |
| 2 | 2 1 x 2 | EMPTY |
Bài 4. Máy in luân phiên
Phòng học có một máy in dùng chung. Có n tệp cần in, tệp thứ i cần t[i] phút. Máy in làm luân phiên: lấy tệp ở đầu hàng, in tối đa q phút. Nếu tệp chưa in xong thì xếp xuống cuối hàng để lần sau in tiếp; nếu in xong thì tệp rời hàng. Hãy cho biết thời điểm mỗi tệp in xong. Thời điểm bắt đầu là 0.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n ≤ 1000; 1 ≤ q ≤ 1000). Dòng 2: n số nguyên t[i] (1 ≤ t[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | n dòng, theo thứ tự in xong, mỗi dòng gồm số thứ tự của tệp và thời điểm in xong, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 3 4 10 4 6 | 2 8 3 18 1 20 |
| 2 | 2 5 3 3 | 1 3 2 6 |
Bài 5. Chuỗi ngày thắng giá
Thỏ ghi lại giá một món đồ chơi trong n ngày liên tiếp. Với mỗi ngày i, “khoảng giá” là số ngày liên tiếp kết thúc ở ngày i (tính cả ngày i) mà giá mỗi ngày đều không lớn hơn giá ngày i. Hãy tính khoảng giá của mỗi ngày.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109) là giá các ngày. | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách, số thứ i là khoảng giá của ngày i. | |
| Test | Input | Output |
| 1 | 7 100 80 60 70 60 75 85 | 1 1 1 2 1 4 6 |
| 2 | 3 5 5 5 | 1 2 3 |
Bài 6. Số nhỏ nhất sau khi xóa chữ số
Gấu Po viết một số nguyên dương rất dài bằng các chữ số. Gấu Po được xóa đúng k chữ số (các chữ số còn lại giữ nguyên thứ tự) để số còn lại là nhỏ nhất có thể. Kết quả không có chữ số 0 đứng đầu; nếu không còn chữ số nào thì kết quả là 0.
| Đầu vào | Dòng 1: xâu s gồm các chữ số, không bắt đầu bằng 0, dài từ 1 đến 105. Dòng 2: số nguyên k (0 ≤ k ≤ độ dài của s). | |
|---|---|---|
| Đầu ra | Số nhỏ nhất sau khi xóa k chữ số. | |
| Test | Input | Output |
| 1 | 1432219 3 | 1219 |
| 2 | 10200 1 | 200 |
| 3 | 10 2 | 0 |
Bài 7. Giải mã chuỗi lặp
Thỏ mã hóa một xâu bằng cách viết d[xâu con] để chỉ xâu con lặp lại d lần (d là một chữ số từ 1 đến 9). Các cặp ngoặc có thể lồng nhau. Ví dụ 3[a2[c]] là accaccacc. Hãy giải mã xâu của Thỏ.
| Đầu vào | Một dòng duy nhất là xâu s gồm chữ cái thường, chữ số 1 đến 9 và các dấu [ ], dài không quá 1000 ký tự, đảm bảo hợp lệ. Xâu sau giải mã dài không quá 105. | |
|---|---|---|
| Đầu ra | Xâu sau khi giải mã. | |
| Test | Input | Output |
| 1 | 3[a2[c]] | accaccacc |
| 2 | 2[ab]3[c]d | ababcccd |
Bài 8. Hình chữ nhật lớn nhất
Hổ xếp n cột gỗ sát nhau thành một hàng, cột thứ i có chiều rộng 1 và chiều cao h[i]. Hổ muốn cắt một hình chữ nhật có các cạnh song song với các cạnh cột, nằm gọn trong các cột liên tiếp. Hãy tìm diện tích lớn nhất của hình chữ nhật đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Diện tích lớn nhất. | |
| Test | Input | Output |
| 1 | 6 2 1 5 6 2 3 | 10 |
| 2 | 3 4 4 4 | 12 |
Bài 9. Thử thách (không bắt buộc): Khung kính lớn nhất
Hổ có n số xếp thành hàng và một khung kính che k số liên tiếp, trượt từ trái sang phải. Với mỗi vị trí của khung, hãy cho biết số lớn nhất nhìn thấy trong khung. (Gợi ý: dùng deque giữ chỉ số các ứng viên theo thứ tự giảm dần của giá trị.)
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | n - k + 1 số cách nhau một dấu cách, số thứ t là số lớn nhất trong khung bắt đầu ở vị trí t. | |
| Test | Input | Output |
| 1 | 8 3 1 3 -1 -3 5 3 6 7 | 3 3 5 5 6 7 |
| 2 | 4 1 2 9 4 1 | 2 9 4 1 |
-
Gợi ý chung: Trước khi gọi top(), front() hoặc pop(), luôn kiểm tra empty() để chắc chắn stack hay queue không rỗng. Gọi khi rỗng làm chương trình lỗi (có thể hiện “Runtime Error” khi nộp bài).
-
Lưu ý thêm: pop() chỉ bỏ phần tử đi chứ không trả về giá trị, nên muốn dùng phần tử đó phải đọc top() hoặc front() trước rồi mới pop(). Stack và queue không có chỉ số, muốn xem hết thì lấy ra từng phần tử bằng vòng while (!st.empty()).