Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Châu Thị Bảo Hà
lượt xem 2
download
Chương 5 trình bày những kiến thức về ngăn xếp (Stack) và hàng đợi (Queue) trong dữ liệu. Thông qua chương này người học sẽ biết được: Khái niệm Stack và Queue, các thao tác trên Stack và Queue, hiện thực Stack và Queue, ứng dụng của Stack và Queue. Mời các bạn cùng tham khảo.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Châu Thị Bảo Hà
- Chương 5: NGĂN XẾP – HÀNG ĐỢI (Stack - Queue) 1
- NỘI DUNG Ngăn xếp (Stack) Hàng đợi (Queue) 2 Chương 5: Ngăn xếp – Hàng đợi
- NỘI DUNG Ngăn xếp (Stack) Khái niệm Stack Các thao tác trên Stack Hiện thực Stack Ứng dụng của Stack 3 Chương 5: Ngăn xếp – Hàng đợi
- STACK - KHÁI NIỆM Stack là một danh sách mà các đối tượng được thêm vào và lấy ra chỉ ở một đầu của danh sách (A stack is simply a list of elements with insertions and deletions permitted at one end) Vì thế, thao tác trên Stack được thực hiện theo cơ chế LIFO (Last In First Out - Vào sau ra trước) 4 Chương 5: Ngăn xếp – Hàng đợi
- STACK – CÁC THAO TÁC Stack hỗ trợ 2 thao tác chính: Push: Thêm 1 đối tượng vào Stack Pop: Lấy 1 đối tượng ra khỏi Stack Ví dụ: 523--4 Stack cũng hỗ trợ một số thao tác khác: isEmpty(): Kiểm tra xem Stack có rỗng không Top(): Trả về giá trị của phần tử nằm ở đầu Stack mà không hủy nó khỏi Stack. Nếu Stack rỗng thì lỗi sẽ xảy ra 5 Chương 5: Ngăn xếp – Hàng đợi
- STACK – HIỆN THỰC STACK (IMPLEMENTATION OF A STACK) Mảng 1 chiều Danh sách LK 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 khá dàng phức tạp 6 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (IMPLEMENTATION OF A STACK USING ARRAY) Có thể tạo một Stack bằng cách khai báo một mảng 1 chiều với kích thước tối đa là N (ví dụ: N =1000) Stack có thể chứa tối đa N phần tử đánh số từ 0 đến N-1 Phần tử nằm ở đỉnh Stack sẽ có chỉ số là top Như vậy, để khai báo một Stack, ta cần một mảng 1 chiều, và 1 biến số nguyên top cho biết chỉ số của đỉnh Stack: struct Stack { DataType list[N]; int top; }; 7 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Các hàm cần cài đặt: Init( Stack &s ): Khởi tạo Stack isEmpty( Stack s ) Push( Stack &s , DataType x ) Pop( Stack &s ) Top( Stack &s ) Khi cài đặt bằng mảng 1 chiều, Stack bị giới hạn kích thước nên cần xây dựng thêm một thao tác phụ cho Stack: isFull(): Kiểm tra xem Stack có đầy chưa, vì khi Stack đầy, việc gọi đến hàm Push() sẽ bị lỗi 8 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Khởi tạo Stack: 9 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Kiểm tra Stack có rỗng hay không: Rỗng: hàm trả về 1 Ngược lại: hàm trả về 0 10 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Kiểm tra Stack có đầy hay không: Đầy: hàm trả về 1 Ngược lại: hàm trả về 0 11 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Thêm một phần tử x vào Stack 12 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Lấy một phần tử ra khỏi Stack 13 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Xem phần tử ở đỉnh Stack DataType Top(Stack s) { DataType x; if (!isEmpty(s)) // stack không rỗng { x = s.list[s.top-1]; } return x; } 14 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Nhận xét: Các thao tác trên đều làm việc với chi phí O(1) Việc cài đặt Stack thông qua mảng một chiều đơn giản và khá hiệu quả Tuy nhiên, hạn chế lớn nhất của phương án cài đặt này là giới hạn về kích thước của Stack (N) Giá trị của N có thể quá nhỏ so với nhu cầu thực tế hoặc quá lớn sẽ làm lãng phí bộ nhớ 15 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG DSLK (IMPLEMENTATION OF A STACK USING LINKED LIST) Có thể tạo một Stack bằng cách sử dụng một danh sách liên kết đơn (DSLK) Khai báo các cấu trúc: struct Node { DataType data; Node *pNext; }; struct Stack { Node *top; 16 }; Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG MẢNG (TT.) (IMPLEMENTATION OF A STACK USING ARRAY) Các hàm cần cài đặt: Init( Stack &s ): Khởi tạo Stack isEmpty( Stack s ) Push( Stack &s , DataType x ) Pop( Stack &s ) Top( Stack &s ) 17 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG DSLK (TT.) (IMPLEMENTATION OF A STACK USING LINKED LIST) Khởi tạo Stack: void Init( Stack &s ) { } 18 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG DSLK (TT.) (IMPLEMENTATION OF A STACK USING LINKED LIST) Kiểm tra xem Stack có rỗng không: int isEmpty ( Stack s ) { } 19 Chương 5: Ngăn xếp – Hàng đợi
- HIỆN THỰC STACK DÙNG DSLK (TT.) (IMPLEMENTATION OF A STACK USING LINKED LIST) Thêm một phần tử vào Stack: void Push ( Stack &s, DataType x ) { Thêm phần tử vào đầu danh sách 20 } Chương 5: Ngăn xếp – Hàng đợi
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn