Ngăn xếp (Stack) là cấu trúc dữ liệu trong đó phần tử nào được đưa vào sau cũng sẽ được lấy ra trước. Hàng đợi (Queue) là cấu trúc dữ liệu trong đó phần từ nào được đưa vào trước sẽ được lấy ra trước. Tưởng tượng ngăn xếp giống như một chồng sách; cuốn sách trên đầu của chồng sách là cuốn sách được đưa vào cuối cùng, khi bạn lấy một cuốn sách ra khỏi chồng thì bạn nên lấy cuốn ở trên cùng. Hàng đợi thì giống như khi bạn xếp hàng trong siêu thị; ai xếp hàng trước sẽ được thanh toán (đi ra khỏi hàng đợi) trước. Đó là tất cả những gì bạn cần biết về ngăn xếp và hàng đợi.

Figure 1: (a) Minh hoạ ngăn xếp. Các phần tử được đưa vào (push) đỉnh ngăn xếp và cũng được lấy ra (pop) từ đỉnh của ngăn xếp. (b) Minh họa hàng đợi. Các phần tử được đưa vào (enqueue) cuối hàng đợi và cũng được lấy ra (dequeue) từ đầu của hàng đợi.

Thực thi ngăn xếp có hai cách: sử dụng mảng hoặc sử dụng danh sách liên kết. Nếu thực hiện bằng mảng, kí hiệu là $A$, ta cần một biến, kí hiệu là $top$, để xác định phần tử đầu tiên của ngăn xếp. Phần tử $A[top]$ chính là phần tử trên cùng của ngăn xếp (phần tử được đưa vào ngăn xếp gần đây nhất). Mỗi khi chèn vào ngăn xếp dữ liệu $x$, ta thực hiện hai bước:

1. Tăng $top$ lên $1$, i.e, gán $top \leftarrow top +1 $.
2. Gán $A[top] \leftarrow x$.

Khi lấy phần tử ra khỏi ngăn xếp, ta sẽ copy dữ liệu từ $A[top]$ ra một biến $y$, giảm $top$ 1 đơn vị và trả lại giá trị của biến $y$. Nếu thực hiện ngăn xếp bằng DSLK, mỗi khi thêm vào ngăn xếp, ta luôn chèn vào đầu của DSLK (bài DSLK chúng ta đã có nhận xét là chèn vào đầu DSLK luôn hiệu quả và sạch sẽ hơn chèn vào đuôi). Khi lấy dữ liệu ra khỏi ngăn xếp, ta lấy dữ liệu ra từ mắt xích đầu tiên của DSLK.

Thực thi hàng đợi, ta cũng có hai cách tương tự như ngăn xếp, chỉ có thứ tự lấy ra và đưa vào là khác. Khi đưa vào hàng đợi, bạn nên đưa vào đuôi của DSLK và lấy ra từ đầu của DSLK nếu cấu trúc bạn sử dụng là DSLK đơn (tại sao không làm ngược lại?). Nếu bạn sử dụng DSLK đôi thì bạn có thể làm ngược lại, lấy ra từ đuôi và chèn vào đầu của DSLK.

Do thực thi ngăn xếp và hàng đợi có nhiều điểm tương tự nhau, từ đây trở đi mình chỉ nói về thực thi ngăn xếp. Trong hai cách thực thi trên, mỗi cách đều có một điểm yếu riêng. Trong phương pháp thực thi bằng mảng, ta cần phải biết trước lượng bộ nhớ tối đa của hàng đợi tại một thời điểm bất kì để khai báo và cấp phát bộ nhớ cho mảng. Trong một số trường hợp, ví dụ BFS trong duyệt đồ thị, ta có thể ước lượng được lượng bộ nhớ này một cách khá chính xác. Tuy nhiên, trong hầu hết các trường hợp khác, rất khó để biết trước. Cho dù biết trước lượng bộ nhớ tối đa này, không phải tại thời điểm nào ta cũng cần dùng hết lượng bộ nhớ khai báo. Điều này dẫn đến dư thừa bộ nhớ. Nếu thực thi bằng DSLK, ta có thể khắc phục dư thừa bộ nhớ, nhưng mỗi lần thêm một mắt xích mới ta lại phải thực hiện cấp phát bộ nhớ cho mắt xích đó. Các hàm cấp phát bộ nhớ (ví dụ hàm malloc trong C) nói chung đều liên quan đến một chuỗi các thủ tục khác để quản lí bộ nhớ. Do đó, mỗi lần cấp phát bộ nhớ như vậy cũng không hề rẻ.

Nếu coi cách thực thi mảng là một cách thực thi đổi bộ nhớ lấy tốc độ thì cấu trúc mảng mở rộng (extendable array) ta nói tới ở đây cũng có tính chất tương tự. Tuy nhiên, mảng mở rộng cho phép ta kiểm soát được lượng bộ nhớ hi sinh để đổi lại thời gian thực thi, do đó, nó phù hợp trong ứng dụng thực thi ngăn xếp (hàng đợi). Vector trong C++ chính là cấu trúc mảng mở rộng.

Remark: Mảng mở rộng còn được biết tới một cái tên khác là mảng động (dynamic array). Mình không thích từ "động" lắm nên dùng từ mở rộng. Cái tên chuẩn hơn có lẽ là mảng tự mở rộng hoặc mảng tự điều chính kích thước. Tất cả đều dài nên tạm thời dùng từ mảng mở rộng vậy. Bạn nào có tên hay thì comment xuống dưới giúp mình.

Mảng mở rộng

Về cơ bản, mảng mở rộng (extendable array) là một cấu trúc dựa trên mảng. Mảng này, gọi là $A$, ban đầu được cấp phát một lượng bộ nhớ nhỏ (10 phần tử chẳng hạn như trong ArrayList của Java). Để đơn giản, ta giả sử chỉ thực hiện chèn (vào cuối) mảng mở rộng. Thao tác xóa sẽ được bàn thêm ở phần dưới.

Mỗi lần chèn một phần tử vào cuối mảng (ta sẽ đề cập đến xóa sau), nếu mảng đã đầy thì ta:

1. Cấp phát một mảng mới $B$ có kích thước gấp $\alpha$ lần mảng hiện tại $A$. Ở đây $\alpha$ lớn hơn 1. Ta gọi $\alpha$ là hệ số mở rộng. Các ngôn ngữ khác nhau sẽ chọn hệ số $\alpha$ khác nhau. Ví dỵ Python là $\alpha = 1.125$, Facebook folly là $\alpha = 1.5$ (xem thêm tại wikipedia).
2. Copy toàn bộ mảng $A$ sang mảng $B$.
3. Xóa mảng $A$ để giải phóng bộ nhớ.

Ba thao tác trên có vẻ rất tốn kém (và thực sự là nó tốn kém) vì phải xóa toàn bộ mảng cũ và tạo một mảng mới. Điểm mấu chốt ở đây là ta sẽ không phải thường xuyên thực hiện ba thao tác trên vì ta chỉ thực hiện khi nào mảng đầy. Nhận xét, mỗi lần thực hiện ba thao tác trên, ta tăng bộ nhớ lên $\alpha$ lần. Do đó, nếu bộ nhớ hiện tại của mảng là $n$ thì tổng số lần thực hiện ba thao tác là $O(\log_\alpha(n))$. Mỗi lần thực hiện ba thao tác trên, ta trả thời gian $O(n)$ để khởi tạo và copy, do đó, tổng thời gian là $O(\log_\alpha(n)n)$. Phân tích kĩ hơn trình bày dưới đây cho thấy tổng thời gian phải trả vẫn chỉ là $O(n)$, hay nói cách khác, thời gian khấu trừ (armotized time) cho mỗi thao tác chèn là $O(1)$. Chú ý ở đây ta vân chưa xét phép xóa khỏi mảng.

Để thực thi các thao tác trên, ta cần thêm hai biến: (i) biến $cap$ lưu trữ dung lượng (capacity) của mảng hiện tại và (ii) biến $size$ để lưu số phần tử hiện tại lưu trữ trong mảng, hay lượng dữ liệu của mảng. Ta sẽ kí hiệu mảng mở rộng bằng bộ ba biến $(A, cap, size)$. Ban đầu khởi tạo mảng, ta cấp phát một mảng kích thước hằng số. Ở đây ta khởi tạo là $\lceil \alpha \rceil$ để dễ phân tích.

 
Ta có:

 
Chứng minh: Để trình bày được đơn giản, ta giả sử $\alpha$ nguyên. Dễ thấy, nếu bỏ qua thao tác mở rộng thì tổng thời gian chèn $n$ phần tử là $O(n)$. Ta chỉ cần đếm số thao tác xảy ra trong quá trình mở rộng. Gọi $k = \lfloor\log_\alpha n \rfloor$. Do ta chỉ thực hiện mở rộng mảng mỗi khi số phần tử của mảng là $\alpha^i$ với $i \leq k$, và mỗi lần mở rộng, ta mất thời gian là kích thước của mảng, i.e, thời gian $O(\alpha^i)$. Ta có tổng thời gian mở rộng mảng là:

$T(n) = \sum_{i=1}^{k} O(\alpha^i) = O(\frac{\alpha^{k+1}-1}{\alpha -1} - 1 )= O(\frac{\alpha}{\alpha-1}n) \qquad (1)$

Từ (1), ta suy ra tổng thời gian chèn là $O(\frac{\alpha}{\alpha-1}n) + O(n) = O(\frac{\alpha}{\alpha-1}n)$

Bằng một chút phân tích nhỏ (coi như bài tập cho bạn đọc), ta thấy lượng bộ nhớ dư thừa là tối đa là $(\alpha -1)n$. Theorem 1 cho ta thấy rõ: nếu ta cần tiết kiệm bộ nhớ ($\alpha$ càng gần 1), thì ta cần phải trả nhiều thời gian cho mỗi thao tác chèn và ngược lại, ta càng cấp phát nhiều bộ nhớ sau mỗi lần bị đầy ($\alpha$ lớn) thì khả năng dư thừa bộ nhớ càng cao, nhưng thời gian mỗi thao tác chèn lại càng nhỏ.

