Xem mẫu
- Cấu trúc dữ liệu và giải thuật
Đỗ Tuấn Anh
anhdt@it-hut.edu.vn
- Nộ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 đợi
1. Định nghĩa Stack
2. Lưu trữ kế tiếp với Stack (sử dụng mảng)
3. Ứng dụng của Stack
4. Định nghĩa Queue
5. 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 Stack
8. 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)
Pop
Push
top Pop
7 7
7 top
top
5
top
5 5 5
3 3 3 3
2 2 2 2
- Ví 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 Out
- Cá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/đầy
- Push
Thêm phần tử mới vào đỉnh stack
- Pop
Rút một phần tử ra khỏi đỉnh stack
- Top
Kiểm tra phần tử đỉnh. Stack không thay
đổi
- Push/Pop Stack
Stack rỗng thêm một phần tử Thêm một phần tử khác
top
B
top
A
top A
Lấy một phần tử ra khỏi Stack
top
A
- Lư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ối
- Lư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-20
- Cấ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
3
- Push
int 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 */
- Pop
int 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 */
nguon tai.lieu . vn