Bài 9. Ngăn xếp
Nội dung:
9.1. Khái niệm về stacks (7)
9.2. Các thao tác chính của stacks (9)
9.3. Các thao tác khác của stacks (9)
Tham khảo:
1. Data structures and Algorithms Stacks.htm
2. Kyle Loudon Mastering Algorithms, Chapter 6 Stacks and Queues
3. Elliz Horowitz –Fundamentals of Data Structures, Chapter 3 Stacks and
Queues
4. Deshpande Kakle –C and Data Structures, Chapter 19. Stacks and
Queues
5. Bài giảng TS Nguyễn Nam Hồng
PhD Ngo Huu Phuc, Le Quy Don Technical University
2
9.1. Khái niệm về stacks (1/7)
Có thể hình dung stack như một chồng đĩa. Với
chồng đĩa này, có thể nhìn thấy chiếc đĩa ở trên
cùng, các đĩa còn lại chưa nhìn thấy được.
Khi thêm một đĩa vào chồng đĩa (pushed), chiếc
đĩa này ở đỉnh của stack, có thể nhìn thấy.
Khi lấy di một đĩa từ stack (popped), có thể sử
dụng đĩa này, chiếc đĩa kế tiếp trở thành đỉnh của
stack.
PhD Ngo Huu Phuc, Le Quy Don Technical University
3
9.1. Khái niệm về stacks (2/7)
PhD Ngo Huu Phuc, Le Quy Don Technical University
4
9.1. Khái niệm về stacks (3/7)
Nguyên lý cơ bản của stack là Last In First Out
(LIFO), có nghĩa vào sau ra trước.
Với nguyên lý đó, chỉ có chiếc đĩa trên cùng stack
mới có thể nhìn thấy. Muốn nhìn thấy chiếc đĩa
thứ 3, cần lấy ra khỏi stack các đĩa thứ nhất và
thứ 2.
PhD Ngo Huu Phuc, Le Quy Don Technical University
5
