Bài giảng Ngăn xếp - Stack, hàng đợi -queue

Ngăn xếp-Stack, hàng đợi-queue Ngăn xếp Chuyển đổi biểu diễn thập phân sang nhị phân 26|0 13|1 6|0 3|1 1|1 (26)10 = (11010)2 Ngăn xếp Một danh sách hay một dãy các mục dữ liệu trong đó phép toán thêm vào và bớt đi đều được thực hiện ở đầu Phép toán cơ bản: Push, Pop Last – in first – out Cài đặt bằng mảng và bản ghi Lật ngược ngăn xếp để phần tử ở vị trí số 1 là đáy ngăn xếp → biến Top ghi lại vị trí đỉnh ngăn xếp Const MaxSize = …; {độ lớn cực đại của ngăn xếp} Type ElementType = ..; {kiểu của các phần tử trong ngăn xếp} StackArray = array[1..MaxSize] of ElementType; StackType = record Top: 1..MaxSize; Element: StackArray end Var Procedure Create(Var S: StackType); {Khởi tạo ngăn xếp rỗng} Begin S.Top:=0; End --------------------------------------------------------------- Function Empty(S:StackType): Boolean; {Giá trị của hàm là true nếu ngăn xếp rỗng} Begin Empty:=(S.Top=0); End Procedure Push(Var S:StackType; Item: ElementType); {Thủ tục đẩy Item vào ngăn xếp S giả sử ngăn xếp kô đầy} Begin If S.Top=StackLimit then halt else with S do Begin Top:=Top+1; Element[Top]:=Item; End {of with} End {of Push} Procedure Pop(Var S: StackType; Var Item: ElementType); {Thủ tục lấy Item ra từ đỉnh của ngăn xếp S, giả sử ngăn xếp kô rỗng} Begin If Empty(S) then halt else with S do begin Item: = Element[Top]; Top:=Top -1 end End Begin {đọc số n cần chuyển vào} Create(S); While n0 do Begin R:=n mod 2; Push(S, R); n:=n div 2; End {of while} While not Empty(S) do Begin Pop(S, R); Write(R); End {of while } Ngăn xếp đầy không liên quan đến cấu trúc dữ liệu (về mặt lý thuyết là kô có giới hạn) Bd bằng mảng → kô chính xác Cài đặt bằng danh sách liên kết Type StackType=^StackNode StackNode=record Data: ElementType; Next: Stacktype End Var S: StackType; Procedure Create(Var S: StackType) Begin S:=nil; End --------------------------------------------------------------- Function Empty(S: StackType):boolean; Begin Empty:=(S=nil); End Procedure Push(Var S: StackType; Item: ElementType); Var Temp: StackType; Begin New(Temp); Temp^.Data:=Item; Temp^.Next:=S; S:=Temp; End {of push} ---------------------------------------------------------------------------------------------------- Procedure Pop(Var S:StackType; Var Item: ElementType); Var Temp: StackType; Begin If Empty(S) then halt Else begin Item:=S^.data; Temp:=S; S:=S^.Next; Dispose(Temp); end; End; Ứng dụng ngăn xếp Loại bỏ sự đệ qui của chương trình thủ tục đệ qui P(x) được gọi từ → thực hiện ở mức 1.Thủ tục này gọi chính nó→mức 2... cho đến một mức k. k phải thực hiện xong thì mức k-1 mới được thực hiện → thủ tục quay về mức k-1 từ mức i đi vào mức i+1 → các biến cục bộ của mức i, địa chỉ của mã lệnh còn dang dở phải được lưu trữ → địa chỉ này gọi là địa chỉ trở về → dùng một ngăn xếp để lưu giữ các giá trị cần thiết của mỗi lần gọi tới thủ tục. Tóm tắt quá trình: Bước 1: Lưu các biến cục bộ và địa chỉ trở về. Bước 2: Nếu thỏa điều kiện ngừng đệ qui thì chuyển sang bước 3. Nếu không thì tính toán từng phần và quay lại bước 1 (đệ qui tiếp). Bước 3: Khôi phục lại các biến cục bộ và địa chỉ trở về. Bài toán tháp Hà Nội (tower of Hanoi) Bài toán tháp Hà Nội được phát biểu như sau Có ba cọc A,B,C. Khởi đầu cọc A có một số đĩa xếp theo thứ tự nhỏ dần lên trên đỉnh. Bài toán đặt ra là phải chuyển toàn bộ chồng đĩa từ A sang B. Mỗi lần thực hiện chuyển một đĩa từ một cọc sang một cọc khác và không được đặt đĩa lớn nằm trên đĩa nhỏ (hình II.10) type elementType=record N:integer; A,B,C:integer; end; procedure MOVE(x:elementtype); var temp,temp1:elementtype; S:Stack; {ngăn xếp chứa các phần tử kiểu elementType} begin MAKENULL_STACK(s); PUSH(x,s); repeat TOP(s,temp);{lấy phần tử đầu ngăn xếp} POP(s);{xoá phần tử đầu ngăn xếp} if temp.n=1 then writeln(‘ Chuyển 1 đĩa từ ',temp.A,' sang ',temp.B) Else begin { lưu trữ cho lời gọi move(n-1,C,B,A) } temp1.n:=temp.n-1; temp1.A:=temp.C; temp1.B:=temp.B; temp1.C:=temp.A PUSH(temp1,s); { lưu trữ cho lời gọi move(1,A,B,C) } temp1.n:=1; temp1.A:=temp.A; temp1.B:=temp.B; temp1.C:=temp.C PUSH(temp1,s); {lưu trữ cho lời gọi move(n-1,A,C,B} temp1.n:=temp.n-1; temp1.A:=temp.A; temp1.B:=temp.C; temp1.C:=temp.B PUSH(temp1,s); end; until EMPTY_STACK(s); end; Ứng dụng – Ký pháp nghịch đảo BaLan Trung tố - infix notation X=A*B+C → Ký pháp hậu tố: toán tử đi sau toán hạng 1950 nhà logic học Ba Lan Jan Lukasiewicz: dấu ngoặc là không cần thiết trong ký pháp hậu tố (ký pháp nghịch đảo Ba Lan) 2 * (3 + 4) 2 3 4 + * Đánh giá biểu thức 1 6 + 8 4 2 - - * 1 6 + 8 4 2 - - * 7 8 4 2 - - * 7 8 2 - * 7 6 * 42 Tt đánh giá biểu thức RPN Khởi động 1 ngăn xếp rỗng Lặp lại các bước sau đây cho đến khi dấu kết thúc biểu thức được đọc Đọc phần tử (token - hằng số, biến số, toán tử số học) tiếp theo trong biểu thức RPN Nếu phần tử này là một toán hạng, đẩy vào ngăn xếp. Nếu là toán tử, thực hiện các bước sau: Lấy ra từ đỉnh ngăn xếp hai giá trị (nếu ngăn xếp kô chứa 2 phần tử, xảy ra lỗi biểu thức kô đúng dạng RPN, tt kết thúc) Áp dụng toán tử trên vào hai giá trị vừa lấy ra Đẩy kết quả vào ngăn xếp Khi gặp dấu kết thúc, giá trị bt thức là giá trị ở đỉnh ngăn xếp Chuyển biểu thức từ trung tố sang hậu tố 7 + 2 * 3 7: hiển thị ngay +: lưu trữ lại 2: hiển thị (trái hay phải) + so với * → đẩy * vào ngăn xếp 3: hiển thị Tt chuyển từ dạng trung tố sang dạng RPN Khởi động một ngăn xếp rỗng của các toán tử While (kô xảy ra lỗi và chưa đạt đến kết thúc của biểu thức trung tố) làm các bước sau: Đọc phần tử (hằng số, biến, toán tử, dấu ngoặc trái, phải) tiếp theo trong biểu thức trung tố Nếu phần tử là Một dấu ngoặc trái: đẩy nó vào ngăn xếp Một dấu ngoặc phải: lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi dấu ngoặc trái được đọc (nếu ngăn xếp là rỗng thì xảy ra lỗi) Một toán tử: nếu ngăn xếp là rỗng hay phần tử được ưu tiên hơn phần tử ở đỉnh ngăn xếp, đẩy phần tử vào ngăn xếp Nếu khác, lấy ra phần tử ở đỉnh ngăn xếp, lặp lại việc so sánh phần tử với đỉnh ngăn xếp (ngoặc trái được xem là có độ ưu tiên thấp hơn các toán tử) Một toán hạng: hiển thị Khi đạt đến dấu kết thúc biểu thức trung tố, lấy ra và hiển thị các phần tử của ngăn xếp cho đến khi nx rỗng Minh họa ví dụ: 2 * 8 – (2 + 3) Bài tập: Cài đặt Hàng đợi (Queue) Đến trước phục vụ trước First In First Out Cấu trúc dữ liệu là kiểu danh sách đặc biệt trong đó các phép toán cơ bản chèn và xóa được thực hiện ở điểm cuối của ds Đầu (head), đuôi (tail) Chờ được máy in phục vụ, bộ đêm vào ra Hàng đợi hai đầu (deque – double end queue) phép toán xóa và chèn phải được thực hiện ở cả hai đầu Ví dụ: Đầu vào tương tác: thêm dl vào vùng đệm qua bàn phím, xóa đi bằng cách ấn backspace hay delete Hàng đợi có độ ưu tiên (priority queue): mỗi mục được gán một giá trị ưu tiên nào đó, lưu trữ sao cho mục ưu tiên nhất ở gần đầu hàng đợi và được phục vụ trước Cài đặt hàng đợi bằng mảng và bản ghi Const MaxSize=…; {chiều dài cực đại của hàng đợi} MaxPosition = …; {maxsize-1} Type ElementType = ..; QueueArray = array[0..MaxPosition] of ElementType; QueueType = record Front, Rear: 0..MaxPosition Element: QueueArray end; Procedure CreateQ(Var Q: QueueType); {Thủ tục khởi tạo hàng đợi rỗng} Begin Q.Front:=0; Q.Rear:=0; End {of CreateQ} ------------------------------------------------------------------- Function EmptyQ(Q: QueueType): boolean; {trả lại giá trị true nếu hàng đợi rỗng} Begin EmptyQ:=(Q.Front=Q.Rear) End {of EmptyQ} Procedure AddQ(Var Q: QueueType; Item: ElementType) {Chèn Item vào đuôi hàng đợi, giả sử hàng đợi kô đầy} Var NewRear: 0..MaxPosition; Begin with Q do begin NewRear:=(Rear+1) mod maxsize; if NewRear = Front then halt else begin Element[Rear]:=Item; Rear :=NewRear; end {of else} End Procedure RemoveQ(Var Q: QueueType; Var Item: ElementType); {thủ tục tìm Item và lấy ra từ đầu hàng đợi, giả sử hàng đợi kô rỗng} Begin If EmptyQ(Q) then halt else with Q do begin Item:=Element[Front]; Front:=(Front + 1) mod MaxSize end {of else} End {of RemoveQ} Cài đặt hàng đợi bằng danh sách Procedure CreateQ(var F, R: QueueType) Begin F:=nil; R:=nil; End -------------------------------------------------------------------- Function EmptyQ(F, R: QueueType): boolean; Begin Empty:=(F=R); End Procedure AddQ(Var F, R: QueueType; Item: ElementType); Var Temp: QueueType; Begin New(Temp); Temp^.Data=Item; R^.Next:=Temp; R:=Temp; End Procedure RemoveQ(Var F, R: QueueType; Var Item: ElementType) Var T: QueueType; Begin Item:=F^.Data; T:=F; F:=F^.Next; Dispose(T); End;