Chương 4: Ngăn xếp, hàng đợi và danh sách móc nối (stack, queue, link list)

Ngăn xếp (Stack) hay bộ xếp chồng là một kiểu danh sách tuyến tính đặc biệt mà phép bổ xung phần tử và loại bỏ phần tử luôn luôn được thực hiện ở một đầu gọi là đỉnh (top).
Nội dung trích xuất từ tài liệu:
Chương 4: Ngăn xếp, hàng đợi và danh sách móc nối (stack, queue, link list) CHƯƠNG 4 NGĂN XẾP, HÀNG ĐỢI VÀ DANH SÁCH MÓC NỐI (STACK, QUEUE, LINK LIST)4.1- Kiểu dữ liệu ngăn xếp và ứng dụng4.1.1- Định nghĩa và khai báo Ngăn xếp (Stack) hay bộ xếp chồng là một kiểu danh sách tuyến tính đặcbiệt mà phép bổ xung phần tử và loại bỏ phần tử luôn luôn được thực hiện ở mộtđầu gọi là đỉnh (top). Có thể hình dung stack như một chồng đĩa được xếp vào hộp hoặc một băngđạn được nạp vào khẩu súng liên thanh. Quá trình xếp đĩa hoặc nạp đạn chỉ đ ượcthực hiện ở một đầu, chiếc đĩa hoặc viên đạn cuối cùng lại chiếm vị trí ở đỉnh đầutiên còn đĩa đầu hoặc viên đạn đầu lại ở đáy của hộp (bottom), khi l ấy ra thì đĩacuối cùng hoặc viên đạn cuối cùng lại được lấy ra trước tiên. Nguyên tắc vào sau ratrước của stack còn được gọi dưới một tên khác LIFO (Last- in- First- Out). Stack có thể rỗng hoặc bao gồm một số phần tử. Có hai thao tác chính chostack là thêm một nút vào đỉnh stack (push) và loại bỏ một nút tại đỉnh stack (pop).Nếu ta muốn thêm một nút vào đỉnh stack thì trước đó ta phải kiểm tra xem stack đãđầy (full) hay chưa, nếu ta muốn loại bỏ một nút của stack thì ta phải kiểm tra stackcó rỗng hay không. Hình 4.1 minh họa sự thay đổi của stack thông qua các thao tácthêm và bớt đỉnh trong stack. 134 Giả sử ta có một stack S lưu trữ các kí tự. Trạng thái bắt đầu của stack đượcmô tả trong hình a. Khi đó thao tác: push(S,’G’) (hình b) push(S,’H’) (hình c) pop(S) (hình d) pop(S) (hình e) push(S,’I’) (hình f)(hình a) (hình b) (hình c) (hình d) (hình e) (hình f) H G G G I F F F F F F E E E E E E D D D D D D C C C C C C B B B B B B A A A A A A Có thể lưu trữ stack dưới dạng một vector S gồm n thành phần liên tiếpnhau. Nếu T là là địa chỉ của phần tử đỉnh stack thì T sẽ có giá trị biến đổi khi stackhoạt động. Ta gọi phần tử đầu tiên của stack là phần tử thứ 0, như vậy stack rỗngkhi T có giá trị nhỏ hơn 0 ta qui ước là -1. Stack tràn khi T có giá trị là n-1. Mỗi khimột phần tử được thêm vào stack, giá trị của T được tăng lên 1 đơn vị, khi mộtphần tử bị loại bỏ khỏi stack giá trị của T sẽ giảm đi một đơn vị.TOP T BOOTTOM S1 S2 S3 ... ST . . . 135 Để khai báo một stack, chúng ta có thể dùng một mảng một chiều. Phần tửthứ 0 là đáy stack, phần tử cuối của mảng là đỉnh stack. Một stack tổng quát là mộtcấu trúc gồm hai trường, trường top là một số nguyên chỉ đỉnh stack. Trường node:là một mảng một chiều gồm MAX phần tử trong đó mỗi phần tử là một nút c ủastack. Một nút của stack có thể là một biến đơn hoặc một cấu trúc phản ánh t ậpthông tin về nút hiện tại. Ví dụ, khai báo stack dùng để lưu trữ các số nguyên.#define TRUE 1#define FALSE 0#define MAX 100typedef struct { int top; int nodes[MAX];} stack;4.1.2- Các thao tác với stack Trong khi khai báo một stack dùng danh sách tuyến tính, chúng ta cần địnhnghĩa MAX đủ lớn để có thể lưu trữ được mọi đỉnh của stack. Một stack đã bị tràn(TOP = MAX- 1) thì nó không thể thêm vào phần tử trong stack, một stack rỗng thìnó không thể đưa ra phần tử. Vì vậy, chúng ta cần xây dựng thêm các thao tác kiểmtra stack có bị tràn hay không (full) và thao tác kiểm tra stack có rỗng hay không(empty).Thao tác Empty: Kiểm tra stack có rỗng hay không:int Empty(stack *ps) { if (ps ->top == -1)// liệu đây có phảI là danh sách liên kết không. Nếu khôngphảI thì cáI này nó có ý nghĩa gì đây? return(TRUE); return(FALSE);}Thao tác Push: Thêm nút mới x vào đỉnh stack và thay đổi đỉnh stack.void Push (stack *ps, int x) { if ( ps ->top == -1) { printf(“ stack full”); 136 ...