Bài giảng Cấu trúc dữ liệu và giải thuật - Hàng đợi

Hàng đợiKhái niệmCác phép toánCài đặt bằng mảngCài đặt bằng con trỏ1Khái niệmHàng đợi là một danh sáchCác phép toán chèn, xoá phần tử được giới hạn ở các điểm cuối của danh sáchPhép toán chèn phần tử mới được thực hiện ở một điểm cuối - gọi là đuôi của hàng đợiPhép loại bỏ một phần tử được thực hiện ở đầu kia của hàng đợi - gọi là đầu của hàng đợi2Các phép toán cơ bảnKhởi tạo hàng đợi rỗngKiểm tra hàng đợi rỗng hay không?Kiểm tra hàng đợi đầy hay không?Chèn phần tử vào đuôi hàng đợiTìm và lấy ra phần tử ở đầu hàng đợi 3Cài đặt hàng đợi bằng mảngConst max =N;Type Queue = Record	front, rear :Integer;	element= array[1.. max] of item;end;Var Q:Queue;4Cài đặt hàng đợi bằng mảng (tiếp)Khởi tạo hàng đợi rỗngProcedure Init( Var Q:Queue);Begin	Q.front: =1;	Q.rear :=0;End;5Cài đặt hàng đợi bằng mảng (tiếp)Kiểm tra hàng đợi rỗng ?Hàm isEmpty :Input: Hàng đợi QOutput:1: Nếu hàng đợi rỗng0: Hàng đợi đã có phần tử6Cài đặt hàng đợi bằng mảng (tiếp)Function isEmpty(Q:Queue):boolean;Begin	isEmpty:= (Q.rear = 0);End;7Cài đặt hàng đợi bằng mảng (tiếp)Kiểm tra hàng đợi đầy?Xây dựng hàm isFull:Input: Hàng đợi QOutput:1: Hàng đợi đầy0: ngược lại8Cài đặt hàng đợi bằng mảng (tiếp)Function isFull(Q: Queue):boolean;begin	isFull:= (Q.rear = max);end;9Cài đặt hàng đợi bằng mảng (tiếp)Thêm phần tử vào đuôi hàng đợiThuật toán:Nếu hàng đợi đầy thì dừng, ngược lại làm các bước sau:Gán rear = rear +1;Gán phần tử tại vị trí rear bằng phần tử x cần thêm vào hàng đợi10Cài đặt hàng đợi bằng mảng (tiếp)Xây dựng hàm Add( var Q:Queue; x:Item)Input:Q: Hàng đợix : Phần tử cần chèn có kiểu Item11Cài đặt hàng đợi bằng mảng (tiếp)Procedure Add( var Q: Queue,x :Item);Begin	if(not isFull(Q)) then	begin	Q.rear :=Q.rear+1;	Q.element[Q.rear]: =x;	end;End;12Cài đặt hàng đợi bằng mảng (tiếp)Tìm và lấy ra phần tử ở đầu hàng đợiThuật toán:Nếu hàng đợi rỗng thì dừng, ngược lại làm các bước:Lấy phần tử tại vị trí frontNếu front = rear đánh dấu hàng rỗng bằng cách gán front =1, rear =0 ngược lại front = front+113Cài đặt hàng đợi bằng mảng (tiếp)Xây dựng thủ tục Remove(Q:Queue;var x:Item) Procedure Remove(Q:Queue;var x:Item);Begin	if(not isEmpty(Q)) then 	begin	x := Q.element[Q.front];	if(Q.front= Q.rear) then 	Q.front =1;Q.rear =0;}	else Q.front = Q.front +1;	 end;End;14Cài đặt hàng đợi bằng mảng vòng trònConst max = N;Type Queue = Record	count,front, rear :Integer;	element= array[1.. max] of item;end;Var Q:Queue;15Cài đặt hàng đợi bằng mảng vòng trònProcedure Init( var Q: Queue);Begin	Q.count: =0;Q.front :=1; Q.rear :=0;End;Function isEmpty( Q:Queue):boolean;Begin	isEmpty :=(Q.count =0);End;16Cài đặt hàng đợi bằng mảng vòng trònFunction isFull(Q:Queue):boolean;Begin	isFull:= (Q.count = max);End;17Cài đặt hàng đợi bằng mảng vòng trònProcedure Add(var Q:Queue; x:Item); Begin	if (not isFull(Q)) then 	begin	if (Q.rear = max) then Q.rear :=1;	else Q.rear: = Q.rear +1;	Q.element[Q.rear] := x;	Q.count: = Q.count +1; end;End;18Cài đặt hàng đợi bằng mảng vòng trònProcedure Remove(Q: Queue; var: x: Item );begin	if (not isEmpty(Q)) then	begin	x := Q.element[Q.front];	if(Q.front =Q.rear) then begin	Q.front: =1; Q.rear: =0;	end else if(Q.front = max) then Q.front: =1;	else Q.front := Q.front+1;	Q.count := Q.count+1; 	 end;End;19Cài đặt hàng đợi bằng con trỏPointer =^Node;Type Node =Record	Data: Item;	next: Pointer;end; Queue =Record	*front,*rear : Node;end;20Cài đặt hàng đợi bằng con trỏProcedure Init(var Q:Queue); Begin	Q.front := nil;End;Function isEmpty(Q:Queue):boolean;Begin	IsEmpty:=(Q=nil);End;21Cài đặt hàng đợi bằng con trỏProcdure Add(var Q: Queue; x: Item);Begin	p:Pointer;	new(p);	p^.Data: = x;p^.next:= nil;	if(Q.front = nil)then begin Q.front := p;Q.rear:= p;end	else begin Q.rear^.next := p; Q^.rear :=p;end;End;22Cài đặt hàng đợi bằng con trỏProcedure Remove(Q:Queue ; var x:Item);Begin	p:Pointer;	if( not isEmpty(Q)) then 	begin	p:= Q.front;	x:=Q.front^.Data;	Q.front: = Q.front^.next;	dispose (p);	end;End;23