Bài giảng Cấu trúc dữ liệu - Chương 5: Ngăn xếp

Ch

ng 5:

ươ Ế NGĂN X P – HÀNG

Đ IỢ

(Stack Queue)

ộ

N i dung

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

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ộ

N i dung

 Ngăn x p (ế Stack)



ự ệ

ệ  Khái ni m Stack  Các thao tác trên Stack  Hi n th c Stack ụ Ứ ủ ng d ng c a Stack

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Stack Khái ni mệ

ố ượ ng đ c ượ thêm vào và

ộ  Stack là m t danh sách mà các đ i t ỉ ở ộ ầ ủ m t đ u c a danh sách ch

ấ l y ra (A stack is simply a list of elements with insertions and deletions permitted at one end)

 Vì th , thao tác trên Stack đ

ế ượ ơ ế ệ c th c hi n theo c ch LIFO

(Last In First Out Vào sau ra tr ự cướ )

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Stack – Các thao tác

 Stack h tr 2 thao tác chính:

ố ượ

ng vào Stack ỏ ng ra kh i

Thêm 1 đ i t L yấ 1 đ i t

 Push:  Pop: Stack  Ví d :ụ

ỗ ợ

5 2 3 4



ể

ỗ

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

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

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự Stack – Hi n th c Stack (Implementation of a Stack)

Cấp phát động!

Kích thước stack khi quá thiếu, lúc quá thừa

Push/Pop khá dễ dàng

Push / Pop khá phức tạp

ề ả M ng 1 chi u Danh sách LK

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Có th t o m t Stack b ng cách khai báo m t

ề ả ằ ộ m ng 1 chi u

ầ ử

ố ừ

ể ứ ố

i đa N ph n t

ế 0 đ n N1

đánh s t ỉ ố

ụ i đa là N (ví d : N =1000) ể ạ ớ v i kích th ộ ướ ố c t

ẽ đ nh Stack s có ch s là

ư ậ ả ầ

 Stack có th ch a t ầ ử ằ ở ỉ n m ể ế ố và 1 bi n s nguyên struct Stack {

top  Ph n t ề , ộ m ng 1 chi u  Nh v y, đ khai báo m t Stack, ta c n m t ỉ ố ủ ỉ ế t ch s c a đ nh Stack: ộ top cho bi

DataType list[N]; int top;

};

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Các hàm c n cài đ t:



ở ạ



Init( Stack &s ): Kh i t o Stack isEmpty( Stack s )

ề

ướ

i h n kích th

 Push( Stack &s , DataType x )  Pop( Stack &s )  Top( Stack &s ) ặ ằ ả  Khi cài đ t b ng m ng 1 chi u, Stack b gi ự

ầ

ị ớ ạ ụ

ệ

ầ

ộ nên c n xây d ng thêm m t thao tác ph cho Stack:  isFull(): Ki m tra xem Stack có đ y ch a, vì khi Stack đ y, vi c

ọ ế

ể g i đ n hàm

ẽ ị ỗ i

Push() s b l

ầ ặ

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Kh i t o Stack:

ở ạ

