ươ

ế

ề

ả

ổ ứ Ch ng 3. T  ch c ngăn x p  ợ (Stack) & Hàng đ i (Queue) trên  ộ m ng m t chi u

Trần Minh Thái Email: minhthai@huflit.edu.vn 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)

• Các thao tác trên Ngăn xếp và Hàng đợi

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

2

Ngăn xếp

• Ngăn xếp là gì?

• Cách khai báo cấu trúc ngăn xếp dùng mảng một chiều?

• Các ứng dụng

• Cài đặt

3

Ví dụ về Ngăn xếp

Thành phần được lấy ra đầu tiên?

4

Khái niệm Stack

• Gồm nhiều phần tử lưu trữ theo thứ tự

• Hoạt động theo cơ chế “Vào sau – Ra trước” (LIFO – Last In,

First Out)

ỉ Đ nh  ngăn  x pế

5

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?

Push

Pop

• Push: thêm 1 phần tử vào Stack

• Pop: lấy ra 1 phần tử khỏi Stack

6

Thao tác Push vào Stack

P U S H

Top

7

Thao tác Pop khỏi stack

Top

P O P

8

Stack – Sử dụng mảng

Top

C B A

Stack

A B C 2 1 0

3

4

5

6

7

8

9

Top

9

Ngăn xếp – Sử dụng mảng

Top

Top Top

Top

Top B A C B A D C B A D C B A E D C B A

Top A

10

Ví dụ, Ngăn xếp chứa 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;

11

Ngăn xếp số nguyên – Sử dụng mảng

int InitStack(STACK& s, int MaxItems)

{

s.StkArray = new int[MaxItems];

if (s.StkArray == NULL)

return 0;

s.StkMax = MaxItems;

s.StkTop = -1;

return 1; //Khởi tạo thành công

}

12

Ngăn xếp số nguyên – Sử dụng mảng

int IsEmpty(const STACK &s)

{

if (s.StkTop==-1)

return 1;

return 0;

}

13

Stack số nguyên – Sử dụng mảng

int IsFull(const STACK &s)

{

if (s.StkTop==s.StkMax-1)

return 1;

return 0;

}

14

Stack số nguyên – Sử dụng mảng

int Push (STACK &s, int newitem)

{

if (IsFull(s)==1)

return 0;

s.StkTop++;

s.StkArray[s.StkTop] = newitem;

return 1;

}

15

Stack số nguyên – Sử dụng mảng

int Pop(STACK &s, int &outitem)

{

if (IsEmpty(s))

return 0;

outitem = s.StkArray[s.StkTop];

s.StkTop--;

return 1;

}

16

Bài tập

Viết hàm nhập, xuất Stack số nguyên dương sao cho:

• Cho phép người dùng lần lượt nhập vào Stack các số nguyên

dương

• Nếu nhập vào giá trị <=0 thì kết thúc quá trình nhập

17

Stack – Ứ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

18

Stack – Ứng dụng

• Lưu vết trong thuật toán “back-tracking” (theo dõi dấu vết)

• Tính giá trị biểu thức toán học

• Khử đệ quy

• …

19

Bài toán tháp HaNoi

Towers of Hanoi

Towers of Hanoi

Towers of Hanoi

Towers of Hanoi

Towers of Hanoi

Towers of Hanoi

Towers of Hanoi

Bài toán tháp HaNoi

void ThapHaNoi (int discs, STACK fromPole, STACK toPole, STACK aux)

{

int d;

if( discs >= 1)

{

ThapHaNoi (discs-1, fromPole, aux, toPole);

d = fromPole.pop();

toPole.push(d);

ThapHaNoi (discs-1,aux, toPole, fromPole);

}

}

Stack – Quick Sort

• Để khử đệ quy cho Quick Sort, ta sử dụng một stack để lưu lại các

partition (phân hoạch) cần tiến hành sắp xếp.

• Ý tưởng:

