Elearning CodePath – CTP Online Judge

Stack Simulation

STACK_SIMULATION

🟢 Easy #General #Hash

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một dãy số nguyên ban đầu **rỗng** và $Q$ truy vấn (query). Thực hiện các truy vấn theo thứ tự. Các truy vấn thuộc một trong ba dạng sau:

1.  **Thêm (Push):** Thêm một phần tử có giá trị $u$ vào **cuối** dãy.
2.  **Loại bỏ (Pop):** Loại bỏ phần tử ở **cuối** dãy. Nếu dãy rỗng, bỏ qua truy vấn này (không làm gì cả).
3.  **Xem (Top):** In ra giá trị của phần tử ở **cuối** dãy. Nếu dãy rỗng, in ra $-1$.

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `stack.inp` gồm:

* **Dòng 1:** Gồm số nguyên $Q$ – số lượng truy vấn.
* **Dòng 2 đến $Q+1$:** Mỗi dòng ghi một trong ba dạng truy vấn.
    * Truy vấn dạng 1: `1 u` (hai số nguyên cách nhau một khoảng trắng).
    * Truy vấn dạng 2 hoặc 3: `2` hoặc `3` (một số nguyên).

**Giới hạn (Ràng buộc):**
$1 \le Q \le 10^5 $
$0 \le u \le 10^9$
---

### 📤 Định dạng Đầu ra

Ghi ra file `stack.out` kết quả của **mọi** truy vấn loại 3, mỗi kết quả trên một dòng riêng biệt.

---

### ✨ Ví dụ

| Input (`stack.inp`) | Output (`stack.out`) |
| :--- | :--- |
| `6` `1 2` `1 3` `2` `3` `2` `3` | `2` `-1` |

---

### 🧪 Giải thích Ví dụ

| Bước | Truy vấn | Dãy số (Stack) | Output |
| :---: | :--- | :--- | :--- |
| 0 | - | $\emptyset$ | - |
| 1 | `1 2` | $[2]$ | - |
| 2 | `1 3` | $[2, 3]$ | - |
| 3 | `2` (Pop 3) | $[2]$ | - |
| 4 | `3` (Top) | $[2]$ | **2** |
| 5 | `2` (Pop 2) | $\emptyset$ | - |
| 6 | `3` (Top) | $\emptyset$ | **-1** |

---

### 💡 Gợi ý thuật toán

Sử dụng cấu trúc dữ liệu **Stack** (hoặc một mảng/vector hoạt động như Stack) để quản lý dãy số. Đảm bảo các thao tác **Push**, **Pop**, và **Top** đều có độ phức tạp thời gian **$O(1)$** để đạt hiệu suất $O(Q)$ tổng thể.

✅ Đã AC: 1 / 2 submissions