Xóa ở cuối mảng mở rộng

Điểm chính ở đây là ta muốn thu hồi phần bộ nhớ dư thừa sau khi xóa (rất nhiều) phần tử khỏi mảng, để đảm bảo dung lượng của mảng không quá lớn so với lượng dữ liệu lưu trữ trong mảng, i.e, $cap = O(size)$. Nếu ta không nhất thiết phải thu hồi bộ nhớ thì chỉ việc xóa khỏi mảng bình thường.

Ta muốn đảm bảo, ngoài việc cho phép thu hồi bộ nhớ, trung bình mỗi thao tác xóa và chèn có thời gian $O(1)$. Xét ý tưởng sau mở rộng từ ý tưởng ở trên: Giả sử hiện tại dung lượng của mảng là $cap = \alpha^k$. Nếu khi ta xóa một phần tử khỏi mảng, số phần tử trong mảng còn lại là $size = \alpha^{k-1}$, ta sẽ "co" bộ nhớ của mảng về $\alpha^{k-1}$ bằng cách tương tự như khi chèn: (i) cấp phát mảng mới kích thước $\alpha^{k-1}$, (ii) copy toàn bộ $A$ sang mảng mới, và (iii) giải phóng bộ nhớ của $A$. Vấn đề của ý tưởng này ở chỗ nếu $cap = size = \alpha^{k-1}$ và nếu ta cứ thêm một phần tử mới, sau đó lại lấy ra, sau đó lại thêm mới. Thao tác thêm và xóa xảy ra liên tiếp nhau, thì ta phải thực hiện thao tác mở rộng và co rất nhiều lần, mỗi lần có độ phức tạp $O(n)$.

Chúng ta sẽ đi lạc đề một chút: tìm hiểu một cách khác để chứng minh Theorem 1 vì cách này cho chúng ta ý tưởng để (phân tích và) giải quyết trường hợp xóa khỏi mảng. Khi số phần tử của mảng đạt ngưỡng $size = \alpha^k$, lần mở rộng gần nhất là khi $size = \alpha ^{k-1}$. Điều đó có nghĩa giữa hai lần mở rộng, ta đã chèn:

$\alpha^k - \alpha^{k-1} = (\alpha - 1)\alpha^{k-1} \qquad (2)$

vào mảng. Mở rộng mảng mất thời gian $O(\alpha^k)$, do đó, chia trung bình cho các phần tử vừa chèn vào giữa hai lần mở rộng liên tiếp, ta có:

$\frac{O(\alpha^k)}{(\alpha - 1)\alpha^{k-1}} = O(\frac{\alpha}{\alpha -1}) \qquad (3)$

Phân tích trên có điểm hay là ta chỉ cần nhìn vào các phần tử giữa hai lần mở rộng liên tiếp để phân tích mà không cần quan tâm đến toàn bộ mảng hiện tại. Nhận xét này cho ta cách giải quyết xóa vào cuối mảng như sau: ta chỉ giải phóng bộ nhớ khi $\frac{cap}{size} = \alpha^2$ (thay vì $\frac{cap}{size} = \alpha$ như ý tưởng trên). Nếu xóa một phần tử khỏi mảng mà số dữ liệu còn lại trong mảng $size = \alpha^{k-2}$, ta sẽ: (i) cấp phát mảng mới kích thước $\alpha^{k-1}$ (chú ý $k-1$ ở đây), (ii) copy toàn bộ $A$ sang mảng mới, và (iii) giải phóng bộ nhớ của $A$. Như vậy, lượng bộ nhớ dư thừa tối đa là $(\alpha^2 - 1)n$.

 
Chứng minh: Gọi $m$ là số thao tác xóa trước khi ta thực hiện co mảng. Theo cách mở rộng mảng, ta chỉ mở rộng mảng đến dung lượng $cap$ khi và chỉ khi dữ liệu trong mảng có kích thước $size \geq \frac{cap}{\alpha}$.
Do ta chỉ co mảng khi $size = cap/\alpha^2 $, ta phải xóa ít nhất:

$cap(\frac{1}{\alpha} - \frac{1}{\alpha^2}) = cap\frac{\alpha -1}{\alpha^2} \qquad (4)$

phần tử ra khỏi mảng. Phép co mất thời gian $O(size) = O( cap/\alpha^2)$, do đó, trung bình mỗi thao tác xóa mất tối đa:

$O(\frac{\alpha^2}{(\alpha -1)\alpha^2}) = O(\frac{1}{\alpha -1}) \qquad (5)$

Remark Phần bộ nhớ dư thừa trong cấu trúc mảng mở rộng trình bày ở trên là $O(n)$. Về mặt lí thuyết, ta có thể giảm phần bộ nhớ dư thừa này xuống còn $O(\sqrt{n})$ [2]. Mình khuyến khích bạn đọc đọc thêm tại [2].

Tham khảo

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2001) [1990]. 17.4 Dynamic tables. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.
[2] A. Brodnik, S. Carlsson, R. Sedgewick, J. Munro, E. D. Demaine (1999). Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo.