Phân biệt sức chứa với số phần tử đang dùng
Đây là phần vận dụng cách biểu diễn bằng mảng của SGK. Tạo `T = [None] * N` với N nguyên dương, giữ nguyên N ô. Chỉ số idx (ngăn xếp) hoặc last (hàng đợi) bắt đầu bằng −1. Vùng đang dùng là từ 0 đến chỉ số ấy; số phần tử là chỉ số + 1.
Rỗng khi chỉ số bằng −1; đầy khi bằng N−1. Khi thêm phải kiểm đầy trước; khi lấy phải kiểm rỗng trước. Trong mô hình này, sức chứa N không thay đổi mỗi lần lấy; `len(T)` luôn bằng N.
Ngăn xếp: thêm và lấy ở cuối vùng đang dùng
Các hàm trả về chỉ số mới. Cần gán lại, chẳng hạn `idx = fixed_push(T, idx, 4)` hoặc `x, idx = fixed_pop(T, idx)`. Giả định chỉ số đầu vào là chỉ số hiện hành hợp lệ.
```python
def fixed_push(T, idx, x):
if idx == len(T) - 1:
raise ValueError("Ngăn xếp đầy")
idx += 1
T[idx] = x
return idx
def fixed_pop(T, idx):
if idx == -1:
raise ValueError("Ngăn xếp rỗng")
x = T[idx]
T[idx] = None
return x, idx - 1
```
Hàng đợi: lấy đầu rồi dồn vùng đang dùng
Sau khi lấy T[0], dịch các phần tử đang dùng về trước và xóa ô cuối cũ bằng None. Đây là cách biểu diễn đơn giản, không phải hàng đợi vòng.
```python
def fixed_enqueue(T, last, x):
if last == len(T) - 1:
raise ValueError("Hàng đợi đầy")
last += 1
T[last] = x
return last
def fixed_dequeue(T, last):
if last == -1:
raise ValueError("Hàng đợi rỗng")
x = T[0]
for i in range(last):
T[i] = T[i + 1]
T[last] = None
return x, last - 1
```
Với N=3, T=[4,8,None], last=1, `x,last = fixed_dequeue(T,last)` cho x=4, last=0, T=[8,None,None]. Thêm 6 tiếp theo cho T=[8,6,None], last=1. Mảng vẫn có ba ô; chỉ vùng dữ liệu thay đổi.
Bài luyện
N=3, idx=2. Ngăn xếp đang ở trạng thái nào?
Rỗng dùng idx=-1.
Số phần tử là idx+1.
Đúng. idx=N−1, cả ba ô đang dùng.
Chỉ số 2 tương ứng phần tử thứ ba.
Lời giải
Các vị trí đang dùng là 0,1,2, tổng cộng idx+1=3 phần tử. Vì idx bằng N−1 nên ngăn xếp đầy, không được thêm trước khi lấy bớt.
Bài luyện
T=[4,8,None], last=1. Sau fixed_dequeue đúng như mã, kết quả nào đúng?
Đúng. Lấy đầu, dồn 8, giữ nguyên sức chứa.
8 nằm cuối, không phải đầu.
Không được giảm len(T) hoặc giữ chỉ số cũ.
8 vẫn còn trong hàng đợi.
Lời giải
Lưu x=T[0]=4, dồn T[1]=8 về T[0], gán ô cuối cũ T[1]=None. Trả chỉ số mới 0; T vẫn dài 3 và đang có một phần tử là 8.
Bài luyện
Vì sao phải viết idx = fixed_push(T,idx,4) thay vì chỉ gọi fixed_push(T,idx,4)?
Sức chứa trong mô hình này cố định.
Quy tắc thêm/lấy quyết định LIFO.
Hàm chỉ gán ô mới.
Đúng. Cần giữ chỉ số bên ngoài đồng bộ với dữ liệu.
Lời giải
Hàm thay ô trong T và trả về idx đã tăng. Tham số số nguyên idx trong hàm không tự đổi biến idx của nơi gọi. Gán lại giúp thao tác sau dùng đúng chỉ số hiện hành.
Đang học