Ngăn xếp và hàng đợi
Ngăn xếp và hàng đợi
Hai cấu trúc chỉ khác nhau đúng một chỗ: lấy phần tử ra từ đầu nào. Cùng một dãy vào, chúng cho hai thứ tự ra không giống nhau chút nào. Và hàng đợi vòng là nơi lỗi lệch một đơn vị hay xảy ra nhất trong cả môn này.
Mảng động ở bài trước cho bạn thêm và đọc ở bất kỳ chỗ nào. Nhiều bài toán lại không cần tự do đến vậy, và khi bạn tự nguyện bỏ bớt tự do thì đổi lại được thứ khác: cấu trúc đơn giản hơn, ít chỗ sai hơn, và thường là nhanh hơn.
Ngăn xếp chỉ cho bạn động vào một đầu: đẩy vào ở đó, lấy ra cũng ở đó. Phần tử vào sau cùng là phần tử ra trước tiên. Hàng đợi thì đẩy vào ở một đầu và lấy ra ở đầu kia, nên phần tử vào trước sẽ ra trước. Chỉ khác nhau đúng chỗ đó thôi, và đó đã đủ để chúng dùng cho hai loại việc hoàn toàn khác nhau.
Cách chắc chắn nhất để thấy sự khác nhau ấy là cho cùng một dãy thao tác chạy trên cả hai rồi nhìn hai dòng kết quả. Sim dưới đây làm đúng vậy, và mọi thứ đều sửa được: dãy thao tác, số ô của mảng, và cách hàng đợi phân biệt rỗng với đầy.
1 · Một dãy thao tác, hai thứ tự đi ra ✎ sửa được
- nghĩa là lấy ra một phần tử. Ví dụ A B - C - là đẩy A, đẩy B, lấy ra, đẩy C, lấy ra.C còn hàng đợi trả về A. Cùng một dãy vào, cùng một mảng, chỉ khác chỗ lấy ra từ đầu nào.2 · Hàng đợi vòng: hai chỉ số cuốn quanh mảng ✎ nhấp bảng để xem từng bước
Mảng có 6 ô cố định. Chỉ số đầu trỏ vào phần tử cũ nhất, chỉ số cuối trỏ vào ô trống sắp ghi. Cả hai chỉ tiến tới, và khi chạm hết mảng thì quay về ô 0 nhờ phép chia lấy dư. Nhờ vậy hàng đợi phục vụ được số phần tử tuỳ ý mà không phải dời gì cả, khác hẳn cách xoá phần tử đầu rồi dồn cả mảng lên một ô.
- giữ một ô trống: rỗng khi đầu bằng cuối, đầy khi cuối tiến một bước nữa thì đụng đầu. Cái giá: mất đứt một ô, sức chứa thật chỉ còn m - 1. Với 6 ô thì cách này chứa được 5 phần tử.
- giữ thêm biến đếm: rỗng khi biến đếm bằng 0, đầy khi biến đếm bằng số ô. Cái giá: dùng đủ m ô, đổi lại phải cập nhật thêm một biến ở mọi thao tác. Với 6 ô thì cách này chứa được 6 phần tử.
| # | thao tác | ngăn xếp | hàng đợi vòng | ||||||
|---|---|---|---|---|---|---|---|---|---|
| kết cục | ra | cỡ | kết cục | ra | đầu | cuối | cỡ | ||
| 1 | đẩy vào A | ✓ xong | · | 1 | ✓ xong | · | 0 | 1 | 1 |
| 2 | đẩy vào B | ✓ xong | · | 2 | ✓ xong | · | 0 | 2 | 2 |
| 3 | đẩy vào C | ✓ xong | · | 3 | ✓ xong | · | 0 | 3 | 3 |
| 4 | lấy ra | ✓ xong | C | 2 | ✓ xong | A | 1 | 3 | 2 |
| 5 | đẩy vào D | ✓ xong | · | 3 | ✓ xong | · | 1 | 4 | 3 |
| 6 | đẩy vào E | ✓ xong | · | 4 | ✓ xong | · | 1 | 5 | 4 |
| 7 | lấy ra | ✓ xong | E | 3 | ✓ xong | B | 2 | 5 | 3 |
| 8 | đẩy vào F | ✓ xong | · | 4 | ✓ xong | · | 2 | 0 | 4 |
| 9 | đẩy vào G | ✓ xong | · | 5 | ✓ xong | · | 2 | 1 | 5 ● |
| 10 | đẩy vào H | ✓ xong | · | 6 | ⚠ tràn | · | 2 | 1 | 5 ● |
| 11 | lấy ra | ✓ xong | H | 5 | ✓ xong | C | 3 | 1 | 4 |
| 12 | lấy ra | ✓ xong | G | 4 | ✓ xong | D | 4 | 1 | 3 |
3 · Ứng dụng thật: kiểm dấu ngoặc cân đối ✎ sửa được
Gặp một dấu mở thì đẩy vào ngăn xếp, gặp một dấu đóng thì lấy ra và so xem có đúng loại không. Cột dưới đây là độ cao của ngăn xếp sau từng ký tự: nó lên khi lồng sâu thêm, xuống khi đóng lại, và phải về đúng 0 khi hết chuỗi.
- Nó đếm thao tác, ô nhớ và độ sâu. Nó không đo thời gian. Ở đây cả hai cấu trúc phục vụ mọi thao tác trong một số bước cố định, nên sim không hề nói cấu trúc nào chạy nhanh hơn trong một chương trình thật.
- Ngăn xếp và hàng đợi ở đây nằm trong mảng cố định, nên chúng tràn được.
ArrayDequecủa Java haystd::queuecủa C++ thì tự lớn lên khi hết chỗ, tức là chúng đổi lỗi tràn lấy một lần cấp phát và chép, đúng như bài mảng động. Đừng đọc con số tràn ở đây thành lời khẳng định về thư viện thật. - Chỗ báo lỗi ngoặc kiểu thiếu dấu đóng là một quy ước: sim chỉ ra dấu mở trong cùng còn chờ. Chỉ ra dấu mở ngoài cùng cũng hợp lý không kém, và trình biên dịch thật thường in cả hai. Sim vẫn giữ đủ danh sách vị trí còn chờ nên bạn tự đối chiếu được.
- Bộ kiểm ngoặc này không phân tích cú pháp. Nó không biết dấu ngoặc nằm trong chuỗi ký tự hay trong lời chú thích, nên với mã nguồn thật nó sẽ báo nhầm ở những chỗ đó.
Cùng một dãy, hai thứ tự đi ra
Dãy mở bài có 12 thao tác: 8 lần đẩy vào và 4 lần lấy ra, viết gọn thành A B C - D E - F G H - -. Mảng có 6 ô.
Ngăn xếp trả về C → E → H → G. Hàng đợi trả về A → B → C → D. Hai dòng lệch nhau ngay từ phần tử ra đầu tiên: lần lấy ra thứ nhất rơi vào lúc trong ruột đang có A, B, C, và ngăn xếp đưa cho bạn cái mới nhất là C còn hàng đợi đưa cái cũ nhất là A.
Đây là chỗ đáng dừng lại: không có cấu trúc nào đúng hơn cấu trúc nào. Nếu bạn đang lần ngược một mê cung và muốn quay lại ngã rẽ gần nhất thì ngăn xếp mới đúng, và đó chính là tìm kiếm theo chiều sâu. Nếu bạn muốn xét các ô theo đúng thứ tự gặp được, tức loang đều ra mọi hướng, thì phải là hàng đợi, và đó là tìm kiếm theo chiều rộng. Đổi cấu trúc là đổi luôn thuật toán, dù mã nguồn gần như giống hệt.
Có lúc hai thứ tự trùng nhau. Bấm preset chạy vòng nhiều lượt rồi nhìn: cả hai đều ra A → B → C → D → E → F → G. Không phải trùng hợp, mà vì dãy đó đẩy một cái rồi lấy ngay một cái, nên chưa lần nào lấy ra lúc trong ruột có quá một phần tử, mà với đúng một phần tử thì hai luật lấy ra là một. Quét toàn bộ 2.047 hình dạng dãy dài tới 10 thao tác thì có 1.451 dãy cho hai thứ tự khác nhau và 596 dãy cho cùng thứ tự, và mọi dãy trùng nhau đều thuộc đúng loại vừa nói.
Ngăn xếp: một chỉ số là đủ
Ngăn xếp trong mảng chỉ cần đúng một biến, tạm gọi là đỉnh, trỏ vào ô trống đầu tiên. Đẩy vào là ghi vào ô đó rồi tăng đỉnh lên một; lấy ra là giảm đỉnh xuống một rồi đọc. Vì thế đỉnh cũng chính là số ô đang dùng, và mảng 6 ô chứa được đủ 6 phần tử, không phí ô nào.
Ở dãy mở bài, ngăn xếp có lúc sâu tới 6 tầng, tức chạm đúng trần mảng mà chưa tràn. Hết dãy thì nó còn giữ A, B, D, F từ đáy lên, tức 4 ô đang dùng.
Cái ngăn xếp nổi tiếng nhất bạn dùng hằng ngày mà không tự viết dòng nào: ngăn xếp gọi hàm của máy. Mỗi lần chương trình gọi một hàm, máy đẩy vào đó một khung chứa tham số, biến cục bộ và chỗ cần quay về; hàm kết thúc thì khung ấy bị lấy ra. Vì nó là ngăn xếp nên hàm luôn quay về đúng chỗ đã gọi nó gần nhất. Và vì nó nằm trong một vùng nhớ có giới hạn nên nó tràn được: đệ quy không có điều kiện dừng sẽ đẩy khung vào mãi cho tới lúc hết chỗ, và lỗi báo ra đúng tên gọi của chuyện vừa xảy ra. Bài đệ quy nói kỹ chỗ đó.
Hàng đợi vòng: vì sao phải cuốn quanh
Hàng đợi khó hơn ngăn xếp một bậc, vì nó động vào hai đầu. Cách ngây thơ là để đầu hàng luôn ở ô 0: lấy ra thì đọc ô 0 rồi dồn cả mảng lên một ô. Cách đó chạy đúng nhưng mỗi lần lấy ra phải chép cả mảng, nên phục vụ n phần tử tốn chừng n² phép. Với một hàng đợi mà cả chương trình dùng chung thì đó là một tai hoạ.
Cách đúng là để cả hai chỉ số cùng chạy. Chỉ số đầu trỏ phần tử cũ nhất, chỉ số cuối trỏ ô trống sắp ghi. Cả hai chỉ tiến tới, không lùi, và khi chạm hết mảng thì quay về ô 0 nhờ phép chia lấy dư. Mảng không còn là một đoạn thẳng nữa mà là một vòng tròn, đúng như hình sim vẽ.
Ở dãy mở bài, bạn thấy chuyện đó xảy ra ở thao tác thứ 8: F được ghi vào ô 5, tức ô cuối mảng, rồi chỉ số cuối cuốn từ 5 về 0. Thao tác thứ 9 ghi G vào chính ô 0 đó, ô mà A từng ở và đã trả lại từ lâu. Hết dãy thì đầu dừng ở ô 4, cuối dừng ở ô 1, và ba phần tử còn lại là E, F, G nằm vắt qua chỗ nối của mảng.
Bấm preset chạy vòng nhiều lượt để thấy hết sức mạnh của cách này: mảng chỉ 4 ô mà phục vụ trọn 7 phần tử, không tràn lần nào, không dời một ô nhớ nào, chỉ số cuối cuốn vòng 1 lần và chỉ số đầu cũng cuốn 1 lần. Lúc đông nhất trong ruột vẫn chỉ có 1 phần tử. Đây chính là hình dáng của một hàng đợi thật: dòng người đi qua thì dài vô kể, còn chỗ ngồi thì có bấy nhiêu.
Đầu bằng cuối: rỗng hay đầy?
Và đây là câu hỏi làm hỏng nhiều bài thi lẫn nhiều đoạn mã thật.
Khi hàng đợi rỗng trơn, đầu đuổi kịp cuối, nên đầu == cuối. Khi hàng đợi đầy khít, cuối cuốn hết một vòng và cũng đuổi kịp đầu, nên lại đầu == cuối. Hai trạng thái ngược hẳn nhau mà cho ra đúng một cặp chỉ số như nhau. Nhìn riêng hai con số đó thì không tài nào phân biệt được, và nếu bạn viết if (dau == cuoi) return RONG; thì chương trình sẽ báo rỗng đúng vào lúc nó đầy nhất.
Bấm preset đầu bằng cuối: rỗng hay đầy? để nhìn tận mắt. Dãy A B C D E F - - - - - - chạy trên mảng 6 ô ở kiểu giữ biến đếm đưa hàng đợi qua đúng hai lần đầu == cuối: ở thao tác thứ 6 cả hai đều bằng 0 mà trong ruột có 6 phần tử, ở thao tác thứ 12 cả hai lại bằng 0 mà trong ruột không còn gì. Cùng một cặp (0, 0), hai nghĩa đối nghịch.
Có hai cách chữa, và cả hai đều phải trả giá.
Cách một: hy sinh một ô, không bao giờ dùng tới. Quy ước rỗng là đầu == cuối, còn đầy là (cuối + 1) % m == đầu, tức cuối chỉ được phép đuổi tới sát lưng đầu chứ không được chạm. Nhờ vậy đầu == cuối chỉ còn một nghĩa duy nhất. Cái giá rất cụ thể: sức chứa thật chỉ còn m - 1. Mảng 6 ô chứa được 5, mảng 8 ô chứa được 7, mảng 16 ô chứa được 15. Đúng một ô, không hơn không kém, ở mọi kích thước.
Cách hai: giữ thêm một biến đếm. Rỗng là đếm == 0, đầy là đếm == m. Dùng được cả m ô. Cái giá là mỗi lần đẩy vào và lấy ra đều phải cập nhật thêm một biến, và giờ có ba thứ phải giữ cho nhất quán thay vì hai.
Con số m - 1 không phải chuyện học thuộc, nó đo được. Ở dãy mở bài, mảng 6 ô đang chạy kiểu giữ một ô trống, nên hàng đợi chỉ chứa được 5. Đến thao tác thứ 9 nó đã báo đầy trong khi mới có 5 phần tử và mắt bạn còn thấy rõ một ô trống trên hình. Thao tác thứ 10 muốn đẩy H vào thì tràn, và H bị từ chối. Cũng chính H đó lại vào được ngăn xếp một cách nhẹ nhàng, vì ngăn xếp dùng đủ 6 ô. Gạt núm sang giữ thêm biến đếm thì H vào được, số lần tràn về 0, và cuối dãy hàng đợi giữ 4 ô thay vì 3.
Ở kiểu giữ một ô trống, hàng sim ghi hiệu hai chỉ số, lấy dư cho m luôn bằng đúng số phần tử đang có, nên kiểu này thật sự không cần biến đếm nào. Ở kiểu giữ biến đếm thì hai con số đó tách nhau đúng một lần: khi đầy khít, hiệu hai chỉ số đọc ra 0 còn số phần tử thật là 6. Lý do rất đơn giản khi viết ra: hiệu hai chỉ số là số phần tử lấy dư cho m, mà 0 và m chia cho m thì dư như nhau.
Tràn và rỗng phải được báo, không được im lặng
Hai mốc biên còn lại cũng phải làm cho đúng, và chúng dễ làm sai theo kiểu nguy hiểm hơn nhiều vì chương trình vẫn chạy.
Đẩy vào một hàng đợi đã đầy phải báo tràn và không đổi gì cả. Cài sai kiểu phổ biến nhất là cứ ghi đè lên ô mà cuối đang trỏ tới, thế là phần tử cũ nhất biến mất không dấu vết, số đếm vẫn đẹp, và lỗi chỉ lộ ra rất lâu sau đó ở một chỗ chẳng liên quan. Bấm preset đổ đầy rồi đẩy thêm: mảng 4 ô, sức chứa thật 3, phần tử thứ tư báo tràn, và ba phần tử cũ vẫn nằm nguyên chỗ cũ.
Lấy ra từ một hàng đợi rỗng phải báo, không được để chương trình đọc bừa một ô. Bấm preset lấy ra khi rỗng: dãy - - A - - báo rỗng 3 lần và chỉ có đúng 1 phần tử ra được, còn hai chỉ số thì đứng yên suốt cả hai lần đầu.
Cổng kiểm số của bài này khoá đúng các mốc ấy: với mọi số ô từ 2 tới 16 và cả hai kiểu, đổ đúng bằng sức chứa thì không tràn lần nào, thêm một phần tử nữa thì tràn đúng một lần, và mọi thao tác bị từ chối đều bị so từng ô nhớ với trạng thái trước đó để chắc rằng không có gì bị đụng vào.
Ứng dụng gọn nhất của ngăn xếp: dấu ngoặc cân đối
Thuật toán vỏn vẹn một câu: gặp dấu mở thì đẩy vào ngăn xếp, gặp dấu đóng thì lấy ra và so xem có đúng loại không; hết chuỗi mà ngăn xếp còn thừa thì thiếu dấu đóng.
Biểu thức mở bài if (x[0] < y) { z = (x[1] + 3; } dài 32 ký tự, trong đó có 9 ký tự ngoặc gồm 5 dấu mở và 4 dấu đóng. Ngăn xếp lên xuống theo đúng độ lồng, sâu nhất 3 tầng, rồi vỡ ở ký tự thứ 32: chỗ ấy là dấu } nhưng dấu mở gần nhất còn chờ lại là ( mở từ ký tự thứ 21. Điều đáng giá là thuật toán chỉ ra được cả hai vị trí, chứ không chỉ nói một câu chung chung là biểu thức sai.
Vì sao phải là ngăn xếp mà không phải một biến đếm? Bấm preset đếm thì cân, xếp thì hỏng. Chuỗi ([)] có đúng một dấu mở và một dấu đóng cho từng loại, nên mọi cách kiểm bằng đếm đều bảo nó cân đối. Ngăn xếp thì bắt lỗi ngay ở ký tự thứ 3, vì lúc gặp ) thì dấu mở đang chờ là [ ở ký tự thứ 2. Phép đếm không biết gì về thứ tự lồng nhau, còn ngăn xếp thì cấu trúc của nó chính là thứ tự đó.
Đây không phải một ca hiếm được dựng lên cho đẹp. Quét toàn bộ 55.987 chuỗi dài tới 6 ký tự viết bằng sáu ký tự ngoặc thì có 157 chuỗi thật sự cân đối, nhưng có tới 1.800 chuỗi mà phép đếm bảo cân trong khi ngăn xếp bảo hỏng. Nói cách khác, trong dải chuỗi ngắn ấy, cách đếm sai nhiều hơn số ca nó đúng hơn mười lần.
Ba kiểu hỏng có ba dáng khác nhau, và ba preset còn lại cho bạn xem từng kiểu: thừa dấu đóng lộ ngay giữa chừng khi một dấu đóng gặp ngăn xếp rỗng, sai loại dấu cũng lộ giữa chừng, còn thiếu dấu đóng thì phải đọc hết chuỗi mới biết. Với hai kiểu lộ giữa chừng, các ký tự phía sau được tô nhạt vì thuật toán dừng ngay chứ không đọc nốt.
Đếm cái gì, và không đếm cái gì
Sim đếm ba thứ, cả ba đều đếm lại được bằng mắt trên chính hình vẽ: số thao tác đã chạy, độ sâu lớn nhất của ngăn xếp, và số ô nhớ đang dùng. Con số cuối cùng đúng bằng số ô có giá trị trên hình, không phải một biến đếm riêng đi một đằng còn hình vẽ đi một nẻo.
Vài chỗ sim không nói được, cần rạch ròi:
- Nó không đo thời gian. Ở mô hình này cả hai cấu trúc phục vụ mọi thao tác trong một số bước cố định, nên không có gì ở đây kết luận được cấu trúc nào chạy nhanh hơn trong chương trình thật. Muốn biết thì phải đo, và bài hiệu năng tập hợp trong Java nói về việc đo đó.
- Ngăn xếp và hàng đợi ở đây nằm trong mảng cố định, nên chúng tràn được.
ArrayDequecủa Java haystd::queuecủa C++ thì tự lớn lên khi hết chỗ, tức chúng đổi lỗi tràn lấy một lần cấp phát và chép y như mảng động. Bài danh sách và hàng đợi trong Java nói về mấy lớp thư viện đó. Đừng đọc con số tràn ở đây thành lời khẳng định về thư viện thật. - Chỗ báo lỗi thiếu dấu đóng là một quy ước. Sim chỉ ra dấu mở trong cùng còn chờ; chỉ ra dấu mở ngoài cùng cũng hợp lý không kém, và trình biên dịch thật thường in cả hai. Sim vẫn giữ đủ danh sách vị trí còn chờ nên bạn tự đối chiếu được.
- Bộ kiểm ngoặc không phân tích cú pháp. Nó không biết dấu ngoặc nào nằm trong chuỗi ký tự hay trong lời chú thích, nên với mã nguồn thật nó sẽ báo nhầm ở những chỗ đó.
Ngăn xếp và hàng đợi chỉ khác nhau ở chỗ lấy phần tử ra từ đầu nào, và chừng đó là đủ để cùng một dãy vào cho hai thứ tự ra khác hẳn nhau: C → E → H → G so với A → B → C → D. Ngăn xếp cần đúng một chỉ số nên dùng hết cả mảng. Hàng đợi cần hai chỉ số cùng cuốn vòng, và ngay lập tức đụng câu hỏi đầu bằng cuối thì rỗng hay đầy. Hai cách chữa đều phải trả giá: giữ một ô trống thì sức chứa thật chỉ còn m - 1, giữ thêm biến đếm thì dùng đủ m ô nhưng phải cập nhật thêm một biến ở mọi thao tác. Và dù chọn cách nào, đẩy vào lúc đầy phải báo tràn chứ không ghi đè, lấy ra lúc rỗng phải báo chứ không đọc bừa: hai mốc biên ấy mới là chỗ giết người, không phải phần thuật toán.
- 1Một hàng đợi vòng cài bằng mảng 8 ô, dùng cách giữ một ô trống để phân biệt rỗng với đầy. Bạn đẩy vào liên tiếp 8 phần tử. Chuyện gì xảy ra?
- 2Bạn đọc mã của một hàng đợi vòng cài bằng mảng 6 ô và thấy trạng thái đầu bằng 3, cuối cũng bằng 3. Hàng đợi này đang rỗng hay đang đầy?
- 3Một bạn kiểm dấu ngoặc bằng cách đếm: đếm số dấu mở và số dấu đóng của từng loại, bằng nhau thì kết luận cân đối. Cách này hỏng ở đâu?