Trong bài trước, chúng ta đã sử dụng kiểu dữ liệu hàng đợi và ngăn xếp. Trong nhiều trường hợp ứng dụng trong thực tế chúng ta phải kết hợp cả hai loại dữ liệu này...

Ví dụ thực tế cần sử dụng cả kiểu dữ liệu hàng đợi (queue) và ngăn xếp (stack) là trong việc thực hiện kiểm tra biểu thức số học (arithmetic expression) để xem liệu biểu thức có được viết đúng (well-formed) hay không, đặc biệt là kiểm tra tính đúng đắn của dấu ngoặc.

Ví dụ: Kiểm tra tính đúng đắn của dấu ngoặc trong biểu thức

Giả sử có một biểu thức toán học và bạn muốn kiểm tra xem tất cả các dấu ngoặc mở đều có dấu ngoặc đóng tương ứng và được đặt đúng thứ tự. Để làm điều này, bạn có thể sử dụng ngăn xếp và hàng đợi như sau:

1. Ngăn xếp (Stack): Dùng để theo dõi các dấu ngoặc mở.
2. Hàng đợi (Queue): Dùng để lưu trữ biểu thức đã phân tích và kiểm tra trong trường hợp bạn cần lưu trữ và xử lý lại sau khi kiểm tra dấu ngoặc.

Cách thực hiện

1. Duyệt qua từng ký tự trong biểu thức:
   • Nếu gặp dấu ngoặc mở ((, [, {), đưa vào ngăn xếp.
   • Nếu gặp dấu ngoặc đóng (), ], }), kiểm tra ngăn xếp để đảm bảo dấu ngoặc đóng tương ứng với dấu ngoặc mở tương ứng. Nếu đúng, loại bỏ dấu ngoặc mở khỏi ngăn xếp.
2. Sau khi duyệt qua tất cả các ký tự:
   • Nếu ngăn xếp trống, biểu thức có dấu ngoặc đúng.
   • Nếu ngăn xếp không trống, biểu thức có dấu ngoặc không đúng.