void Init (Stack &s) {

s.top = 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ể

 Ki m tra Stack có r ng hay không: ả ề

ả ề

i: hàm tr v 0

ỗ ỗ  R ng: hàm tr v 1 ượ ạ  Ng c l

int isEmpty(Stack s) {

if ( s.top==0 )

return 1; // stack rỗng

else

return 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ể ầ

 Ki m tra Stack có đ y hay không: ả ề

ả ề

ầ  Đ y: hàm tr v 1 ượ ạ  Ng c l

i: hàm tr v 0

int isFull(Stack s) {

if (s.top>=N)

return 1;

else

return 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Thêm m t ph n t

ầ ử ộ x vào Stack

void Push (Stack &s, DataType x) {

ư ầ

if (!isFull(s)) // stack ch a đ y {

s.list[s.top] = x; s.top++;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ầ ử ấ ộ  L y m t ph n t ỏ ra kh i Stack

DataType Pop(Stack &s) {

DataType x; if (!isEmpty(s)) // stack không r ngỗ {

s.top--; x = s.list[s.top];

} return x;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Xem ph n t

ầ ử ở ỉ đ nh Stack

DataType Top(Stack s) {

DataType x; if (!isEmpty(s)) // stack không r ngỗ {

x = s.list[s.top-1];

} return x;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

Nh n xét: ậ

ề

 Các thao tác trên đ u làm vi c v i chi phí O(1)  Vi c cài đ t Stack thông qua m ng m t chi u đ n gi n

ệ ớ ả ệ ề ả ặ ơ ộ

ệ ả

 Tuy nhiên, h n ch l n nh t c a ph

ế ớ ươ ặ và khá hi u qu ạ ng án cài đ t này là

ự ế

ầ

ớ

ể

 Giá tr c a N có th quá nh so v i nhu c u th c t

ặ ho c

ị ủ ớ ẽ

ộ

ớ

ỏ quá l n s làm lãng phí b nh

ớ ạ ướ ủ gi ề i h n v kích th ấ ủ c c a Stack (N)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Stack dùng DSLK (Implementation of a Stack using Linked List)

 Có th t o m t Stack b ng cách s d ng m t danh sách liên

ử ụ ằ ộ ộ

 Khai báo các c u trúc:

ể ạ ế ơ k t đ n (DSLK) ấ

struct Node {

DataType data; Node *pNext;

}; struct Stack {

Node *top;

};

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

(tt.)

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Các hàm c n cài đ t:



ở ạ

Init( Stack &s ): Kh i t o Stack



isEmpty( Stack s )

 Push( Stack &s , DataType x )

 Pop( Stack &s )

 Top( Stack &s )

ầ ặ

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

(tt.)

Hi n th c Stack dùng DSLK (Implementation of a Stack using Linked List)

 Kh i t o Stack:

ở ạ

void Init( Stack &s ) {

s.top = NULL;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

(tt.)

Hi n th c Stack dùng DSLK (Implementation of a Stack using Linked List)

 Ki m tra xem Stack có r ng không:

ỗ ể

int isEmpty ( Stack s ) {

return s.top == NULL ? 1 : 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

(tt.)

Hi n th c Stack dùng DSLK (Implementation of a Stack using Linked List)

 Thêm m tộ ph nầ tử vào Stack:

void Push ( Stack &s, DataType x ) {

Node *p = new Node; if ( p==NULL ) { cout<<“Khong du bo nho”;

return; }

p>data = x; Thêm ph n t p>pNext = NULL; if (s.top==NULL)

// if (isEmpty(s))

s.top = p;

else{

p>pNext = s.top; s.top = p;

}

ầ ử ầ vào đ u danh sách

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

(tt.)

Hi n th c Stack dùng DSLK (Implementation of a Stack Using Linked List)

ấ ầ ử ỏ ra kh i Stack:

ộ  L y m t ph n t DataType Pop ( Stack &s ) {

if ( s.top==NULL ){

cout<<"Stack rỗng"; return 0;

ấ ầ ử ở ầ đ u danh sách

} DataType x; L y và xóa ph n t Node *p = s.top; s.top = s.top->pNext; x = p->data; delete p; return x;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

(tt.)

Hi n th c Stack dùng DSLK (Implementation of a Stack Using Linked List)

ầ ử ở ỉ  Xem ph n t đ nh Stack: DataType Top ( Stack s ) {

if ( s.top==NULL ){

cout<<"Stack rỗng"; return 0;

} DataType x; x = s.top->data; return x;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ụ

Ứ Stack ng d ng

ự truy

ạ ữ ệ ữ ữ ợ ư  Stack thích h p l u tr các lo i d li u mà trình t ự ư c v i trình t

ấ xu t ng ộ ố ứ ượ ớ l u tr ụ  M t s ng d ng c a Stack:

ủ ụ

ị  Trong trình biên d ch (thông d ch), khi th c hi n các th t c,

ườ

c s d ng đ l u môi tr

Stack đ

ệ ủ ụ ng c a các th t c ế ồ ị

ể ư ộ ố

ả

ủ

ự ủ ư i m t s bài toán c a lý thuy t đ th (nh

ượ ử ụ  L u d li u khi gi

ng đi)



tìm đ Ứ

ể

ư ữ ệ ườ ứ ụ ng d ng trong các bài toán tính toán bi u th c ử ệ  Kh đ qui  …

ủ ị

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ụ

Ứ Stack ng d ng

ổ ố ừ ơ ố

ơ ố

ậ

Bài t p: đ i s t

c s 10 sang c s x

ụ

2 57 1 28 2 0 14 2 0 7 2 1 3 2 1 1 2 1 0

Ví d : 57 = ??? 57 = 1110012

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

void main() {

Stack s;

int coso, so, sodu;

ế

ậ ố ầ ậ ơ ố ầ ế ể Init(s); ể // Nh p s c n chuy n vào bi n so … // Nh p c s c n chuy n vào bi n coso…

while (so != 0) {

sodu = so % coso; Push (s, sodu); // push so du vao stack so = so/coso;

ả

} ế cout<<"K t qu : "; while ( !isEmpty(s) )

cout<

} ợ ế ươ ng 5: Ngăn x p – Hàng đ i

ụ

Ứ Stack ng d ng

ọ

gi a x=a[(l+r) / 2]

ằ

ủ ụ ể ử ệ

ộ ộ

ầ ử

ề

ệ

ự thì th c hi n:

ầ ử

ề

ệ

Ví d : th t c Quick_Sort dùng Stack đ kh đ qui:  B c 1. l=1; r=n;  B c 2. Ch n ph n t  B c 3. Phân ho ch (l, r) thành (l1, r1) và (l2, r2) b ng cách xét:

ự thì th c hi n:

ướ

c 2

ấ ế  l = l1  r = r1  Quay lên b ượ ạ i c l

 Ng

ế

ỏ

ỗ

ướ

ượ

 L y (l, r) ra kh i Stack, n u Stack khác r ng thì quay lên b

c 2, ng

ừ

ấ ạ i thì d ng

ụ ướ ầ ử ữ ướ ạ ướ (cid:0) x ế  y thu c (l1, r1) n u y ượ ạ  y thu c (l2, r2) ng i c l ạ ế ướ  B c 4. N u phân ho ch (l2, r2) có nhi u h n 1 ph n t  C t (l2, r2) vào Stack  N u (l1, r1) có nhi u h n 1 ph n t

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ụ

Ứ Stack ng d ng

 Thuật toán Ba Lan ngược

 Định nghĩa RPN:

 Biểu thức toán học trong đó các toán tử được viết sau toán

hạng và không dùng dấu ngoặc

 Phát minh bởi Jan Lukasiewics một nhà khoa học Ba Lan

vào những năm 1950

(Reverse Polish Notation – RPN)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ậ

ượ

Thu t toán Ba Lan ng

c

RPN

vi vi

ử ế sau toán h ngạ ử ế tr

cướ toán

t t

toán t

ử ế gi aữ toán h ngạ

Prefix

toán t Postfix (RPN): Prefix : toán t h ngạ Infix Examples: Infix A + B A * B + C A * (B + C) A - (B - (C - D)) A - B - C - D

RPN (Postfix) A B + A B * C + A B C + * A B C D - - - A B - C - D - + A B + * A B C * A + B C - A - B - C D - - - A B C D

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ượ

ứ

ể

L

ỹ

ng giá bi u th c RPN ạ ậ g ch d

K thu t ướ : i

ệ ừ ả ủ ứ ế ể ặ trái sang ph i c a bi u th c cho đ n khi g p toán

1. Duy t t .ử t

ướ ử ế ợ c toán t và k t h p chúng

ướ ử ằ ạ 2. G ch d b ng toán t ạ i 2 toán h ng ngay tr trên

ặ ặ ạ ứ ể ế i cho đ n h t bi u th c.

ế 3. L p đi l p l Ví d ụ 2*((3+4)(56))

(cid:0) (cid:0) (cid:0) (cid:0) 2 3 4 + 5 6 - - * 2 3 4 + 5 6

(cid:0)

(cid:0) (cid:0) - - * 2 7 5 6 - - * 2 7 5 6 - - * 2 7 -1 - * 2 7 -1 - * (cid:0) 2 8 * (cid:0) 2 8 * (cid:0)

16 29

ể

ị

Dùng Stack đ tính giá tr RPN

ở ạ ỗ . 1. Kh i t o Stack r ng

ứ ế ế ể ặ 2. L p cho đ n khi k t thúc bi u th c:

ầ ử ủ ọ Đ c 1 ph n t ứ ế c a bi u th c

ế ư ầ ử toán h ng ạ N u ph n t là thì đ a vào Stack.

Ng ượ ạ c l i (là phép toán):

ầ ử ấ L y ra 2 ph n t trong Stack.

ầ ử ừ ấ ụ Áp d ng phép toán cho 02 ph n t v a l y ra.

ư ế ả Đ a k t qu vào Stack.

ầ ử ố ị ủ ứ ủ ể 3. Giá tr c a bi u th c chính là ph n t cu i cùng c a Stack.

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

2*((3+4)-(5-6))

Example: 2 3 4 + 5 6 - - *

Push 2 Push 3 Push 4 Read +

4 3 2

3 + 4 = 7

Pop 4, Pop 3,

Push 7 Push 5 Push 6 Read -

6 5 7 2

5 - 6 = -1

Pop 6, Pop 5,

Push -1 Read -

-1 7 2

7 - -1 = 8

Pop -1, Pop 7,

Push 8 Read *

8 2

2 * 8 = 16

Pop 8, Pop 2,

Push 16

ể

Chuy n Infix thành Postfix

ở ạ ứ ỗ

1. Kh i t o Stack r ng (ch a các phép toán) ế ứ ể ế ặ 2. L p cho đ n khi k t thúc bi u th c:

ọ ầ ử ủ ầ ử ứ (01 ph n t ể có th là Đ c 01 ph n t

ế ế c a bi u th c ằ h ng, bi n, phép toán, “)” hay “(” )

ế ầ ử là:

ầ ử ủ ế ặ c a Stack ra cho đ n khi g p

N u ph n t ư 2.1 “(”: đ a vào Stack. ấ 2.2 “)”: l y các ph n t “(” trong Stack.

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ể

Chuy n Infix thành Postfix (tt.)

ộ 2.3 M t phép toán:

ộ ư ế

ư phép toán có đ u : đ a vào Stack. ầ ử ở ầ ơ tiên cao h n ph n t

+ * / N u ế Stack r ngỗ : đ a vào Stack. ỗ N u Stack khác r ng và đ u Stack ỗ N u Stack khác r ng và phép

ế ấ ơ ư toán có đ ộ : đ u Stack u tiên th p h n ho c b ng ph n t

ệ ớ

ph n t ặ ế ằ

ầ ử ở ầ ặ ằ ầ ử ừ ấ t Stack ra; l y ph n t ặ ạ i vi c so sánh v i sau đó l p l ầ ử ở ầ đ u Stack. ả ư ế 2.4 H ng ho c bi n: đ a vào k t qu . ấ ế ấ ả ầ ử ủ t c các ph n t c a Stack ra. 3. L y h t t

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ậ

ượ

Thu t toán Ba Lan ng

ộ ư c Đ u tiên

 + , -  *, /  ^

1 2 3

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

(A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F)) (A+B*C)/(D-(E-F))

Output A

AB

* + (

ABC

Example: Push ( Display A Push + Display B Push * Display C Read ) + (

Pop *, Display *, Pop +, Display +, Pop (

(

ABC* ABC*+

ABC*+D

ABC*+DE

- ( - ( /

ABC*+DEF

Push / Push ( Display D Push - Push ( Display E Push - Display F Read )

Pop -, Display -, Pop (

ABC*+DEF-

Pop -, Display -, Pop (

- ( /

Read ) Pop /, Display /

ABC+DEF-- ABC+DEF--/

Ví dụ

A + (B*C - (D/E^F) * G) * H

S=[];

KQ=“”

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H A + (B*C (D/E^F) * G) * H

S=[+]; S=[];

KQ=“A” KQ=“”

A + (B*C - (D/E^F) * G) * H

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H A + (B*C (D/E^F) * G) * H A + (B*C (D/E^F) * G) * H A + (B*C (D/E^F) * G) * H A + (B*C (D/E^F) * G) * H

S=[+(*]; S=[+]; S=[+(];

KQ=AB KQ=ABC KQ=A

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+(]; S=[+(]; S=[+(*];

KQ=ABC* KQ=ABC

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((]; S=[+(];

KQ=ABC*

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((];

KQ=ABC*D KQ=ABC*

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((/]; S=[+((];

KQ=ABC*D

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((/];

KQ=ABC*DE KQ=ABC*D

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((/^]; S=[+((/];

KQ=ABC*DE

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+((/^];

KQ=ABC*DEF KQ=ABC*DE

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+(]; S=[+((/^]; S=[+((]; S=[+((/];

KQ=ABC*DEF^/ KQ=ABC*DEF^ KQ=ABC*DEF

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+(*]; S=[+(];

KQ=ABC*DEF^/

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+(*];

KQ=ABC*DEF^/G KQ=ABC*DEF^/

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+(]; S=[+]; S=[+(*]; S=[+(];

KQ=ABC*DEF^/G* KQ=ABC*DEF^/G KQ=ABC*DEF^/G*

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+*]; S=[+];

KQ=ABC*DEF^/G*

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[+*];

KQ=ABC*DEF^/G*H KQ=ABC*DEF^/G*

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Ví dụ

A + (B*C (D/E^F) * G) * H

S=[]; S=[+*];

KQ=ABCDEF^/GH+ KQ=ABCDEF^/GH KQ=ABCDEF^/GH+

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ộ

N i dung

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

 Khái niệm Queue

 Các thao tác trên Queue

 Hiện thực Queue

 Ứng dụng Queue

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Queue Khái ni mệ

 Queue là m t danh sách mà các đ i t

ở

ộ ộ ầ ủ ố ượ ng đ ở ộ ầ

ượ thêm vào c ủ ấ m t đ u c a danh sách và m t đ u kia c a danh l y ra sách (A queue is also a list of elements with insertions permitted at one end and deletions permitted from the other end)

ệ ộ ố ượ ng luôn di n ra ở cu iố Queue và vi c ệ

 Vi c thêm m t đ i t ấ l y ra m t đ i t

ộ ố ượ ễ

 Vì th , thao tác trên Queue đ

ế

ượ FIFO (First In First Out Vào tr ễ ở đ uầ Queue ng luôn di n ra ự ơ ế ệ c th c hi n theo c ch ướ ) ướ c c ra tr

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Queue Khái ni mệ

Imaging

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Queue – Các thao tác

 Queue h tr 2 thao tác chính:

ố rear) Queue

ố ượ ố ượ

ng vào cu i ( đ u ( ng

ở ầ front) Queue

 EnQueue(): Thêm đ i t  DeQueue(): L yấ đ i t

 Ví d :ụ

ỗ ợ

Front Rear

5 3 2 4



ể

ỗ

isEmpty(): Ki m tra xem Queue có r ng không

đ u Queue mà không

ị ỗ

ả ề  Front(): Tr v giá tr ph n t ế ủ h y nó. N u Queue r ng thì l

ầ ử ằ ở ầ n m ỗ ẽ ả i s x y ra

ỗ ợ  Queue còn h tr các thao tác:

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự Queue – Hi n th c Queue (Implementation of a Queue)

Cấp phát động!

Kích thước queue khi quá thiếu, lúc quá thừa

EnQueue/DeQueu e khá dễ dàng

EnQueue/DeQueu e khá phức tạp

ề ả M ng 1 chi u Danh sách LK

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

ự

ộ

ầ ử

ờ ờ

ồ

ra thì đ ng th i d i các ô phía sau nó

A B C D

B C D

B C D E

Ban đầu

Thêm vào 1 phần tử

Lấy ra 1 phần tử: dời tất cả về trước để trống chỗ thêm vào

ệ  Hai cách hi n th c: ấ  Khi l y m t ph n t ộ ị lên m t v trí:

ầ ử

ộ

ấ

ờ

 Khi l y m t ph n t

ra thì không d i ô lên (xoay vòng):

A B C D

B C D

Ban đầu

Lấy ra 1 phần tử

Thêm vào 1 phần tử

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Tr ngạ thái Queue lúc bình th

 Tr ngạ thái Queue lúc xoay vòng:

ngườ :

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

A 12 1 4 2 5

Cách dùng m ng 2ả

DeQueue(Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

A 1 4 2 5

Cách dùng m ng 2ả

DeQueue(Q) EnQueue(5,Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

A 1 4 2 5 5

Cách dùng m ng 2ả

DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

Cách dùng m ng 2ả

A 1 4 2 5 5 5

DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) DeQueue(Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

Cách dùng m ng 2ả

A 2 5 5 5

ươ

DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) DeQueue(Q) DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), ………. ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

Cách dùng m ng 2ả

A 5 5 5 5

ươ

DeQueue(Q) EnQueue(5,Q) EnQueue(5,Q) DeQueue(Q) DeQueue(Q) DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), ………. ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

A 5 5 5 5

Cách dùng m ng 2ả

DeQueue(Q), EnQueue(5,Q), DeQueue(Q), EnQueue(5,Q), ……….

Empty Queue Full Queue

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

a. Cài đặt hàng đợi bằng mảng:

 Giả sử một mảng a[8] chứa các phần tử của hàng đợi.

Front

Rear

9 10 2 17 19 25 30

Rear

10 2 17 19 25 30

1 2 3 4 5 6 7

Rear

10 2 17 19 25 30 50

1 2 3 4 5 6 7

ầ ử

thì

ầ ử ộ Xóa m t ph n t Front tăng lên 1

ộ Thêm m t ph n t Rear tăng lên 1

ướ

ế N u thêm ti p m t ầ ử ph n t Nên ph i t nh ti n tr

ộ ế ị hàng b tràn . ế ả ị c khi thêm vào hàng

ầ ử Các ph n t ủ hàng c a ư ượ đ a đ vào m ng ả a[8]

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Nhận xét:

 Khi front = rear thì queue có thể đầy hoặc rỗng  Không thể phân biệt được queue đầy hoặc rỗng trong

trường hợp này

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Để khai báo m tộ Queue, ta c n khai báo

front, rear cho bi

tế chỉ số c aủ đ uầ và cu iố c aủ

 1 m ngả m tộ chi uề list, ố  2 s nguyên hàng đ iợ ,

tế kích th

cướ t

ầ :

 h ngằ số N cho bi ợ  Hàng đ i có th đ

iố đa c aủ Queue ụ ể ư c khai báo c th nh sau:

ể ượ

struct Queue {

DataType list[N]; int front, rear;

};

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Các hàm c n cài đ t:

 Init(Queue &q)

 isEmpty(Queue q)

 EnQueue(Queue &q, DataType x)

 DeQueue(Queue &q)

 Front(Queue q)

ặ ầ

ề ộ ả  Do khi cài đ t b ng m ng m t chi u, Queue b gi



ể

ầ

ư isFull(): Ki m tra xem Queue có đ y ch a

ặ ằ ầ ướ ự ộ ị ớ ạ i h n ụ c nên c n xây d ng thêm m t thao tác ph : kích th

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Kh i t o Queue:

ở ạ

void Init(Queue &q) {

q.front = q.rear = 0;

}

 Ki m tra xem Queue có r ng không:

ỗ ể

int isEmpty(Queue q) {

if ( q.front==q.rear && q.rear==0 )

return 1;

if (q.front == q.rear) return 1; return 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Ki m tra xem Queue có đ y hay không:

ể

ầ int isFull(Queue q) { if (q.front == q.rear) return 1; return 0; }

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Giải quyết trường hợp điều kiện Queue đầy hoặc rỗng:

1. Không để Queue đầy

 Tăng kích thước mảng khi thêm mà không còn chỗ

1. Định nghĩa thêm 1 biến để tính số phần tử hiện hành

trong Queue (NumElements)

 Mỗi khi thêm 1 pt vào Queue thì NumElements++

 Mỗi khi lấy 1 pt khỏi Queue thì NumElements—

 Queue rỗng khi (front = rear và NumElements=0)

 Queue đầy khi (front = rear và NumElements!=0)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Thêm m t ph n t

ầ ử ộ ố x vào cu i Queue:

int EnQueue(Queue &q, DataType x) {

if (isFull(q))

ượ

ầ c vì Queue đ y

return 0; // không thêm đ

q.rear=0;

q.list[q.rear] = x; q.rear++; if (q.rear==N) return 1;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 L y ph n t

ầ ử ấ ỏ ra kh i Queue:

DataType DeQueue(Queue &q) {

if (isEmpty(q)){

cout<<“Queue rong”; return 0;}

DataType t = q.list[q.front]; q.front++; if (q.front==N) q.front = 0; return t;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Xem thông tin c a ph n t

ủ ầ ử ở ầ đ u Queue:

DataType Front(Queue q) {

if (isEmpty(q)) {

cout<<“Queue rong”; return 0;

} return q.list[q.front];

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

ể ể ử ụ ễ ơ ằ  Có th bi u di n Queue b ng cách s d ng DSLK đ n

 pHead s là ẽ front, pTail s là ẽ rear

 pHead s là ẽ rear, pTail s là ẽ front

rear

front

rear

ự ố ọ  Có 2 l a ch n (cách nào t ấ t nh t?):

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

 Khai báo các c u trúc:

ấ

struct Node {

DataType data; Node *pNext;

}; struct Queue {

Node front, rear;

};

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

 Kh i tở

ạ ỗ o Queue r ng:

void Init(Queue &q) {

q.front = q.rear = NULL;

 Ki m tra hàng đ i r ng :

} ợ ỗ ể int isEmpty(Queue &q) {

if ( q.front==NULL )

else

return 1; return 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

 Thêm m t ph n t

ầ ử ộ ố p vào cu i Queue:

int EnQueue(Queue &q, DataType x) {

Node *p = new Node; if (p==NULL) return 0; //Khong du bo nho p->pNext = NULL; p->data = x; if (q.front==NULL) // TH Queue rỗng q.front = q.rear = p; else {

q.rear->pNext = p; q.rear = p;

} return 1;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

 L y ph n t

ầ ử ấ ỏ ra kh i Queue:

DataType DeQueue(Queue &q) {

if (isEmpty(q)) {

cout<<“Queue rong”;return 0;

} Node *p = q.front; DataType x = p->data; q.front = q.front->pNext; if ( q.front==NULL ) q.rear = NULL; delete p; return x;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Xem thông tin c a ph n t

ủ ầ ử ở ầ đ u Queue:

DataType Front(Queue q) {

if (isEmpty(q)) {

cout<<“Queue rong”; return 0;

} return q.front->data;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

Hi n th c Queue dùng DSLK (Implementation of a Queue using Linked List)

Nh n xét: ậ

 Các thao tác trên Queue bi u di n b ng danh sách liên k t

ể ế ễ ằ

ệ ớ

ả ầ ử ố cu i xâu, thao tác Dequeue

làm vi c v i chi phí O(1) ế  N u không qu n lý ph n t ộ ứ ạ ẽ s có đ ph c t p O(n)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ụ

Ứ Queue ng d ng

 Queue có thể đ

 Bài toán “s nả xu tấ và tiêu th ”ụ ( ngứ d ngụ trong các hệ đi uề

hành song song)

 Bộ đ mệ (ví dụ: Nh nấ phím (cid:0)

Bộ đ mệ (cid:0)

CPU xử lý)

 Xử lý các l nhệ trong máy tính ( ngứ d ngụ trong HĐH, trình biên

d chị

), hàng đ iợ các ti nế trình chờ đ

cượ xử lý, ….

cượ sử d ngụ trong m tộ số bài toán:

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

 Có th t o m t Queue b ng cách s d ng m t m ng 1

ể ạ ằ

ộ ể a ầ ử ộ ả ử ụ ề ớ ầ ử n1 k v i ph n t

ề chi u theo ki u xoay vòng (coi ph n t a0)

(cid:0) ứ ố i đa N ph n tầ ử

 Ph n t  Ph n t

 The limitation of an array implementation is that the queue cannot

grow and shrink dynamically as per the requirement

ợ Hàng đ i ch a t ầ ử ở ầ ầ ử ở ố ợ ẽ đ u hàng đ i s có ch s ợ ẽ cu i hàng đ i s có ch s ỉ ố front ỉ ố rear

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

A 12 1 4 2 5

Cách dùng m ng 1ả

DeQueue(Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

A 1 4 2 5

Cách dùng m ng 1ả

DeQueue(Q)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

Cách dùng m ng 1ả

A 1 4 2 5

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

A 12 1 4 2 5

r f

A[2]

A[0] A[1]

Cách dùng m ng 2ả

Empty queue f=r

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

empty(Q): return (f = r)

Front(Q): if empty(Q) then error else return A[f]

Cách dùng m ng 2ả

A 1 4 2 5

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[N1]

A[0] A[1] A[2]

size(Q): if (r >= f) then return (rf) else return N(fr)

Cách dùng m ng 2ả

A 1 4 2 5

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Queue dùng m ng (Implementation of a Queue using Array)

r f

A[2]

A[N1]

A[0] A[1]

size(Q): if (r >= f) then return (rf) else return N(fr)

Cách dùng m ng 2ả

A 5 5 5 5

Bài giảng Cấu trúc dữ liệu - Chương 5: Ngăn xếp - Hàng đợi

Ch

ng 5:

ươ Ế NGĂN X P – HÀNG

Đ IỢ

(Stack ­ Queue)

ộ

N i dung

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ộ

N i dung

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Stack ­ Khái ni mệ

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

Stack – Các thao tác

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự Stack – Hi n th c Stack (Implementation of a Stack)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

void Init (Stack &s) {

s.top = 0;

}

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Ki m tra Stack có r ng hay không: ả ề

ả ề

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

 Ki m tra Stack có đ y hay không: ả ề

ả ề

ầ  Đ y: hàm tr v 1 ượ ạ  Ng c l

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

ệ

ự

ả

Hi n th c Stack dùng m ng (Implementation of a Stack using Array)

ươ

ợ ế ng 5: Ngăn x p – Hàng đ i

(Stack Queue)

Stack Khái ni mệ

Ứ Stack ng d ng

Ứ Stack ng d ng