- Dựa trên tính chất của các giải thuật, các ứng dụng của ngăn xếp có thể được chia làm bốn nhóm như sau: đảo ngược dữ liệu, phân tích biên dịch dữ liệu, trì hoãn công việc và các giải thuật quay lui. - Một điều đáng chú ý ở đây là khi xem xét các ứng dụng, chúng ta không bao giờ quan tâm đến cấu trúc chi tiết của ngăn xếp. - Chúng ta luôn sử dụng ngăn xếp như một cấu trúc dữ liệu trừu tượng với các chức năng mà chúng ta đã định nghĩa cho nó.. - Trong phần trình bày về ngăn xếp chúng ta đã được làm quen với một ví dụ xuất các phần tử theo thứ tự ngược với thứ tự nhập vào. - Ở đây chúng ta tiếp tục tham khảo thêm ứng dụng đổi một số thập phân sang một số nhị phân.. - Tuy nhiên các ký số được xuất ra sẽ là thứ tự ngược của kết quả mà chúng ta mong muốn. - Thực là dễ dàng nếu chúng ta sử dụng ngăn xếp để khắc phục điều này.. - Một điều dễ nhận thấy là nếu chúng ta dùng một mảng liên tục ( array trong C. - để chứa các số digit rồi tìm cách in theo thứ tự đảo lại, chúng ta sẽ phải tiêu tốn sức lực vào việc quản lý các biến chỉ số chạy trên mảng. - Việc tuân thủ lời khuyên này giúp chúng ta có thói quen tốt khi đụng phải những bài toán lớn hơn: chúng ta có thể tập trung vào giải quyết những vấn đề chính của bài toán.. - Trong việc kiểm tra cú pháp thì việc kiểm tra cấu trúc khối lồng nhau một cách hợp lệ là một trong những điều có thể được thực hiện dễ dàng nhờ ngăn xếp.. - Để kiểm tra tính hợp lệ của các cấu trúc khối lồng nhau, chúng ta cần kiểm tra các cặp dấu ngoặc như. - Lý do sử dụng ngăn xếp được giải thích như sau: theo thứ tự xuất hiện, một dấu ngoặc mở xuất hiện sau cần phải có dấu ngoặc đóng tương ứng xuất hiện trước. - Điều này rõ ràng liên quan đến nguyên tắc FILO của ngăn xếp. - Mỗi cấu trúc khối sẽ được chúng ta biết đến. - Khởi tạo ngăn xếp để chứa các ký số 0 và 1.. - khi bắt đầu gặp dấu ngoặc mở của nó, và chúng ta sẽ chờ cho đến khi nào gặp dấu ngoặc đóng tương ứng của nó thì xem như chúng ta đã duyệt qua cấu trúc đó. - Các dấu ngoặc mở mà chúng ta gặp, chúng ta sẽ lần lượt lưu vào ngăn xếp, nếu đoạn chương trình hợp lệ, thì chúng ta cứ yên tâm rằng các dấu ngoặc đóng tương ứng của chúng sẽ xuất hiện theo đúng thứ tự ngược lại. - Như vậy, mỗi khi gặp một dấu ngoặc đóng, việc cần làm là lấy từ ngăn xếp ra một dấu ngoặc mở và so trùng.. - Mỗi dấu ngoặc mở. - được xem như một dấu ngoặc chưa so trùng và được lưu vào ngăn xếp cho đến khi gặp một dấu ngoặc đóng. - Mỗi dấu ngoặc đóng cần phải so trùng được với dấu ngoặc mở vừa được lưu cuối cùng, và như vậy dấu ngoặc mở này sẽ được lấy ra khỏi ngăn xếp và bỏ đi. - Trường hợp dấu ngoặc đóng xuất hiện mà ngăn xếp rỗng là trường hợp văn bản bị lỗi thừa dấu ngoặc đóng (tính đến vị trí đang xét). - ngược lại, khi đọc hết đoạn văn bản, nếu ngăn xếp không rỗng thì do lỗi thừa dấu ngoặc mở.. - ...phần trong này dĩ nhiên không cần kiểm tra tính hợp lệ của các cặp dấu ngoặc. - Khi sử dụng ngăn xếp để đảo ngược dữ liệu, toàn bộ dữ liệu cần được duyệt xong, chúng ta mới bắt đầu lấy dữ liệu từ ngăn xếp. - Trong trường hợp dữ liệu cần được xử lý theo đúng thứ tự mà chúng xuất hiện, chúng ta sẽ dùng hàng đợi làm nơi lưu trữ dữ liệu. - Ngược lại, nếu thứ tự xử lý dữ liệu ngược với thứ tự mà chúng xuất hiện, chúng ta sẽ dùng ngăn xếp do nguyên tắc FILO của nó.. - Chúng ta sẽ xem xét ví dụ về cách tính trị của một biểu thức ở dạng Balan ngược (reverse Polish calculator- còn gọi là postfix). - Trong quá trình duyệt biểu thức, khi gặp các toán hạng chúng ta phải hoãn việc tính toán cho đến khi gặp toán tử tương ứng của chúng, do đó chúng sẽ được đẩy vào ngăn xếp. - Khi gặp toán tử, các toán hạng được lấy ra khỏi ngăn xếp, phép tính được thực hiện và kết quả lại được đẩy vào ngăn xếp (do kết quả này có thể lại là toán hạng của một phép tính khác mà toán tử của nó chưa xuất hiện). - Do phần tiếp theo đây chỉ chú trọng đến ý tưởng sử dụng ngăn xếp trong giải thuật, nên chương trình sẽ nhận biết các thành phần của biểu thức một cách dễ dàng thông qua việc cho phép người sử dụng lần lượt nhập chúng. - Trong chương trình, người sử dụng nhập dấu ? để báo trước sẽ nhập một toán hạng, toán hạng này sẽ được chương trình lưu vào ngăn xếp. - vào ngăn xếp. - dấu = yêu cầu hiển thị phần tử tại đỉnh ngăn xếp (nhưng không lấy ra khỏi ngăn xếp), đó là kết quả của một phép tính mới nhất vừa được thực hiện.. - a: đẩy a vào ngăn xếp;. - b: đẩy b vào ngăn xếp. - c: đẩy c vào ngăn xếp. - lấy c và b ra khỏi ngăn xếp, đẩy b-c vào ngăn xếp. - lấy 2 toán hạng từ ngăn xếp là trị (b-c) và a, tính a * (b-c), đưa kết quả vào ngăn xếp.. - d: đẩy d vào ngăn xếp.. - lấy 2 toán hạng từ ngăn xếp là d và trị (a * (b-c. - d, đưa kết quả vào ngăn xếp.. - Ngăn xếp stored_numbers làm thông số cho hàm do_command được khai báo là tham chiếu do nó cần phải thay đổi khi hàm được gọi.. - Chúng ta có độ ưu tiên từ cao xuống thấp theo thứ tự sau đây:. - Khi duyệt biểu thức infix từ trái sang phải, các toán hạng trong biểu thức infix đều được đưa ngay vào biểu thức postfix, các toán tử cần được hoãn lại nên được đưa vào ngăn xếp. - Do đó, từ biểu thức infix, trước khi một toán tử nào đó cần được đưa vào ngăn xếp thì phải lấy từ đỉnh ngăn xếp tất cả các toán tử có độ ưu tiên cao hơn nó để đặt vào biểu thức postfix trước. - Riêng trường hợp độ ưu tiên của toán tử đang cần đưa vào ngăn xếp bằng với độ ưu tiên của toán tử đang ở đỉnh ngăn xếp, thì toán tử ở đỉnh ngăn xếp cũng được lấy ra trước nếu các toán tử này là các toán tử kết hợp trái (Việc tính toán xử lý từ trái sang phải).. - Chúng ta quan sát ba ví dụ sau đây:. - Ví dụ 1, dấu + vẫn ở trong ngăn xếp, và dấu * được đẩy vào ngăn xếp.. - Ví dụ 2, dấu * được lấy ra khỏi ngăn xếp trước khi đưa dấu + vào.. - Ví dụ 3, dấu + được lấy ra khỏi ngăn xếp trước khi đưa dấu - vào.. - cần được lưu trong ngăn xếp cho đến khi gặp dấu đóng. - Chúng ta quy ước độ ưu tiên của dấu ngoặc mở thấp nhất là hợp lý. - Mọi toán tử xuất hiện sau dấu ngoặc mở đều không thể làm cho dấu này được lấy ra khỏi ngăn xếp, trừ khi dấu ngoặc đóng tương ứng được duyệt đến. - trong ngăn xếp đều được lấy ra để đưa vào biểu thức dạng postfix. - Do các dấu ngoặc không bao giờ xuất hiện trong biểu thức postfix, dấu. - được đặt vào ngăn xếp để chờ dấu. - Các toán tử. - Ngăn xếp còn được sử dụng trong các giải thuật quay lui nhằm lưu lại các thông tin đã từng duyệt qua để có thể quay ngược trở lại. - Chúng ta sẽ xem xét các ví dụ sau đây.. - Chúng ta có một nút bắt đầu và một nút gọi là đích đến. - Để đơn giản, chúng ta xét đồ thị không có chu trình và chỉ có duy nhất một đường đi từ nơi bắt đầu đến đích. - Nhìn hình vẽ chúng ta có thể nhận ra ngay đường đi này. - Chúng ta bắt đầu từ nút 1, sang nút 2 và nút 3. - Tại nút 3 có 2 ngã rẽ, giả sử chúng ta đi theo đường trên, đến nút 4 và nút 5. - Tại nút 5 chúng ta lại đi theo đường trên đến nút 6 và nút 7. - Đến đây chúng ta không còn đường đi tiếp và cũng chưa tìm được đích cần đến, chúng ta phải quay trở lại nút 5 để chọn lối đi khác.. - Tại nút 8 chúng ta lại phải quay lại nút 5 để đi sang nút 9. - Bằng cách này, từ nút 13, khi chúng ta tìm được nút 16 thì chúng ta không cần phải quay lui để thử với nút 17, 18 nữa. - Giải thuật của chúng ta cần lưu các nút để quay lại. - So sánh nút 3 và nút 5, chúng ta thấy rằng trên đường đi chúng ta gặp nút 3 trước, nhưng diểm quay về để thử trước lại là nút 5. - Do đó cấu trúc dữ liệu thích hợp chính là ngăn xếp với. - Ngoài ra nếu chúng ta lưu nút 3 và nút 5 thì có sự bất tiện ở chỗ là khi quay về, thông tin lấy từ ngăn xếp không cho chúng ta biết các nhánh nào đã được duyệt qua và các nhánh nào cần tiếp tục duyệt. - Do đó, tại nút 3, trước khi đi sang 4, chúng ta lưu nút 12, tại nút 5, trước khi đi sang 6 chúng ta lưu nút 8 và nút 9,…. - Với giải thuật trên chúng ta có thể tìm đến đích một cách dễ dàng. - Tuy nhiên, nếu bài toán yêu cầu in ra các nút trên đường đi từ nút bắt đầu đến đích thì chúng ta chưa làm được. - Như vậy chúng ta cũng cần phải lưu cả các nút trên đường mà chúng ta đã đi qua. - Những nút nằm trên những đoạn đường không dẫn đến đích sẽ được dỡ bỏ khỏi ngăn xếp khi chúng ta quay lui. - Ở đây chúng ta gặp phải một vấn đề cũng tương đối phổ biến trong một số bài toán khác, đó là những gì chúng ta bỏ vào ngăn xếp không có cùng mục đích. - Có hai nhóm thông tin khác nhau: một là các nút nằm trên đường đang đi qua, hai là các nút nằm trên các nhánh rẽ khác mà chúng ta sẽ lần lượt thử tiếp khi gặp thất bại trên con đường đang đi. - Trong những trường hợp như vậy, việc giải quyết rất là dễ dàng: chúng ta dùng cách đánh dấu để phân biệt từng trường hợp, khi lấy ra khỏi ngăn xếp, căn cứ vào cách đánh dấu này chúng ta sẽ biết phải xử lý như thế nào cho thích hợp (Việc duyệt cây theo thứ tự LRN trong chương 10 nếu dùng ngăn xếp cũng là một ví dụ). - Trong hình 14.1, ký tự B trong ngăn xếp cho biết đó là những nút dành cho việc quay lui (Backtracking) để thử với nhánh khác. - Vậy khi gặp điểm cuối của một con đường không dẫn đến đích, chúng ta dỡ bỏ khỏi ngăn xếp các nút cho đến khi gặp một nút có ký tự ‘B’, bỏ lại nút này vào ngăn xếp (không còn ký tự ‘B. - Cuối cùng khi gặp đích, con đường được tìm thấy chính là các nút đang lưu trong ngăn xếp mà không có ký tự. - Hình 14.1- Ví dụ và ngăn xếp minh họa quá trình backtracking.. - Trên đây là mã giả cho bài toán tìm đích, cấu trúc dữ liệu để chứa đồ thị chúng ta sẽ được tìm hiểu sau trong chương 13.. - loop (còn nhánh chưa đưa vào ngăn xếp. - còn lại vào ngăn xếp.. - Sinh viên có thể tham khảo ý tưởng được trình bày dưới đây để giải bài toán tám con hậu sử dụng ngăn xếp thay vì đệ quy.. - Với bàn cờ 64 ô, bài toán mã đi tuần yêu cầu chúng ta chỉ ra đường đi cho con mã bắt đầu từ một ô nào đó, lần lượt đi qua tất cả các ô, mà không có ô nào lập lại hơn một lần.. - Giải thuật quay lui rất gần với hướng suy nghĩ tự nhiên của chúng ta. - Trong các khả năng có thể, chúng ta thường chọn ngẫu nhiên một khả năng để đi. - Và với vị trí mới chúng ta cũng làm điều tương tự. - Mỗi ô đi qua chúng ta đánh dấu lại. - Trong quá trình thử này, nếu có lúc không còn khả năng lựa chọn nào khác vì các ô nằm trong khả năng đi tiếp đều đã được đánh dấu, chúng ta cần phải lùi lại để thử những khả năng khác. - Thay vì biểu diễn đường đi cho con mã trên bàn cờ (hình 14.2a), chúng ta vẽ lại các khả năng đi và thấy chúng không khác gì so với bài toán tìm đích (hình 14.2b). - Và như vậy, chúng ta thấy cách sử dụng ngăn xếp trong những bài toán dạng này hoàn toàn đơn giản và tương tự. - trí bắt đầu của con mã, khả năng có lời giải và có bao nhiêu lời giải chúng ta không xem xét ở đây. - Chúng ta chỉ quan tâm đến cách sử dụng ngăn xếp trong những bài toán tương tự
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt