Bài giảng Cấu trúc dữ liệu và giải thuật: Úng dụng của DSLK: Queue

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ứng dụng của DSLK: Queue Mô tả queue Một queue là một cấu trúc dữ liệu mà việc thêm vào được thực hiện ở một đầu (rear) và việc lấy ra được thực hiện ở đầu còn lại (front) Phần tử vào trước sẽ ra trước – FIFO (First In First Out) Ví dụ về Queue Sau khi thêm A,B, C,D Lấy ra 1 phần tử: Thêm vào 1 phần tử E Ban đầu hàng đợi rỗng Một số phép toán trên hàng đợi void CreateEmpty(QueueType &Q): tạo hàng đợi rỗng int EmptyQueue(QueueType Q): Kiểm tra hàng đợi có rỗng hay không? int FullQueue(QueueType Q): Kiểm tra hàng đợi Q đầy hay không? (trường hợp hàng đợi được tạo bằng mảng) void EnQueue(QueueType &Q,DataType x): Đưa phần tử x vào hàng đợi Q. int DeQueue(QueueType &Q,DataType &x): Lấy phần tử đầu của hàng đợi gán cho x nếu hàng đợi không rỗng. int FrontQueue(QueueType S,DataType &x): Lấy giá trị phần tử đầu của hàng đợi gán cho x để xem nếu hàng đợi không rỗng. Cài đặt hàng đợi bằng DSLK typedef …. DataType; struct Node { DataType Data; Node *Next; }; typedef Node *NodePtr; struct QueueType { NodePtr Head,Tail; }; Cài đặt hàng đợi bằng DSLK void CreateEmpty(QueueType &Q) { Q.Head=Q.Tail=NULL; } int EmptyQueue(QueueType S) { return (Q.Head==NULL); } Cài đặt hàng đợi bằng DSLK Thêm một phần tử vào Queue Cài đặt hàng đợi bằng DSLK void EnQueue(QueueType &Q,DataType x) {NodePtr temp; temp=new Node; if(temp==NULL) { coutData,x);//Gán x cho vùng Data của Temp temp->Next=NULL; if(EmptyQueue(Q)) {Q.Head=Q.Tail=temp;} else { Q.Tail->Next=temp; Q.Tail=temp; } } } Cài đặt hàng đợi bằng DSLK int DeQueue(QueueType &Q,DataType &x) {NodePtr temp; if(EmptyQueue(Q)) { coutNext; gán(x,temp->Data);//Gán vùng Data của temp cho delete(temp); return 1; } } Cài đặt ngăn xếp bằng DSLK int FrontQueue(QueueType &Q,DataType &x) { if(EmptyQueue(Q)) return 0; else { Gán(x,Q.Head->Data); return 1; } } Ứng dụng của Hàng đợi Cơ chế vùng đệm cho các thao tác xuất nhập ở máy tính Lưu các tiến trình chờ xử lý ở Hệ điều hành, trình biên dịch. Cơ chế bán vé, bến đỗ phi trường, …