Bài giảng Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi

Bài giảng "Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi" cung cấp cho người học các kiến thức cơ bản về: Khái niệm Stack, các thao tác trên Queue, hiện thực Queue, ứng dụng Queue, các thao tác trên Stack, hiện thực Stack, ứng dụng của Stack. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi 1Chương5: NGĂNXẾP–HÀNGĐỢI (StackQueue) Nộidung 2  Ngăn xếp (Stack)  Hàng đợi (Queue)Chương5:Ngănxếp–Hàngđợi Nộidung 3  Ngănxếp(Stack)  KháiniệmStack  CácthaotáctrênStack  HiệnthựcStack  ỨngdụngcủaStackChương5:Ngănxếp–Hàngđợi StackKháiniệm 4  Stacklàmộtdanhsáchmàcácđốitượngđượcthêmvàovà lấyrachỉởmộtđầucủadanhsách (Astackissimplyalistofelementswithinsertionsanddeletions permittedatoneend)  Vìthế,thaotáctrênStackđượcthựchiệntheocơchếLIFO (LastInFirstOutVàosauratrước)Chương5:Ngănxếp–Hàngđợi Stack–Cácthaotác 5  Stackhỗtrợ2thaotácchính:  Push: Thêm1đốitượngvàoStack  Pop: Lấy1đốitượngrakhỏi Stack  Vídụ: 5234  Stackcũnghỗtrợmộtsốthaotáckhác:  isEmpty():KiểmtraxemStackcórỗngkhông  Top():Trảvềgiátrịcủaphầntửnằmởđầu StackmàkhônghủynókhỏiStack.NếuStack rỗngthìlỗisẽxảyraChương5:Ngănxếp–Hàngđợi Stack–HiệnthựcStack (ImplementationofaStack) 6 Mảng1chiều DanhsáchLK Kích thước stack Cấp phát khi quá thiếu, lúc động! quá thừa Push/Pop khá dễ Push / Pop dàng khá phức tạpChương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng (ImplementationofaStackusingArray) 7  CóthểtạomộtStackbằngcáchkhaibáomộtmảng1chiều vớikíchthướctốiđalàN(vídụ:N=1000)  StackcóthểchứatốiđaNphầntửđánhsốtừ0đếnN1  PhầntửnằmởđỉnhStacksẽcóchỉsốlàtop  Nhưvậy,đểkhaibáomộtStack,tacầnmộtmảng1chiều, và1biếnsốnguyêntopchobiếtchỉsốcủađỉnhStack: structStack{ DataTypelist[N]; inttop; };Chương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 8  Cáchàmcầncàiđặt:  Init(Stack&s):KhởitạoStack  isEmpty(Stacks)  Push(Stack&s,DataTypex)  Pop(Stack&s)  Top(Stack&s)  Khicàiđặtbằngmảng1chiều,Stackbịgiớihạnkíchthước nêncầnxâydựngthêmmộtthaotácphụchoStack:  isFull():KiểmtraxemStackcóđầychưa,vìkhiStackđầy,việc gọiđếnhàmPush()sẽbịlỗiChương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 9  KhởitạoStack: void Init (Stack &s) { s.top = 0; }Chương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 10  KiểmtraStackcórỗnghaykhông:  Rỗng:hàmtrảvề1  Ngượclại:hàmtrảvề0 int isEmpty(Stack s) { if ( s.top==0 ) return 1; // stack rỗng else return 0; }Chương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 11  KiểmtraStackcóđầyhaykhông:  Đầy:hàmtrảvề1  Ngượclại:hàmtrảvề0 int isFull(Stack s) { if (s.top>=N) return 1; else return 0; }Chương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 12  ThêmmộtphầntửxvàoStack void Push (Stack &s, DataType x) { if (!isFull(s)) //stackchưađầy { s.list[s.top] = x; s.top++; } }Chương5:Ngănxếp–Hàngđợi HiệnthựcStackdùngmảng(tt.) (ImplementationofaStackusingArray) 13  LấymộtphầntửrakhỏiStack DataTyp ...