tailieunhanh - CHƯƠNG 6: NGĂN XẾP

Trong chương này, chúng ta sẽ trình bày KDLTT ngăn xếp. Cũng giống như danh sách, ngăn xếp là CTDL tuyến tính, nó gồm các đối tượng dữ liệu được sắp thứ tự. Nhưng đối với danh sách, các phép toán xen, loại và truy cập có thể thực hiện ở vị trí bất kỳ của danh sách, còn đối với ngăn xếp các phép toán đó chỉ được thực hiện ở một đầu. Mặc dù các phép toán trên ngăn xếp là rất đơn giản, song ngăn xếp là một trong các CTDL quan trọng nhất. . | Ý tưởng của thuật toán chuyển biểu thức infix thành biểu thức postfix là như sau: Chúng ta xem biểu thức infix như dãy các thành phần (mỗi thành phần ( mỗi thành phần là toán hạng hoặc ký hiệu phép toán hoặc dấu mở ngoặc hoặc dấu đóng ngoặc). Thuật toán có đầu vào là biểu thức infix đã cho và đầu ra là biểu thức postfix. Chúng ta đã sử dụng một ngăn xếp S để lưu các phép toán và dấu mở ngoặc. Đọc lần lượt từng thành phần của biểu thức infix từ trái sang phải, cứ mỗi lần gặp toán hạng, chúng ta viết nó vào biểu thức postfix. Khi đọc tới một phép toán (phép toán hiện thời), chúng ta xét các phép toán ở đỉnh ngăn xếp. Nếu các phép toán ở đỉnh ngăn xếp có quyền ưu tiên cao hơn hoặc bằng phép toán hiện thời, thì chúng được kéo ra khỏi ngăn xếp và được viết vào biểu thức postfix. Khi mà phép toán ở đỉnh ngăn xếp có quyền ưu tiên thấp hơn phép toán hiện thời, thì phép toán hiện thời được đẩy vào ngăn xếp. Bởi vì các phép toán trong cặp dấu ngoặc cần được thực hiện trước tiên, do đó chúng ta xem dấu mở ngoặc như phép toán có quyền ưu tiên cao hơn mọi phép toán khác. Vì vậy, mỗi khi gặp dấu mở ngoặc thì nó được đẩy vào ngăn xếp, và nó chỉ bị loại khỏi ngăn xếp khi ta đọc tới dấu đóng ngoặc tương ứng và tất cả các phép toán trong cặp dấu ngoặc đó đã được viết vào biểu thức postfix.