Giáo trình cấu trúc dữ liệu và giải thuât part 5

Tham khảo tài liệu 'giáo trình cấu trúc dữ liệu và giải thuât part 5', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 4. NGĂN xếp STACK VÀ HÀNG ĐỢI QU U . ĐỊNH NGHĨA STACK Stack là một kiểu danh sách đặc biệt mà phép bổ sung và phép loại bó luôn thực hiện ở một đầu được gọi là đỉnh top . Có thể hình dung cơ cấu của stack như một chổng đĩa. Đưa thêm một đĩa mới vào thì đặt nó vào đầu phía trên đỉnh lấy một đĩa ra thì cũng chỉ lấy được từ đầu đó. Đĩa đưa vào sau cùng chính là đĩa đang nằm ở đỉnh và nó cũng chính là đĩa sẽ được lấy ra trước tiên. Còn đĩa đưa vào đầu tiên lại đang ở vị trí được gọi là đáy bottom và nó chính là đĩa được lấy ra sau cùng. Như vậy slack hoạt động theo cơ chê vào sau ra - trước last in - first out . Do đó slack còn đưđc gọi là danh sách kiểu LIFO Stack có thể rỗng nghĩa là không có phẩn tử nào . LƯU TRỮ KÊ TIẾP ĐÔÌ VỚI STACK Đó chính là cách cài đặt stack bởi một vectơ lưu trữ s bao gồm n ỏ nhớ kế tiếp nhau. Như vậy phần tử ở đỉnh stack sẽ được định vị bởi một chỉ số ĩ nào đó. mà ta coi như một địa chỉ tương đối địa chỉ thực - địa chí tuyệt đô i -sẽ được xác định như đã nêu ở mục thuộc chương 2 . Có thế coi i như giá trị của một con trỏ T trỏ tới đỉnh stack. Người ta quy ước T 0 nghĩa là stack rỗng. Như vậy T i thì stack có i phán tử. Rõ ràng 0 T n khi T n thì stack đă đầy lúc đó nếu có phép bổ sung một phần lử mới vào stack thì sẽ không thực hiện được vì không còn chỗ ta nói là có hiên tượng TRÀN overflow và tất nhiên việc xử lí phải ngừng lại. Còn nếu 64 T 0 nghĩa là stack đã rỗng mà lại có phép loại bỏ một phần tử ra khỏi stack thì phép xử lí này cũng không thực hiện được Ta nói có hiện tượng CẠN underflow . Sau đây là hình ảnh cài đặt của stack với 3 phần tử. S l S 2 S 3 T T đáy T của stack HÌNH Khi bổ sung một phần tử mới vào thì T tăng lên 1 còn khi loại bỏ một phần tử ra khỏi stack thì T giảm đi 1. Hai thủ tục dưới đây thể hiện hai phép xử lí này. Procedure PUSH S T X Thủ tục này thực hiên việc bổ sung phần tử X vào stack cài dặt bởi vectơ s mà T đang trò tới đỉnh Ị 1. Kiểm tra xem stack đã đầy chưa if T n then begin write .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.