Bài giảng Kỹ thuật lập trình: Ngăn xếp và hàng đợi - Nguyễn Minh Huy

Bài giảng Kỹ thuật lập trình: Ngăn xếp và hàng đợi, được biên soạn gồm các nội dung chính sau Tổng quan về ngăn xếp; tổng quan về hàng đợi. 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 Kỹ thuật lập trình: Ngăn xếp và hàng đợi - Nguyễn Minh HuyNgăn x p và Hàng đ i GV. Nguy n Minh HuyK thu t l p trình - Nguy n Minh Huy 1N i dung T ng quan v ngăn x p. p. T ng quan v hàng đ i. i.K thu t l p trình - Nguy n Minh Huy 2N i dung T ng quan v ngăn x p.p. T ng quan v hàng đ i. i.K thu t l p trình - Nguy n Minh Huy 3T ng quan v ngăn x p Khái ni m ngăn x p: p: Dãy ph n t ho t đ ng theo cơ ch LIFO. Cơ ch LIFO (Last In First Out). (L Th t vào sau ra trư c. c. Vào sau Ra trư c Truy xu t t do M ng 5 7 2 6 5 7 Truy xu t tu n t 2 6 data data head next next NULL Ngăn x pK thu t l p trình - Nguy n Minh Huy 4T ng quan v ngăn x p Các thao tác trên ngăn x p: p: push: thêm ph n t . pop: l y ph n t . push pop peek: đ c ph n t . 8 5 empty: ki m tra r ng. ng. peek 5 full: ki m tra đ y. y. 7 2 6 Ngăn x pK thu t l p trình - Nguy n Minh Huy 5T ng quan v ngăn x p Cài đ t ngăn x p trong C: Khai báo và kh i t o: o: // Dùng m ng đ ng. ng. // Dùng danh sách liên k t đơn. đơn. struct Stack struct Stack { { int *data; SNode *head; int top; }; int size; }; void stack_init(Stack &s, int initSize) stack_init(Stack initSize) void stack_init(Stack &s) stack_init(Stack { { s.size = initSize; initSize; head = NULL; s.data = new int[initSize]; int[initSize] } s.top = 0; }K thu t l p trình - Nguy n Minh Huy 6T ng quan v ngăn x p Cài đ t ngăn x p trong C: Ki m tra r ng và đ y: y: // Dùng m ng đ ng. ng. // Dùng danh sách liên k t đơn. đơn. bool stack_empty(Stack s) stack_empty(Stack bool stack_empty(Stack s) stack_empty(Stack { { return s.top == 0; return s.head == NULL; } } bool stack_full(Stack s) stack_full(Stack { return s.top == size; }K thu t l p trình - Nguy n Minh Huy 7T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: Thêm ph n t : stack_push. stack_push. Dùng m ng đ ng Dùng danh sách liên k t đơn Thêm đ u x data x next data 5 7 data data head next next NULL topK thu t l p trình - Nguy n Minh Huy 8T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: L y ph n t : stack_pop. stack_pop. Dùng m ng đ ng Dùng danh sách liên k t đơn data 5 7 2 data data head next next NULL topK thu t l p trình - Nguy n Minh Huy 9T ng quan v ngăn x p Cài đ t ngăn x p trong C: Các thao tác: tác: Đ c ph n t : stack_peek. stack_peek. Dùng m ng đ ng Dùng danh sách liên k t đơn data 5 7 2 data data head next next NULL topK thu t l p trình - Nguy n Minh Huy 10T ng quan v ngăn x p ng d ng ngăn x p: p: Th c hi n thao tác ngư c ...