Giải thuật và lập trình: §5. Ngăn xếp và hàng đợi
Giải phóng thời gian, khai phóng năng lực
NGĂN XẾP (STACK)
Ngăn xếp là một kiểu danh sách được trang bị hai phép toán bổ sung một phần tử vào cuối danh sách và loại bỏ một phần tử cũng ở cuối danh sách.
Có thể hình dung ngăn xếp như hình ảnh một chồng đĩa, đĩa nào được đặt vào chồng sau cùng sẽ nằm trên tất cả các đĩa khác và sẽ được lấy ra đầu tiên. Vì nguyên tắc"vào sau ra trước" đó, Stack còn có tên gọi là danh sách kiểu LIFO (Last In First Out) và vị trí cuối danh sách được gọi là đỉnh (Top) của Stack.
Mô tả Stack bằng mảng
Khi mô tả Stack bằng mảng:
Việc bổ sung một phần tử vào Stack tương đương với việc thêm một phần tử vào cuối mảng. Việc loại bỏ một phần tử khỏi Stack tương đương với việc loại bỏ một phần tử ở cuối mảng. Stack bị tràn khi bổ sung vào mảng đã đầy
Stack là rỗng khi số phần tử thực sự đang chứa trong mảng = 0.
program StackByArray;
const
max = 10000;
var
Stack: array[1..max] of Integer;
Last: Integer;
procedure StackInit; {Khởi tạo Stack rỗng}
begin
Last := 0;
end;
procedure Push(V: Integer); {Đẩy một giá trị V vào Stack}
begin
if Last = max then WriteLn('Stack is full') {Nếu Stack đã đầy thì không đẩy được thêm vào nữa}
else
begin
Inc(Last); Stack[Last] := V; {Nếu không thì thêm một phần tử vào cuối mảng}
end;
end;
function Pop: Integer; {Lấy một giá trị ra khỏi Stack, trả về trong kết quả hàm}
begin
if Last = 0 then WriteLn('Stack is empty') {Stack đang rỗng thì không lấy được}
else
begin
Pop := Stack[Last];
Dec(Last); {Lấy phần tử cuối ra khỏi mảng}
end;
end;
begin
StackInit;
<Test>; {Đưa một vài lệnh để kiểm tra hoạt động của Stack}
end.
Khi cài đặt bằng mảng, tuy các thao tác đối với Stack viết hết sức đơn giản nhưng ở đây ta vẫn chia thành các chương trình con, mỗi chương trình con mô tả một thao tác, để từ đó về sau, ta chỉ cần biết rằng chương trình của ta có một cấu trúc Stack, còn ta mô phỏng cụ thể như thế nào thì không cần phải quan tâm nữa, và khi cài đặt Stack bằng các cấu trúc dữ liệu khác, chỉ cần sửa lại các thủ tục StackInit, Push và Pop mà thôi.
Mô tả Stack bằng danh sách nối đơn kiểu LIFO
Khi cài đặt Stack bằng danh sách nối đơn kiểu LIFO, thì Stack bị tràn khi vùng không gian nhớ dùng cho các biến động không còn đủ để thêm một phần tử mới. Tuy nhiên, việc kiểm tra điều này rất khó bởi nó phụ thuộc vào máy tính và ngôn ngữ lập trình. Ví dụ như đối với Turbo Pascal, khi Heap còn trống 80 Bytes thì cũng chỉ đủ chỗ cho 10 biến, mỗi biến 6 Bytes mà thôi. Mặt khác, không gian bộ nhớ dùng cho các biến động thường rất lớn nên cài đặt dưới đây ta bỏ qua việc kiểm tra Stack tràn.
program StackByLinkedList;
type
PNode = ^TNode; {Con trỏ tới một nút của danh sách}
TNode = record; {Cấu trúc một nút của danh sách}
Value: Integer;
Link: PNode;
end;
var
Last: PNode; {Con trỏ đỉnh Stack}
procedure StackInit; {Khởi tạo Stack rỗng}
begin
Last := nil; end;
procedure Push(V: Integer); {Đẩy giá trị V vào Stack Û thêm nút mới chứa V và nối nút đó vào danh sách}
var
P: PNode; begin
New(P); P^.Value := V; {Tạo ra một nút mới}
P^.Link := Last; Last := P; {Móc nút đó vào danh sách}
end;
function Pop: Integer; {Lấy một giá trị ra khỏi Stack, trả về trong kết quả hàm}
var
P: PNode; begin
if Last = nil then WriteLn('Stack is empty')
else
begin
Pop := Last^.Value; {Gán kết quả hàm}
P := Last^.Link; {Giữ lại nút tiếp theo last^ (nút được đẩy vào danh sách trước nút Last^)}
Dispose(Last); Last := P; {Giải phóng bộ nhớ cấp cho Last^, cập nhật lại Last mới}
end;
end;
begin
StackInit;
<Test>; {Đưa một vài lệnh để kiểm tra hoạt động của Stack}
end.
HÀNG ĐỢI (QUEUE)
Hàng đợi là một kiểu danh sách được trang bị hai phép toán bổ sung một phần tử vào cuối danh sách (Rear) và loại bỏ một phần tử ở đầu danh sách (Front).
Có thể hình dung hàng đợi như một đoàn người xếp hàng mua vé: Người nào xếp hàng trước sẽ được mua vé trước. Vì nguyên tắc"vào trước ra trước" đó, Queue còn có tên gọi là danh sách kiểu FIFO (First In First Out).
Mô tả Queue bằng mảng
Khi mô tả Queue bằng mảng, ta có hai chỉ số First và Last, First lưu chỉ số phần tử đầu Queue còn Last lưu chỉ số cuối Queue, khởi tạo Queue rỗng: First := 1 và Last := 0;
Để thêm một phần tử vào Queue, ta tăng Last lên 1 và đưa giá trị đó vào phần tử thứ Last.
Để loại một phần tử khỏi Queue, ta lấy giá trị ở vị trí First và tăng First lên 1.
Khi Last tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, không thể đẩy thêm phần tử vào nữa.
Khi First > Last thì tức là Queue đang rỗng
Như vậy chỉ một phần của mảng từ vị trí First tới Last được sử dụng làm Queue.
program QueueByArray;
const
max = 10000;
var
Queue: array[1..max] of Integer;
First, Last: Integer;
procedure QueueInit; {Khởi tạo một hàng đợi rỗng}
begin
First := 1;
Last := 0;
end;
procedure Push(V: Integer); {Đẩy V vào hàng đợi}
begin
if Last = max then WriteLn('Overflow')
else
begin
Inc(Last);
Queue[Last] := V;
end;
end;
function Pop: Integer; {Lấy một giá trị khỏi hàng đợi, trả về trong kết quả hàm}
begin
if First > Last then WriteLn('Queue is Empty')
else
begin
Pop := Queue[First];
Inc(First);
end;
end;
begin
QueueInit;
<Test>; {Đưa một vài lệnh để kiểm tra hoạt động của Queue}
end.
Xem lại chương trình cài đặt Stack bằng một mảng kích thước tối đa 10000 phần tử, ta thấy rằng nếu như ta làm 6000 lần Push rồi 6000 lần Pop rồi lại 6000 lần Push thì vẫn không có vấn đề gì xảy ra. Lý do là vì chỉ số Last lưu đỉnh của Stack sẽ được tăng lên 6000 rồi lại giảm đến 0 rồi lại tăng trở lại lên 6000. Nhưng đối với cách cài đặt Queue như trên thì sẽ gặp thông báo lỗi tràn mảng, bởi mỗi lần Push, chỉ số cuối hàng đợi Last cũng tăng lên và không bao giờ bị giảm đi cả. Đó chính là nhược điểm mà ta nói tới khi cài đặt: Chỉ có các phần tử từ vị trí First tới Last là thuộc Queue, các phần tử từ vị trí 1 tới First - 1 là vô nghĩa.
Để khắc phục điều này, ta mô tả Queue bằng một danh sách vòng (biểu diễn bằng mảng hoặc cấu trúc liên kết), coi như các phần tử của mảng được xếp quanh vòng theo một hướng nào đó. Các phần tử nằm trên phần cung tròn từ vị trí First tới vị trí Last là các phần tử của Queue. Có thêm một biến n lưu số phần tử trong Queue. Việc thêm một phần tử vào Queue tương đương với việc ta dịch chỉ số Last theo vòng một vị trí rồi đặt giá trị mới vào đó. Việc loại bỏ một phần tử trong Queue tương đương với việc lấy ra phần tử tại vị trí First rồi dịch chỉ số First theo vòng.
Dùng danh sách vòng mô tả Queue
Lưu ý là trong thao tác Push và Pop phải kiểm tra Queue tràn hay Queue cạn nên phải cập nhật lại biến n. (Ở đây dùng thêm biến n cho dễ hiểu còn trên thực tế chỉ cần hai biến First và Last là ta có thể kiểm tra được Queue tràn hay cạn rồi)
program QueueByCList; const
max = 10000; var
Queue: array[0..max - 1] of Integer;
i, n, First, Last: Integer;
procedure QueueInit; {Khởi tạo Queue rỗng}
begin
First := 0;
Last := max - 1;
n := 0;
end;
procedure Push(V: Integer); {Đẩy giá trị V vào Queue}
begin
if n = max then WriteLn('Queue is Full')
else
end;
begin
Last := (Last + 1) mod max; {Last chạy theo vòng tròn}
Queue[Last] := V;
Inc(n);
end;
function Pop: Integer; {Lấy một phần tử khỏi Queue, trả về trong kết quả hàm}
begin
if n = 0 then WriteLn('Queue is Empty')
else
begin
Pop := Queue[First];
First := (First + 1) mod max; {First chạy theo vòng tròn}
Dec(n);
end;
end;
begin
QueueInit;
<Test>; {Đưa một vài lệnh để kiểm tra hoạt động của Queue}
end.
Mô tả Queue bằng danh sách nối đơn kiểu FIFO
Tương tự như cài đặt Stack bằng danh sách nối đơn kiểu LIFO, ta cũng không kiểm tra Queue tràn trong trường hợp mô tả Queue bằng danh sách nối đơn kiểu FIFO.
program QueueByLinkedList;
type
PNode = ^TNode; {Kiểu con trỏ tới một nút của danh sách}
TNode = record {Cấu trúc một nút của danh sách}
Value: Integer;
Link: PNode;
end;
var
First, Last: PNode; {Hai con trỏ tới nút đầu và nút cuối của danh sách}
procedure QueueInit; {Khởi tạo Queue rỗng}
begin
First := nil;
end;
procedure Push(V: Integer); {Đẩy giá trị V vào Queue}
var
P: PNode;
begin
New(P);
P^.Value := V; {Tạo ra một nút mới}
P^.Link := nil;
if First = nil then First := P {Móc nút đó vào danh sách}
else Last^.Link := P;
Last := P; {Nút mới trở thành nút cuối, cập nhật lại con trỏ Last}
end;
function Pop: Integer; {Lấy giá trị khỏi Queue, trả về trong kết quả hàm}
var
P: PNode;
begin
if First = nil then WriteLn('Queue is empty')
else
begin
Pop := First^.Value; {Gán kết quả hàm}
P := First^.Link; {Giữ lại nút tiếp theo First^ (Nút được đẩy vào danh sách ngay sau First^)}
end;
Dispose(First);
First := P; {Giải phóng bộ nhớ cấp cho First^, cập nhật lại First mới}
end;
begin
QueueInit;
<Test>; {Đưa một vài lệnh để kiểm tra hoạt động của Queue}
end.
Bài tập
Bài 1
Tìm hiểu cơ chế xếp chồng của thủ tục đệ quy, phương pháp dùng ngăn xếp để khử đệ quy.
Bài 2
Viết chương trình mô tả cách đổi cơ số từ hệ thập phân sang hệ cơ số R dùng ngăn xếp.
Bài 3
Hình 13 là cơ cấu đường tàu tại một ga xe lửa
Di chuyển toa tàu
Ban đầu ở đường ray A chứa các toa tàu đánh số từ 1 tới n theo thứ tự từ trái qua phải, người ta muốn chuyển các toa đó sang đường ray C để được một thứ tự mới là một hoán vị của (1, 2, …, n) theo quy tắc: chỉ được đưa các toa tàu chạy theo đường ray theo hướng mũi tên, có thể dùng đoạn đường ray B để chứa tạm các toa tàu trong quá trình di chuyển.
a. Hãy nhập vào hoán vị cần có, cho biết có phương án chuyển hay không, và nếu có hãy đưa ra cách chuyển:
Ví dụ: n = 4 thì thứ tự cần có là (1, 4, 3, 2)
1)A → C; 2)A → B; 3)A → B; 4)A → C; 5)B → C; 6)B → C
b. Những hoán vị nào của thứ tự các toa là có thể tạo thành trên đoạn đường ray C với luật di chuyển như trên.
Bài 4
Tương tự như bài 3, nhưng với sơ đồ đường ray sau:
Di chuyển toa tàu (2)
Giải phóng thời gian, khai phóng năng lực