1
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM1
pTrì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 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM2
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 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM3
Ngăn xếp (Stack)
Các Ví dụ về Stack
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM4
Ngăn xếp (Stack)
Các Ví dụ về Stack
3
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM5

Ngăn xếp (Stack)
Minh họa các thao tác
Thao tác Stack Top, Stack không thay đổi
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM10
Ngăn xếp (Stack)
Xây dựng Stack
p Có 2 cách để xây dựng Stack:
p Sử dụng mảng 1 chiều
p Sử dụng danh sách liên kết đơn
6
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM11
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng
5 2
StkArrayStkMaxStkTop
[0][1][2][3][4]
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM12
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng
// Giả sử Stack chứa các phần tử kiểu nguyên
// (int) -Khai báo cấu trúc Stack
typedef struct STACK {
int *StkArray; // mảng chứa các phần tử
intStkMax; // số phần tử tối đa
intStkTop;// vị trí đỉnh Stack
}
7
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM13
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng

Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM16
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng
p Thao tác “Push”: thêm 1 phần tử vào đỉnh Stack
int Push(STACK &s, int newitem)
{
if (IsFull(s))
return 0; // Stack đầy, không thêm vào được
s.StkTop++;
s.StkArray[s.StkTop] = newitem;
return 1;// Thêm thành công
}
9
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM17
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng
p Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack
int Pop(STACK &s, int &outitem)
{
if (IsEmpty(s))
return 0; // Stack rỗng, không lấy ra được
outitem = s.StkArray[s.StkTop];
s.StkTop--;
return 1;// Lấy ra thành công
}
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM18
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng mảng
p Thao tác “StackTop”: kiểm tra 1 phần tử ở đỉnh
Stack, không làm thay đổi Stack

intStkCount;
STACK_NODE*StkTop;
}
12
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM23
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng Danh sách liên kết
p VD. thực hiện 1 số thao tác trên Stack
STACK s;
InitStack(s);
Push(s, “green”);
Push(s, “blue”);
Pop(s, x);// x = ?
Pop(s, y);// y = ?
13
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM25
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng Danh sách liên kết
p Thao tác khởi tạo Stack rỗng:
void InitStack(STACK &s)
{
s.StkTop = NULL;
s.StkCount = 0;
}
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM26
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng Danh sách liên kết
p Thao tác “Kiểm tra Stack rỗng”:
int IsEmpty(const STACK &s)
{

s.StkCount++;
return 1;// Thêm thành công
}
15
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM29
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng Danh sách liên kết
Spring 2004Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM30
Ngăn xếp (Stack)
Xây dựng Stack, sử dụng Danh sách liên kết
p Thao tác “Pop”: lấy ra 1 phần tử từ đỉnh Stack
# Xóa 1 phần tử ở đầu danh sách
int Pop(STACK &s, int &outitem)
{
if (IsEmpty(s))return 0; // Stack rỗng, không lấy ra được
STACK_NODE *temp = s.StkTop;
outitem = temp->Data;
s.StkTop = temp->pNext;
delete temp;s.StkCount--;
return 1;// Lấy ra thành công
}