Chương 2: Stack

Ấ

C U TRÚC D LI U VÀ I THU T GI

Ữ Ệ Ả

Ậ

Ch

ng 2: Stack

ươ

Mô t

stack

ả

ộ ấ

 M t stack là m t c u trúc d ữ ộ li u mà vi c thêm vào và ệ ệ i lo i b đ c th c hi n t ệ ạ ạ ỏ ượ m t đ u (g i là đ nh – top ỉ ọ ộ ầ c a stack). ủ

 Là m t d ng vào sau ra

ự

ộ ạ c – LIFO (Last In First

ng 2: Stack

ươ

tr ướ Out)

Ví d v stack ụ ề

 Stack r ng:ỗ

 Đ y (push) Q vào:

 Đ y A vào:

ẩ

 L y (pop) ra m t => đ

ẩ

 L y ra m t => đ

c A: ấ ộ ượ

ng 2: Stack

ươ

c Q và stack r ng: ấ ộ ượ ỗ

ng d ng: Đ o ng

c danh sách

Ứ

ụ

ả

ượ

 Yêu c u: Đ o ng ầ i thu t:  Gi

c m t danh sách nh p vào ả ượ ậ ộ

ả ậ

1. L p l ặ ạ

ị ộ i n l n ậ

ẩ

ặ

stack ầ 1.1. Nh p vào m t giá tr 1.2. Đ y nó vào stack 2. L p khi stack ch a r ng ư ỗ ị ừ ộ ấ

ng 2: Stack

ươ

2.1. L y m t giá tr t 2.2. In ra

Đ o ng

c danh sách – Ví d

ả

ượ

ụ

ầ

ố Nh p 1ậ

Nh p 5ậ

Nh p 7ậ

Nh p 3ậ

C n nh p 4 s vào ậ Ban đ uầ

3 7

5 1

L y ra => 3

L y ra => 7

ấ

L y ra => 5

L y ra => 1

ấ

Stack đã r ngỗ Ng ngừ

5 1

ng 2: Stack

ươ

Đ o ng

c danh sách – Mã C++

ả

ượ

#include using namespace std;

s d ng STL ử ụ (Standard Template Library)

ữ ệ

ể

ộ

khai báo m t stack có ki u d li u c a các phân t

bên trong là double

ử

ủ

đ y m t s vào trong stack

ộ ố

ẩ

ki m tra xem stack có khác r ng không

ể

ỗ

ủ

l y giá tr trên đ nh c a stack ra, ỉ ị ấ stack không đ iổ

int main( ) { int n; double item; stack numbers; cout << "Bao nhieu so nhap vao? " cin >> n; for (int i = 0; i < n; i++) { cin >> item; numbers.push(item); } while (!numbers.empty( )) { cout << numbers.top( ) << " "; numbers.pop( ); } }

ỏ

ị

ỉ

là giá tr k ti p

l y giá tr trên đ nh c a stack ra kh i stack, ấ ủ đ nh c a stack bây gi ờ ỉ

ị ế ế

ủ

ng 2: Stack

ươ

Ki u tr u t

ng (abstract data type)

ừ ượ

ể

ể ợ

ủ ậ ầ ợ ị

 ĐN2: M t dãy c a ki u T

 ĐN1: M t ki u (type) ộ  m t t p h p ộ ậ  m i thành ph n c a t p h p này là các giá tr (value) ỗ  Ví d : int, float, char là các ki u c b n ể

ơ ả ể

ụ ộ

ủ  có chi u dài b ng 0 là r ng ằ  có chi u dài n (n>=1): b th t (Sn-1, t) ỗ ộ ứ ự ề ề

 Sn-1: dãy có chi u dài n-1 thu c ki u T  t là m t giá tr thu c ki u T. ộ ị

ể ề ộ

ng 2: Stack

ươ

ể ộ

Stack tr u t

ng

ừ ượ

 M t stack ki u T:

ạ ể

create)

ỗ

push) ủ ỉ

pop) ủ ỉ ị

ng 2: Stack

ươ

