tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi - TS. Trần Ngọc Việt

Bài giảng Cấu trúc dữ liệu và giải thuật: Ngăn xếp và hàng đợi được biên soạn gồm các nội dung chính sau: Ngăn xếp – stack; Giải thuật chức năng PUSH của cấu trúc dữ liệu ngăn xếp-stack; Hàng đợi - queue. Mời các bạn cùng tham khảo! | Bài 1 Ngăn xếp stack -Một ngăn xếp-stack là một cấu trúc dữ liệu hoạt động theo nguyên lý vào sau ra trước LIFO- Last In First Out. Tức là phần tử cuối cùng được chèn vào ngăn xếp sẽ là phần tử đầu tiên được lấy ra khỏi ngăn xếp-stack. -Chẳng han một chồng sách minh họa chồng đĩa và bạn để nó trong một cái hộp như hình phía dưới. Giả sử hộp này vừa khít các cuốn sách. Khi đó các thao tác -Thêm một cuốn sách vào hộp push của ngăn xếp-stack -Lấy một cuốn sách khỏi hộp bạn chỉ lấy được thằng trên cùng pop của ngăn xếp-stack Hình 1. Ngăn xếp-stack CẤU TRÚC DỮ LIỆU 2 1. PUSH trong cấu trúc dữ liệu ngăn xếp-stack trình các bước đặt thêm phần tử dữ liệu mới vào trên ngăn xếp còn được biết đến với tên chức năng PUSH. Chức năng push bao gồm các bước sau Bước 1 kiểm tra xem ngăn xếp-stack đã đầy hay chưa. Bước 2 nếu ngăn xếp-stack là đầy tiến trình bị lỗi và thoát ra. Bước 3 nếu ngăn xếp-stack chưa đầy tăng top để trỏ tới phần bộ nhớ trống tiếp theo. Bước 4 thêm phần tử dữ liệu vào vị trí nơi mà top đang trỏ đến trên ngăn xếp-stack. Bước 5 trả về success. CẤU TRÚC DỮ LIỆU 3 thuật chức năng PUSH của cấu trúc dữ liệu ngăn xếp-stack giải thuật mã giả như sau bắt đầu chức năng push stack data if stack đã đầy return null kết thúc if top top 1 stack top data kết thúc hàm CẤU TRÚC DỮ LIỆU 4 2. POP trong cấu trúc dữ liệu ngăn xếp-stack -Thực hiện chức năng POP xóa phần tử từ ngăn xếp-stack còn được gọi là POP. -Triển khai mảng của chức năng pop phần tử dữ liệu không thực sự bị xóa thay vào đó top sẽ bị giảm về vị trí thấp hơn trong ngăn xếp-stack để trỏ tới giá trị tiếp theo. -Danh sách liên kết dữ liệu pop xóa phần tử dữ liệu và xóa phần tử khỏi không gian bộ nhớ. Chức năng POP bao gồm các bước Bước 1 kiểm tra ngăn xếp-stack là trống hay không. Bước 2 nếu ngăn xếp-stack đầy tiến trình bị lỗi và thoát ra. Bước 3 nếu ngăn xếp-stack là không trống truy cập phần tử dữ liệu tại top đang trỏ tới. Bước 4 giảm giá trị của top đi 1. Bước 5 trả về success. CẤU TRÚC DỮ LIỆU