CHỒNG (STACK) VÀ HÀNG ĐỢI (QUEUE)
Trong các thuật toán trên đồ thị ta thường tổ chức các dữ liệu thành các danh sách và xử lý các phần tử của danh sách theo một cách nào đó:
Danh sách FIFO(Queue):
Danh sách này được tổ chức theo kiểu phần tử nào vào trước được xử lý trước. Khi đó một cách đơn giản nhất là dùng một mảng một chiều A với kích thước có thể chứa mọi phần tử có thể có và hai biến first và last để ghinhận chỉ số của phần tử đầu tiên và chỉ số của phần tử cuối cùng. Các thao tác trên danh sách FIFO như sau
[code]
+Bước khởi tạo: Đầu tiên A rỗng nên first=last=0
+Kết nạp một phần tử v vào A: A[first]=v; first=last=1;
+Kết nạp một phần tử v vào cuối danh sách, kí hiệu A<=v
A <= v <=>last:=last+1;A[last]:=u;
+Đưa một phần tử ra khỏi danh sách, kí hiệu u<=A
u<=A<=>first:=first+1;
Danh sách LIFO(Stack):
Danh sách này được tổ chức theo kiểu phần tử nào vào sau được xử lý trước. Khi đó một cách đơn giản nhất để xử lý danhsách này là dùng một mảng A với kích thước đủ để chứa mọi phần tử có thể có và biến last để ghi nhận phần tử cuối cùng.
Code:
+Bước khởi tạo: Đầu tiên A rỗng tức là last=0
+Kết nạp v vào A <=> last=1;A[last]=v;
+Kết nạp u vào danh sách, kí hiệu A<=u <=> last:=last+1;A[last]:=u;
+Đưa một phần tử ra khỏi danh sách, kí hiệu A=>u
u<=A<=>last:=last-1;