• Push phân hoạch đầu tiên (0, n-1) vào stack

• Pop một phân hoạch từ stack

• Chọn phần tử trục trên phân hoạch này

• Điều chỉnh phân hoạch tương ứng với trục

• Push 2 phân hoạch bên trái và phải trục vào stack

• Trong khi stack chưa rỗng

29

Stack – Quick Sort

• Push phân hoạch đầu tiên (0, n-1) vào stack

• Trong khi stack chưa rỗng

• Pop một phân hoạch từ stack

• Chọn phần tử trục trên phân hoạch này

• Điều chỉnh phân hoạch tương ứng với trục

t

stack

• Push 2 phân hoạch bên trái và phải trục vào

i

j

1 1 1

4 4 4

3 5 3

7 3 5

5 7 7

0 0 0

2 2 2

1 1 1

4 4 4

3 3 3

(3,4)

(0,1) (0,4)

Stack rỗng Stop

30

Thực thi biểu thức

• Giả sử có biểu thức X = a / b - c + d * e - a * c

• Với a = 4, b = c = 2, d = e = 3

• Diễn giải 1:

((4/2)-2)+(3*3)-(4*2)=0 + 8+9=1

• Hay diễn giải 2:

(4/(2-2+3))*(3-4)*2=(4/3)*(-1)*2=-2.66666…

 Máy tính sẽ tính như thế nào?

31 precedence rule + associative rule

Token Operator

Precedence1 Associativity

17

left­to­right

( ) [ ] ­> . ­­ ++

function call array element struct or union member increment, decrement2

16

left­to­right

15

right­to­left

­­ ++ ! ­ ­ + & * sizeof (type)

decrement, increment3 logical not one’s complement unary minus or plus address or indirection size (in bytes) type cast

14

right­to­left

* / % mutiplicative

13

Left­to­right

+ ­

binary add or subtract

12

left­to­right

<< >>  shift

11

left­to­right

10

left­to­right

> >=  < <=  == !=

relational    equality

9

left­to­right

bitwise and

&

8

left­to­right

bitwise exclusive or

^

7

left­to­right

bitwise or

6

left­to­right

&&

logical and

5

left­to­right

logical or

4

left­to­right

(cid:0) (cid:0)

?:

conditional

3

right­to­left

assignment

2

right­to­left

=    += ­= /= *= %= <<= >>= &= ^= (cid:0) =

1

,

comma

left­to­right

Con ng

iườ

Trình biên d chị

Infix

Postfix

2+3*4  a*b+5  (1+2)*7  a*b/c  (a/(b­c+d))*(e­a)*c  a/b­c+d*e­a*c

234*+  ab*5+  12+7*  ab*c/  abc­d+/ea­*c*  ab/c­de*+ac*­

ộ ư

ấ

ặ

Postfix: Không d u ngo c, không đ   u tiên

Token             Stack

Top

[0]            [1]        [2] 6 6                2 6/2 6/2              3 6/2­3 6/2­3          4 6/2­3          4          2 6/2­3          4*2 6/2­3+4*2

0 1 0 1 0 1 2 1 0

6 2 / 3 ­ 4 2 * +

ể

Chuy n Infix thành Postfix

ể

ứ ầ ủ ấ

ả ấ

ấ ả

ặ ượ ứ

ng  ng

ặ (1) Bi u th c đ y đ  d u ngo c a / b ­ c + d * e ­ a * c ­­> ((((a / b) ­ c) + (d * e)) – (a * c)) ặ (2) T t c  phép toán đ t bên ph i d u ngo c t  ((((a / b) ­ c) + (d * e)) – (a * c))

­

*+

*­

ấ ả ấ

(3) Xoá t

/ ặ t c  d u ngo c ab/c­de*+ac*­

ứ ự

ạ

Th  t

ổ  toán h ng trong Infix và Postfix không đ i

a + b * c, * > +

Token

Top Output

Stack [0]    [1]    [2]

+ + +      * +      *

a + b * c eos

­1 0 0 1 1 ­1

a a ab ab abc abc*=

a *1 (b +c) *2 d

Token

Top

Output

Stack [0]    [1]    [2]

match ) *1 = *2

a *1 ( b + c ) *2 d eos

­1 0 1 1 2 2 0 0 0 0

*1 *1        ( *1        ( *1        (      + *1        (      + *1 *2 *2 *2

a a a ab ab abc abc+ abc+*1 abc+*1d abc+*1d*2

1.

2.

3.

Tạo stack opStack rỗng để lưu các toán tử, danh sách list rỗng để lưu kết quả Tách chuỗi biểu thức infix thành danh sách các token Duyệt các token từ trái sang phải

ư ể ả c khi push ph i ki m tra và pop

4.

ộ ư ộ ư ử 3.1. Nếu token là toán hạng thì thêm vào cuối list 3.2. Nếu token là dấu ( thì push vào opstack 3.3. Nếu token là dấu ) thì pop toán tử trong opstack cho đến khi gặp dấu mở ngoặc. Lần lượt thêm toán tử vào cuối list 3.4. Nếu token là *, /, +, hay – thì push opstack (L u ý: tr ử t o á n  t t ro n g ướ ủ token và thêm vào cu i ố list)  này có đ   u tiên ≥ đ   u tiên c a ế opstack n u toán t

Khi xét hết các token thì pop tất cả những toán tử còn lại trong opstack và lần lượt thêm vào cuối list

40

ộ ư

Đ   u tiên

ộ ư

ử ượ ấ

đ

ử

ủ u  tiên  c a  toán  t

ơ   đang  xét  (

ộ ư

ộ ư

ấ

ỏ c  l y  ra  kh i  stack  khi  đ   u  tiên  trong  (1)  Toán  t ớ ằ ớ stack (isp: in­stack precedence) là l n h n hay b ng v i  ộ ư đ   icp:  incoming  precedence) ấ (2)  D u  (    có  đ   u  tiên  trong  stack  th p  và  đ   u  tiên  đang xét cao

(

) + ­

* / % eos

isp 0  19 12  12 13 13 13 0 icp 20 19 12 12 13 13 13 0

Bài tập

• 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)

• Cài đặt thuật toán QuickSort dùng Stack

• Cài đặt chương trình chuyển từ Infix sang Postfix

42

Queue

Phòng vé

cinemark

43

Queue – Định nghĩa

• Hàng đợi là một cấu trúc:

• Gồm nhiều phần tử có thứ tự

• Hoạt động theo cơ chế “Vào trước, ra trước” (FIFO - First In First Out)

44

Queue

rear

rear

rear

front

rear front

D C B

front

front

C B A

D C B A

A

B A

rear front

45

Queue – Định nghĩa

• Các thao tác cơ bản trên hàng đợi:

• InitQueue: khởi tạo hàng đợi rỗng

• IsEmpty: kiểm tra hàng đợi rỗng?

• IsFull: kiểm tra hàng đợi đầy?

• EnQueue: thêm 1 phần tử vào cuối hàng đợi, có thể làm hàng đợi đầy

• DeQueue: lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng

46

Queue

• Minh họa thao tác EnQueue

• Minh họa thao tác DeQueue

47

Queue – Sử dụng mảng

• Dùng 1 mảng (QArray) để chứa các phần tử.

• Dùng 1 số nguyên (QMax)để lưu số phần tử tối đa trong hàng đợi

• Dùng 2 số nguyên (QFront, QRear) để xác định vị trí đầu, cuối hàng đợi

• Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi

48

Queue – Sử dụng mảng

0

1

2

3

4

5

6

37 22 15 3

Qarray

QMax = 7

QNumItems = 4

QFront = 1

QRear = 4

49

Queue số nguyên – Sử dụng mảng

typedef struct QUEUE

{

int* QArray;

intQMax;

intQNumItems;

intQFront;

intQRear;

};

50

Queue số nguyên – Sử dụng mảng

• Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả”

0

1

2

3

4

5

6

37 22 15 3 7

9

• Giải pháp? Nối dài mảng (mảng động) hay sử dụng một mảng

vô cùng lớn?

Qarray QMax = 7 QNumItems = 6 QFront = 1 QRear = 6

51

Queue số nguyên – Sử dụng mảng

• Xử lý mảng như một danh sách liên kết vòng

0

1

2

3

4

5

6

37 22 15 3 7

9

Qarray QMax = 7 QNumItems = 6 QFront = 1 QRear = 6

52

Queue số nguyên – Sử dụng mảng

VD: Cho queue như sau

4

5 6 0 1 2 3   11 7 19 21 81   7

ỉ ố ả Ch  s  m ng QArray QMax QNumItems 5 1 QFront 5 QRear

Queue số nguyên – Sử dụng mảng

1. Thêm giá trị 123 vào hàng đợi

5

4

6

0 1 2 3   11 7 19 21 81  123 7

ỉ ố ả Ch  s  m ng QArray QMax QNumItems 6 1 QFront 6 QRear

Queue số nguyên – Sử dụng mảng

2. Lấy một phần tử khỏi hàng đợi

5

4

6

0 1 2 3   11 7 19 21 81  123 7

ỉ ố ả Ch  s  m ng QArray QMax QNumItems 5 2 QFront 6 QRear

Queue số nguyên – Sử dụng mảng

3. Thêm giá trị 456 vào hàng đợi

6

5

0

4

1 2 3

ỉ ố ả Ch  s  m ng QArray  456 11 7 19 21 81  123 7 QMax QNumItems 6 2 QFront 0 QRear

Queue số nguyên – Sử dụng mảng

int InitQueue(QUEUE &q, int MaxItem)

{

q.QArray = new int[MaxItem];

if (q.QArray == NULL)

return 0;

q.QMax = MaxItem;

q.QNumItems = 0;

q.QFront = q.QRear = -1;

return 1;

}

57

Queue số nguyên – Sử dụng mảng

int IsEmpty(QUEUE q)

{

if (q.QNumItems == 0)

return 1;

return 0;

}

58

Queue số nguyên – Sử dụng mảng

int IsFull(QUEUE q)

{

if (q.QMax == q.QNumItems)

return 1;

return 0;

}

59

Queue số nguyên – Sử dụng mảng

int EnQueue(QUEUE &q, int newitem) {

if (IsFull(q)==1) return 0; q.QRear++; if (q.QRear==q.QMax)

q.QRear = 0;

60

q.QArray[q.QRear] = newitem; if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return 1;

}

Queue số nguyên – Sử dụng mảng

int DeQueue(QUEUE &q, int &itemout) {

if (IsEmpty(q)==1)

return 0;

itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems--; if (q.QFront==q.QMax)

q.QFront = 0; if (q.QNumItems==0)

q.QFront = q.QRear = -1;

return 1;

}

61

Queue số nguyên – Sử dụng mảng

int QueueFront(const QUEUE &q, int &itemout)

{

if (IsEmpty(q)==1)

return 0;

itemout = q.QArray[q.QFront];

return 1;

}

62

Queue số nguyên – Sử dụng mảng

int QueueRear(const QUEUE &q, int &itemout)

{

if (IsEmpty(q)==1)

return 0;

itemout = q.QArray[q.QRear];

return 1;

}

63

Bài tập áp dụng

• Viết chương trình nhập/ xuất hàng đợi số nguyên (dùng mảng 1

chiều). Cho biết trong hàng đợi có bao nhiêu số lẻ

64

Queue – Ví dụ ứng dụng

• Quản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song song

• Hàng đợi in ấn các tài liệu

• Vùng nhớ đệm (buffer) dùng cho bàn phím

• Quản lý thang máy

65