Chương 3.2. Ngăn xếp & Hàng đợi
Trần Minh Thái
Email: [email protected]
Website: www.minhthai.edu.vn
1
Nội dung

Trình bày khái niệm Ngăn xếp (Stack) và Hàng đợi (Queue)

Minh họa các ứng dụng

Các phương pháp xây dựng Stack và Queue
2
Khái niệm Stack
3
Khái niệm Stack

Gồm nhiều phần tử

Hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In, First Out)
Đỉnh
ngăn xếp
4
Thao tác cơ bản trên Stack

InitStack: khởi tạo Stack rỗng

IsEmpty: kiểm tra Stack rỗng?

IsFull: kiểm tra Stack đầy?


thuộc vào bộ nhớ
Stack – Sử dụng mảng
9
3
6
9 3 6
0 1 2 3 4 5 6 7 8 9
Stack
Top
9
Stack số nguyên – Sử dụng mảng
struct ttStack
{
int* StkArray; // mảng chứa các phần tử
int StkMax; // số phần tử tối đa
int StkTop; // vị trí đỉnh Stack
};
typedef struct ttStack STACK;
10
Stack số nguyên – Sử dụng mảng
bool InitStack(STACK& s, int MaxItems)
{
s.StkArray = new int[MaxItems];
if (s.StkArray == NULL)
return false;
s.StkMax = MaxItems;
s.StkTop = -1;
return true;
}
11

return false;
outitem = s.StkArray[s.StkTop];
s.StkTop ;
return true;
}
15
Bài tập

Viết hàm nhập và xuất Stack số nguyên

Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là
ký tự)

Khai báo cấu trúc và viết hàm tạo Stack từ chuỗi ký tự str (mỗi phần tử Stack là
một từ - từ cách nhau bởi khoảng trắng)
16
Stack – Ví dụ ứng dụng

Kiểm tra sự tương ứng của các cặp ngoặc đơn trong một biểu thức

( ( A + B ) / C ( A + B ) / C)

Đảo ngược một chuỗi ký tự

Cá Ăn Kiến  nếiK nĂ áC
? ?
17
Stack – Sử dụng DSLK
9
7

typedef struct tagSTACK_NODE
{
int Data;
tagSTACK_NODE *pNext;
} STACK_NODE;
typedef struct STACK
{
int StkCount;
STACK_NODE *StkTop;
};
20
Stack – Sử dụng DSLK

VD: Thực hiện một số thao tác trên stack
STACK s;
InitStack(s);
Push(s, 7);
Push(s, 4);
Pop(s, x); // x = ?
N
StkCnt StkTop
7
Data Link
4
Data Link
21
Stack số nguyên – Sử dụng DSLK
void InitStack(STACK &s)
{
s.StkTop = NULL;

s.StkCount++;
return true;
}
N
StkCnt StkTop
7
Data Link
4
Data Link
25