DATA STRUCTURE AND ALGORITHM
Stack
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NGĂN XẾP
Dr. Dao Nam Anh

Data Structure and Algorithm

1


Outline – Nội dung

•

Stack - Ngăn xếp
 Khái niệm Stack
 Các thao tác trên Stack
 Hiện thực Stack
 Ứng dụng của Stack

Data Structure and Algorithm

2


Resource - Reference
Slides of James Joshi , and Nor Bahiah Hj Ahmad,
edit by Dao Nam Anh. Major Reference:

•

Robert Sedgewick, and Kevin Wayne, “Algorithms”
Princeton University, 2011, Addison Wesley

•

Algorithm in C (Parts 1-5 Bundle)- Third Edition by
Robert Sedgewick, Addison-Wesley

•

Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.

•

Giải thuật và lập trình, Lê Minh Hoàng, Đại Học
Sư Phạm, 2002
Data Structure and Algorithm

3


Khái niệm Stack

•

Stack là một danh sách mà các đối tượng được
thêm vào và lấy ra chỉ ở một đầu của danh sách
(A stack is simply a list of elements with insertions and deletions
permitted at one end)


•

Việc thêm một đối tượng vào Stack hoặc lấy một
đối tượng ra khỏi Stack được thực hiện theo cơ
chế LIFO (Last In First Out - Vào sau ra trước)

•

Các đối tượng có thể được thêm vào Stack bất kỳ
lúc nào nhưng chỉ có đối tượng thêm vào sau
cùng mới được phép lấy ra khỏi Stack
Data Structure and Algorithm

4


Khái niệm Stack

•

Stack là một danh sách mà các đối tượng được
thêm vào và lấy ra chỉ ở một đầu của danh sách
(A stack is simply a list of elements with insertions and deletions
permitted at one end)

•

Việc thêm một đối tượng vào Stack hoặc lấy một
đối tượng ra khỏi Stack được thực hiện theo cơ

chế LIFO (Last In First Out - Vào sau ra trước)

•

Các đối tượng có thể được thêm vào Stack bất kỳ
lúc nào nhưng chỉ có đối tượng thêm vào sau
cùng mới được phép lấy ra khỏi Stack
Data Structure and Algorithm

5


Khái niệm Stack

•
•

Ví dụ: Chồng sách, chồng đĩa
LAST IN FIRST OUT (LIFO)
data structure.

Slide of Nor Bahiah Hj Ahmad, Software Engineering Department, FSKSM

Data Structure and Algorithm

6


Các thao tác Stack


•

Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

push

Data Structure and Algorithm

7


Các thao tác Stack

•

Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

push

Data Structure and Algorithm

8


Các thao tác Stack


•

Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

Data Structure and Algorithm

9


Các thao tác Stack

•

Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

pop

Data Structure and Algorithm

10


Các thao tác Stack

•


Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

pop

Data Structure and Algorithm

11


Các thao tác Stack

•

Stack hỗ trợ 2 thao tác chính:
 “Push”: Thao tác thêm 1 đối tượng vào Stack
 “Pop”: Thao tác lấy 1 đối tượng ra khỏi Stack

pop
push

Slide of James Joshi

Data Structure and Algorithm

12


Các thao tác Stack khác

Stack cũng hỗ trợ một số thao tác khác:

•
•

isEmpty(): Kiểm tra xem Stack có rỗng không
Top(): Trả về giá trị của phần tử nằm ở đầu Stack
mà không hủy nó khỏi Stack. Nếu Stack rỗng thì
lỗi sẽ xảy ra

Data Structure and Algorithm

13


Stack implementation - Triển khai ngăn xếp

•
•

Ngăn xếp là cấu trúc dữ liệu

•
•

Triển khai ngăn xếp như thế nào?

•
•


Stack is an abstract data structure

•

How to implement a general stack for all those types?

Đối tượng có thể là Integer, Double, String, hoặc,
Employee, Student

Bằng mảng hoặc bằng danh sách liên kết

Item can be Integer, Double, String, and also can be any data type, such as
Employee, Student…
 We can implement stack using array or linked list.

Data Structure and Algorithm

14


Stack implementation - Triển khai ngăn xếp
Array – mảng
• Kích thước cố định
• Kiểm tra còn chỗ không: isFull( ).
• Cần biến chỉ vị trí “top of a stack”.
• Rỗng khi Top = –1
Linked List – Danh sách liên kết
• Kích thước linh hoạt
• Cần con trỏ (pointer), trỏ về đỉnh ngăn xếp (top of
stack).


Data Structure and Algorithm

15


Array Implementation of Stack
Triển khai ngăn xếp bằng mảng

Data Structure and Algorithm

16


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
Thao tác trên Stack

•
•
•
•
•
•

createStack()
push(item)
pop( )
isEmpty( )


top =
2

isFull( )
stackTop()
Data Structure and Algorithm

17


Push() and pop() operations

stack empty

stack empty

Data Structure and Algorithm

18


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
Các hàm

1.
2.

Stack Empty : khi top bằng -1.
Push: Xếp vào

top = top + 1;
stack[top] = newitem;

3. Pop: Lấy ra
Item = stack[top]; hoặc là stackTop();
top = top – 1;

Data Structure and Algorithm

19


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
Khai báo Stack:
const int size = 100;
class stack
{
private : // data declaration
int top ;
char data[size] ;
public : // function declaration
void createStack();
void push(char) ; // insert operation
void pop() ; // delete operation
char stackTop() ; // get top value
bool isFull() ; // check if stack is Full
bool isEmpty(); // check if stack is empty
};


Data Structure and Algorithm

20


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng

•
•

Kích thước:100.
Khai báo:
stack aStack;

Data Structure and Algorithm

21


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
createStack()

void stack:: createStack();
{
top = -1;
}

Data Structure and Algorithm


22


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
isFull()

bool stack::isFull()
{
return (top == size-1 );
}

Data Structure and Algorithm

23


Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
bool isEmpty()

bool stack::isEmpty()
{
return ( top == -1 );
}

Data Structure and Algorithm

24



Array Implementation of Stack –
Triển khai ngăn xếp bằng mảng
push(newItem) operation : Insert item onto stack
 Top will be increased by 1.
top = top + 1;

 New item will be inserted at the top
data[Top] = newItem;

before push()

after push()
Data Structure and Algorithm

25