Bài giảng Cấu trúc dữ liệu: Chương 5 - Trịnh Xuân

Chương 4 cung cấp cho người học những kiến thức về ngăn xếp và hàng đợi. Nội dung chính trong chương 4 gồm: Trình bày khái niệm ngăn xếp (Stack) và hàng đợi (Queue), minh họa các ứng dụng, các phương pháp xây dựng Stack và Queue. 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 - Trịnh Xuân I. Stack – Ngăn xếp: CHƯƠNG V: STACK - QUEUE 8/4/16 2 CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân 1. Giới thiệu: * Các thao tác cơ bản với Stack !  Ngăn xếp là một kiểu danh sách tuyến tính với hai !  initStack (Stack): Khởi tạo Stack rỗng phép toán bổ sung một phần tử vào cuối danh !  isEmpty (Stack): Kiểm tra Stack có rỗng sách và loại bỏ một phần tử cũng ở cuối của danh sách hay không? !  Trong ngăn xếp một phần tử vào sau sẽ bị đẩy ra !  isFull (Stack): kiểm tra danh sách đầy trước và phần tử vào trước sẽ bị đấy ra sau !  Push (Stack, Item): Đẩy phần tử item vào gọi là danh sách LIFO (Last In First Out) Stack !  Pop (Stack): Hủy bỏ một phần tử khỏi Stack !  Top (Stack): Xem nội dung của phần tử đầu empty stack push an element push another pop tiên của Stack top B top top A A AtopCTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân 2. Cài đặt Stack a. Cài đặt Stack bằng mảng !  bằng mảng !  Khai báo Cấu trúc DL Stack #  Sử dụng mảng một chiều để chứa các phần tử #  Cần chỉ số top để chỉ đỉnh !  Thêm – xóa trên vị trí Top #define max … #  Chỉ số đầu (0) để chỉ đáy Top struct Stack { !  bằng danh sách liên kết int top; #  Sử dụng một danh sách liên kết đơn Data nut[max]; #  khai báo và định nghĩa phần tử đầu (Top) để chỉ đỉnh }; !  Thêm-xóa thực hiện tại vị trí Top #  Phần tử cuối là đáy danh sáchCTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Khởi tạo Stack rỗng: * Kiểm tra ngăn xếp rỗng int isEmpty ( Stack s) void InitStack ( Stack &s ) { { if ( s.top == -1 ) s.top = -1 return 1; } else return 0; } Top Top=-1 TopCTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân CTDL – Khoa CNTH – Viện ĐH Mở HN 8/4/16 Ths. Trịnh Thị Xuân * Kiểm tra danh sách đầy * Bổ sung một phần tử vào ngăn xếp int isFull( S ...