Cấu trúc dữ liệu và giải thuật-Chương 4: Ngăn xếp và hàng đợi

Hai danh sách tuyến tính đặc biệt: ngăn xếp-stack; hàng đợi-quêu. Stack: la danh sách mà xóa và thêm phần tử bắt nuộc phải cùng được thực hiện tại một đầu quy nhất định...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật-Chương 4: Ngăn xếp và hàng đợiCấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh anhdt@it-hut.edu.vnNội dung Chương 1 – Thiết kế và phân tích (5 tiết) Chương 2 – Giải thuật đệ quy (10 tiết) Chương 3 – Mảng và danh sách (5 tiết) Chương 4 – Ngăn xếp và hàng đợi (10 tiết) Chương 5 – Cấu trúc cây (10 tiết) Chương 8 – Tìm kiếm (5 tiết) Chương 7 – Sắp xếp (10 tiết) Chương 6 – Đồ thị (5 tiết)Chương 4 – Ngăn xếp và hàng đợi1. Định nghĩa Stack2. Lưu trữ kế tiếp với Stack (sử dụng mảng)3. Ứng dụng của Stack4. Định nghĩa Queue5. Lưu trữ kế tiếp với Queue (sử dụng mảng)6. Ứng dụng của Queue (not yet)7. Lưu trữ móc nối với Stack8. Lưu trữ móc nối với Queue (bài tập)9. Stack và cài đặt đệ quy (not neccesary)1. Định nghĩa Stack Hai danh sách tuyến tính đặc biệt: Ngăn xếp – Stack Hàng đợi – Queue Stack: là danh sách mà xóa và thêm phần tử bắt buộc phải cùng được thực hiện tại một đầu duy nhất (đỉnh) PopPush top Pop 7 7 7 top top 5 top 5 5 5 3 3 3 3 2 2 2 2Ví dụ của Stack trong thực tếVí dụ của Stack trong thực tế • Stack là một cấu trúc LIFO: Last In First OutCác thao tác cơ bản trên Stack Push Thêm một phần tử Tràn (overflow) Pop Xóa một phần tử Underflow Top Phần tử đỉnh stack rỗng Kiểm tra rỗng/đầyPush Thêm phần tử mới vào đỉnh stackPop Rút một phần tử ra khỏi đỉnh stackTop Kiểm tra phần tử đỉnh. Stack không thay đổiPush/Pop Stack Stack rỗng thêm một phần tử Thêm một phần tử khác top B top Atop A Lấy một phần tử ra khỏi Stack top ALưu trữ Stack 2 cách lưu trữ: Lưu trữ kế tiếp: sử dụng mảng Lưu trữ móc nối: sử dụng danh sách móc nốiLưu trữ Stack bằng Mảng Stack được lưu trữ như một mảng Số các phần tử giới hạn Figure 4-20Cấu trúc dữ liệu/* Stack của các số nguyên: intstack */typedef struct intstack { int *stackAry;/* mảng lưu trữ các phần tử */ /* số ptử hiện có của stack */ int count; int stackMax; /* giới hạn Max của số ptử */ /* chỉ số của phần tử đỉnh */ int top;}IntStack;Tràn và Cạn Cạn (underflow) xảy ra khi cố gắng rút phần tử từ stack rỗng Pop Tràn (overflow) xảy ra khi đẩy thêm phần tử vào stack đang đầy 18 6 … 11 3Pushint PushStack(IntStack *stack, int dataIn) { /* Kiểm tra tràn */ if (stack->count == stack->stackMax) return 0; /* Thêm phần tử vào stack */ (stack->count)++; (stack->top)++; /* Tăng đỉnh */ stack->stackAry[stack->top] =dataIn; return 1;} /* pushStack */Popint PopStack (IntStack *stack, int *dataOut) { /* Kiểm tra stack rỗng */ if (stack->count == 0) return 0; /* Lấy giá trị phần tử bị loại*/ *dataOut=stack->stackAry[stack->top]; (stack->count)--; (stack->top)--; /* Giảm đỉnh */ return 1;} /* popStack */ Top/* Lấy phần tử đỉnh của stack Trả lại 1 nếu thành công; 0 nếu stack rỗng dataOut chứa kết quả */int TopStack (IntStack *stack, int* dataOut) { if (stack->count == 0) // Stack rỗng return 0; *dataOut = stack->stackAry[stack->top]; return 1;} /* stackTop */Kiểm tra rỗng?/* Kiểm tra stack rỗng Trả lại 1 nếu là rỗng 0 nếu không rỗng */int IsEmptyStack (IntStack *stack){ return (stack->count == 0);} /* emptyStack */Kiểm tra đầy?/* Kiểm tra stack đầy Trả lại 1 nếu là đầy 0 nếu không đầy */int IsFullStack (IntStack *stack){ return(stack->count==stack->stackMax);} /* fullStack */ ...