ộ ể  M t dãy h u h n ki u T ộ ữ  M t s tác v : ụ ộ ố 1. Kh i t o stack r ng ( ỗ empty) 2. Ki m tra r ng ( 3. Đ y m t giá tr vào trên đ nh c a stack ( ị ộ 4. B giá tr đang có trên đ nh c a stack ( 5. L y giá tr trên đ nh c a stack, stack không đ i ( ủ ở ạ ể ẩ ỏ ấ ỉ ị ổ top)

Thi

t k stack

ế ế

enum Error_code {fail, success, overflow, underflow};

template class Stack { public:

//constructor

ỗ

ng th c c n thi Stack(); bool empty() const; Error_code push(const Entry &item); Error_code pop(); ỏ Error_code top(Entry &item); ấ //khai báo m t s ph ộ ố //ki m tra r ng ể //đ y item vào ẩ trên đ nh //b ph n t ỉ ầ ử //l y giá tr trên đ nh ỉ ị t khác ầ ươ ứ ế

private:

//khai báo d li u và hàm ph tr ch này ụ ợ ữ ệ ỗ

ng 2: Stack

ươ

};

Thi

t k các ph

ng th c

ế ế

ươ

ứ

i thì tr v

template bool Stack::empty() const; Pre: Không có Post: Tr v giá tr ả ề

ị true n u stack hi n t

ệ ạ

ế

i là r ng, ng ỗ

c l ượ ạ

ả ề false

ệ ạ

ầ

c thêm vào đ nh c a stack. ỉ

ủ

i tr v giá tr

c l

template Error_code Stack::push(const Entry &item); Pre: Không có Post: N u stack hi n t ế Ng ượ ạ ả ề

i không đ y, item s đ ẽ ượ ể

ủ

ị overflow c a ki u Error_code và stack không đ i. ổ

i không r ng, đ nh c a stack hi n t

i s b h y b .

ệ ạ

ệ ạ ẽ ị ủ

ủ

ỗ

ỏ

ỉ

i tr v giá tr

c l

template Error_code Stack::pop() const; Pre: Không có Post: N u stack hi n t ế Ng ượ ạ ả ề

ị underflow c a ki u Error_code và stack không đ i. ổ

ủ

ể

i không r ng, đ nh c a stack hi n t

c chép vào tham

ủ

ệ ạ ẽ ượ

template Error_code Stack::top(Entry &item) const; Pre: Không có Post: N u stack hi n t ế bi n item. Ng ế

i s đ ệ ạ ỉ ỗ ị fail c a ki u Error_code. i tr v giá tr c l ượ ạ ả ề

ủ

ể

ng 2: Stack

ươ

Hi n th c stack liên t c

ự

ụ

ệ

ng 2: Stack

ươ

Khai báo stack liên t cụ

const int maxstack = 10;

//small number for testing

template class Stack { public:

Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item);

private:

int count; Entry entry[maxstack];

};

ng 2: Stack

ươ

vào stack

Đ y m t ph n t ộ

ầ ử

ẩ

 Gi

ả

ỉ

ủ ứ ỉ

top

count=3 count=2

ng 2: Stack

ươ

i thu t: ậ 1. N u còn ch tr ng trong stack ỗ ố ế 1.1. Tăng v trí đ nh lên 1 ị 1.2. Ch a giá tr vào v trí đ nh c a stack 1.3. Tăng s ph n t ị lên 1 ị ầ ử ố

B ph n t

ầ ử

trên đ nh stack ỉ

ỏ  Gi

ả

i thu t: ậ 1. N u còn ph n t ế

top

count=2 count=3

ng 2: Stack

ươ

đi 1 trong stack ầ ử 1.1. Gi m v trí đ nh đi 1 ị ả 1.2. Gi m s ph n t ố ả ỉ ầ ử

- Mã C++

Thêm/B ph n t ỏ

ầ ử

template Error_code Stack:: push(const Entry &item) {

if (count >= maxstack)

return overflow;

else

entry[count++] = item;

return success;

}

template Error_code Stack:: pop() {

if (count == 0)

return underflow;

else

count--; return success;

}

ng 2: Stack

ươ

L y giá tr trên đ nh stack

ỉ

ị

ấ  Gi

ả

trong stack

 Mã C++:

i v trí đ nh i thu t: ậ 1. N u còn ph n t ầ ử ế 1.1. Tr v giá tr t ả ề ị ạ ị ỉ

template Error_code Stack:: top(Entry &item) {

if (count == 0)

return underflow;

else

item = entry[count - 1];

return success;

ng 2: Stack

ươ

}

Reverse Polish Calculator

 Mô t

ả

ọ ượ ướ

bài toán:  Các toán h ng đ ạ  Khi đ c vào toán t stack, tính toán ọ c và đ y vào stack ừ ạ

 Thi

c đ c vào tr ẩ , l y hai toán h ng ra t này, r i đ y k t qu vào stack ả ế ử ấ ồ ẩ

ề

ứ ộ

ng i dùng ạ ậ ệ ườ

ng 2: Stack

ươ

v i toán t ử ớ t k ph n m m: ầ ế ế  C n m t stack đ ch a toán h ng ể ầ  C n hàm get_command đ nh n l nh t ừ ầ  C n hàm do_command đ th c hi n l nh ệ ệ ầ ể ể ự