Ngăn xếp (Stack) – Hàng đợi (Queue)

1

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1

p Trình bày khái niệm Stack

và Queue

p Minh họa các ứng dụng

p Các phương pháp xây dựng

Stack và Queue dựa trên

những cấu trúc dữ liệu đã

biết

Ngăn xếp (Stack) – Hàng đợi (Queue)

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2

Nội dung trình bày

p Stack

p Ví dụ

p Định nghĩa

p Các thao tác cơ bản

p Xây dựng Stack

p Queue

p Ví dụ

p Định nghĩa

p Các thao tác cơ bản

p Xây dựng Queue

2

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3

Ngăn xếp (Stack)

Các Ví dụ về Stack

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4

Ngăn xếp (Stack)

Các Ví dụ về Stack

3

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5

Ngăn xếp (Stack)

Định nghĩa

p Stack là 1 cấu trúc:

p gồm nhiều phần tử có thứ tự

p hoạt động theo cơ chế “Vào sau – Ra

trước” (LIFO – Last In, First Out)

Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6

Ngăn xếp (Stack)

Định nghĩa

p Các thao tác cơ bản trên Stack:

p InitStack: khởi tạo Stack rỗng

p IsEmpty: kiểm tra Stack rỗng ?

p IsFull: kiểm tra Stack đầy ?

p Push: thêm 1 phần tử vào đỉnh

Stack, có thể làm Stack đầy

p Pop: lấy ra 1 phần tử từ đỉnh

Stack, có thể làm Stack rỗng

p Stack Top: kiểm tra

phần tử đầu Stack