Cấu trúc dữ liệu và giải thuật - Chương 4

NGĂN XẾP (STACK) VÀ HÀNG ĐỢI (QUEUE)I. ĐỊNH NGHĨA STACK Stack là 1 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 ở 1 đầu; được gọi là đỉnh (top) Có thể hình dung cơ cấu của stack như 1 chồng đĩa.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 4 Chương IV. NGĂN XẾP (STACK) VÀ HÀNG ĐỢI (QUEUE)I. ĐỊNH NGHĨA STACK Stack là 1 kiểu danh sách đặc biệt mà phép bổ sung và phép loại b ỏ luôn thựchiện ở 1 đầu; đ ược gọ i là đỉnh (top) Có th ể hình dung cơ cấu của stack như 1 chồng đĩa. Đưa thêm 1 đ ĩa mới vàothì đặt nó vào đầu phía trên (đỉnh), lấy 1 đĩa ra thì cũng 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ẽ đ ượclấ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à chính nó là đĩa được lấy ra sau cùng. Như vậy stack hoạt động theo cơ ch ế : “vào-sau-ra-trước” (last-in-first-out).Do đó stack đượ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.II. LƯU TRỮ KẾ TIẾP ĐỐI VỚI STACK Đó chính là cách cài đ ặt stack bởi 1 vectơ lưu trữ Stack, S bao gồ m n ô nhớ kếtiếp nhau. Như vậy phần tử ở đỉnh stack sẽ đ ược định vị bởi 1 chỉ số i nào đó , màta coi nh ư 1 địa ch ỉ tương đối (địa ch ỉ thực-địa chỉ tuyệt đố i-sẽ đựơc xác đ ịnh nhưđã nêu ở mục 2.2.2 thuộ c chương 2). Có thể coi i những giá trị của 1 con trỏ T, trỏ tới đỉnh stack. Người ta quy ướcT=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, khiT=n thì stack sẽ đầy, lúc đó nếu có phép bổ sung 1 phần tử 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 T=0 nghĩa là stack đãrỗng, mà lại có phép loại bỏ 1 p hần tử ra khỏ i stack thì phép xử lý này cũng khôngthự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[1] S[2] S[3] • • • • •S Đáy T củ a stack Hình 4.1 Khi bổ sung 1 ph ần tử mới vào thì T tăng lên 1, còn lại khi loại bỏ 1 phần tửra khỏi stack thì T giảm đ i 1. Hai thủ tục dưới đây thể hiện 2 phép xử lí này. Void PUSH(S,T,X); /*Thực hiện việc bổ sung phần tử X vào Stack, cài đặt bởi Vectơ S mà Tđang trỏ tới đ ỉnh*/ { /*Kiểm tra xem Stack đã đầy chư a*/ If (T=n) { printf (“Stack sẽ TRÀN/n”); return; } /*Chuyển con trỏ*/ T=T+1; /*Nạp X vào*/ S[T]=X; } Void POP(S,T,X); /*Thực hiện việc lo ại phần tử đang ở đ ỉnh Stack ra khỏ i Stack và bảo lưuthông tin củ a phần tử này vào Y*/ { /*Kiểm tra xem Stack có cạn không*/ If (T=0) { printf (“Stack đã CẠN/n”); return; } /*Bảo lưu thông tin củ a phần tử sẽ b ị lo ại*/ Y=S[T]; /*Chuyển con trỏ*/ T=T-1;}III. ÁP DỤNG CỦA STACK1. Bài toán đổi cơ số từ thập phân sang nhị phân Ta đã biết : dữ liệu lưu trữ trong bộ nhớ của MTĐT đều được biểu diễn dướidạng số nh ị phân (với 2 chữ só 0 và 1). Như vậy là số thập phân xuất hiện trongchương trình đ ều phải chuyển đổi sang nhị phân . Trước khi xử lí và các kết quảdưới d ạng số nhị phân sẽ được đổi sang th ập phân để hiển th ị cho người dùng biết(vì người dùng vố n đ ã quen với số thập phân rồi). Mộ t cách tổng quát : số thập phân bao gồm 2 phần, phần nguyên và ph ầnphấnó th ập phân – mà ta quen gọ i là phần lẻ. Việc chuyển đổi sang số nh ị phân,ứng với 2 phần, có khác nhau. Ở đây ta chỉ xét tới việc chuyển phần nguyên thôi,hay nói cách khác : ta sẽ xét tới việc chuyển đổi 1 số nguyên dưới dạng thập phânsang nhị phân. Trước h ết ta cần thấy rằng : Ở dạng số thập phân 274 biểu diễn cho con số có giá trị là: 2 . 102 + 3 . 10 1 + 4 . 100 Nếu đem con số n ày chia cho 10 và đ ể ý tới các số dư ta sẽ thấy: Mã số 274 chính là d ạng hiển thị của các số dư, theo thứ tự xuất hiện vàngược lại. Tương tự như vậy, mã số nh ị phân của 1 con số, cho dưới dạng thập phân,cũng sẽ được xác định với phép chia và lấy số dư, chỉ có khác là bây giờ thực hiệnphép chia với 2 và d ư số sẽ là số 0 hoặc 1 thôi. Như vậy rõ ràng là trong cách chuyển đổi này các số dư đã được tạo ra saulại hiển thị trước. Cơ ch ế sắp xếp này rất phù hợp với cơ ch ế hoạt động củ a stack.Vì vậy trong giải thuật chuyển đổi số nguyên từ thập phân sang nhị phân, người tathường sử dụng 1 stack để lưu trữ số d ư, sau đó lại lấy các số này lại từ stack đểhiển thị thành mã số nh ị phân. Giả sử stack được cài đặt bởi 1 vectơ lưu trữ S, mà T là con trỏ, trỏ tới đỉnh;lúc đ ầu stack rỗng, nghĩa là T=0. Có thể viết giải thuật chuyển đổ i 1 số nguyên N sang dạng nhị phân b ằngthủ tụ c như sau : Void CHANGE(N); { m=N /*Tính số dư và nạp vào Stack(S)*/ While m!=0 { R=m mod 2; /*Tính số dư*/ PUSH(S,T,R); /*Nạp R vào Stack S*/ M=m div 2; / ...