TS. Lê Minh Trung ThS. Lương Trần Ngọc Khiết Khoa Công nghệ Thông tin- Đại học Sư phạm TP. HCM

Ngăn Xếp (Stack)

 Sử dụng mảng  Sử dụng con trỏ  Ứng dụng của ngăn xếp

Mô tả stack

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

 Là một cấu trúc vào sau ra In

trước – LIFO (Last First Out)

Hoạt động của Stack

 Stack rỗng:

Q

 Đẩy (push) Q vào:

A

Q

 Đẩy A vào:

A

 Lấy (pop) ra một => được A:

Q

 Lấy ra một => được Q và stack rỗng:

Q

Hoạt động của Stack

Thiết kế của Stack

template //NodeType là kiểu dữ liệu tùy ý class Stack {

public:

};

Stack(void); //phương thức khởi tạo Stack(const Stack &source); //phương thức khởi tạo ~Stack(void); //phương thức hủy bool IsEmpty() const; void Push(const NodeType &item); //thêm phần tử vào đỉnh stack void Pop(); //gỡ phần tử ra khỏi đỉnh stack NodeType &Peek() const; //xem phần tử trên đỉnh stack void Clear(); //xóa dữ liệu của stack void operator=(const Stack &source);

Cài đặt Stack sử dụng mảng http://www.cs.usfca.edu/~galles/visualization/StackArray.html

Thiết kế Stack dùng mảng

const int MAX=20; //stack có tối đa MAX phần tử

template class Stack { public: Stack(void); ~Stack(void); bool IsEmpty() const;//kiểm tra stack rỗng bool IsFull() const; //kiểm tra stack đầy void Push(const NodeType &item); NodeType &Peek() const; void Pop(); void Clear(); private: NodeType data[MAX]; //mảng chứa dữ liệu int top; //đỉnh của stack };

Các phương thức

template Stack::Stack(void) {

template bool Stack::IsEmpty() const {

top =-1;

return top==-1; //stack rỗng

}

}

template void Stack::Clear() {

template bool Stack::IsFull() const {

top =-1;

return top== MAX-1; //stack đầy

}

}

Các phương thức

template void Stack::Push(const NodeType &item) {

if(!IsFull()){

top++; data[top]= item;

}else {

throw exception("Stack is full");

}

}

Các phương thức

template void Stack::Push(const NodeType &item){

if(!IsFull()){

top++; data[top]= item;

}else {

throw exception("Stack is full");

}

}

template void Stack::Pop(){

if(!IsEmpty()){

top--;

}else {

throw exception("Stack is empty");

}

}

Thử nghiệm

#include "Stack.cpp" #include #include using namespace std;

void main(){

Stack s; for(int i=1;i<=10;i++)s.Push(i); while(!s.IsEmpty()){

cout << setw(4)<

} cout<

}

Thử nghiệm

#include "Stack.cpp" #include #include using namespace std;

void main(){

Stack s; try{

for(int i=1;i<=100;i++)s.Push(i); while(!s.IsEmpty()){

cout << setw(4)<

}

cout<

}catch(exception &e){

cout<< e.what(); cout<

}

}

Cài đặt Stack sử dụng con trỏ http://www.cs.usfca.edu/~galles/visualization/StackLL.html

Thiết kế Node

Node

Cần:

Dữ liệu Con trỏ để trỏ đến node sau Constructor

Thiết kế Node

template struct Node {

NodeType item; // dữ liệu của Node Node *next; // con trỏ tới Node kế tiếp Node(); //phương thức khởi tạo Node(NodeType item, Node *ptr=NULL); //phương thức khởi tạo

};

Thiết kế Node

#include "Node.h"

template Node::Node(){}

template Node::Node(NodeType item,Node

*ptr=nullptr)

{

this->item= item; this->next = ptr;

}

Ví dụ với Node liên kết

Node first_node(‘a’); Node *p0 = &first_node; Node *p1 = new Node(‘b’); p0->next = p1; Node *p2 = new Node(‘c’, p0); p1->next = p2;

p1 p2

first_node

p0 a b c

Stack liên kết

Thiết kế Stack

#include "Node.h" template class Stack { public: Stack(void); //phương thức khởi tạo Stack(const Stack &source); //phương thức khởi tạo ~Stack(void); //phương thức hủy bool IsEmpty() const; void Push(const NodeType &item); //thêm phần tử vào đỉnh stack void Pop(); //gỡ phần tử ra khỏi đỉnh stack NodeType &Peek() const; //xem phần tử trên đỉnh stack void Clear(); //xóa dữ liệu của stack void operator=(const Stack &source); //so sánh bằng private: Node *top; Node *Copy(const Stack &source); //copy từ stack source tới vùng dữ liệu mới và trả về con trỏ tới vùng này

};

Thêm vào một stack liên kết

 Giải thuật

 1. Tạo ra một node mới với giá trị cần thêm vào  2. Trỏ nó đến đỉnh hiện tại của stack  3. Trỏ đỉnh của stack vào node mới new_top

new_node

top_node

old top middle last

Phương thức Push

template void Stack::Push(const NodeType &item) {

Node *newTop = new Node(item,top); if(newTop !=nullptr){

top = newTop;

throw exception("Not enough memory");

}else{

}

}

Bỏ đỉnh của một stack liên kết

 Giải thuật:

 1. Gán một con trỏ để giữ đỉnh của stack  2. Trỏ đỉnh của stack vào node ngay sau đỉnh hiện tại  3. Xóa node cũ đi

top_node

old top middle old last

old_top

Phương thức Pop

template void Stack::Pop(){

Node *oldTop = top; top = oldTop ->next; delete oldTop;

}

Sự không an toàn con trỏ trong C++

 Kết thúc biến stack nhưng bộ nhớ còn lại:

 delete stack0;

stack0

 Gán hai stack: cả hai dùng chung một vùng dữ liệu

top middle last

 stack2 = stack1;

stack2

top middle last

stack1

top middle last

Đảm bảo an toàn con trỏ trong C++

 Destructor (phương thức hủy):

 Sẽ được gọi ngay trước khi đối tượng kết thúc thời gian sống  Dùng xóa hết vùng dữ liệu

 Copy constructor:

 Sẽ được gọi khi khởi tạo biến lúc khai báo, hoặc truyền dữ liệu

 Sao chép nguồn thành một vùng dữ liệu mới

 Assignment operator (toán tử gán):

 Sẽ được gọi khi gán đối tượng này vào đối tượng khác  Xóa vùng dữ liệu của đích và đồng thời sao chép nguồn thành một

bằng tham trị

vùng dữ liệu mới

Hủy vùng nhớ đã được cấp cho Stack template void Stack:: Clear() {

while(!IsEmpty())Pop();

}

template Stack::~Stack(void) {

Clear();

}

Sao chép vùng dữ liệu – Ví dụ

copy.top_node

a b c

copy_node

new_copy

new_top

a b c

Sao chép vùng dữ liệu

 Giải thuật:

1. Tạo một đỉnh của danh sách mới với dữ liệu của đỉnh nguồn 2. Giữ một con trỏ đuôi chỉ vào cuối danh sách mới 2. Duyệt qua danh sách nguồn

2.1. Tạo một node mới với dữ liệu từ node nguồn hiện tại 2.2. Nối vào cuối danh sách mới 2.3. Con trỏ đuôi là node mới

Sao chép vùng dữ liệu

template Node *Stack::Copy(const Stack &source) {

Node *sTop, *sCur, *newTop, *newCur; sTop = sCur = source.top; if(sTop==nullptr)return nullptr; newTop = newCur = new Node(sTop->item); while (sCur->next !=nullptr) {

sCur = sCur ->next; newCur->next = new Node(sCur->item); newCur = newCur ->next;

} return newTop;

}

Copy constructor và toán tử gán

template Stack::Stack(const Stack &source) {

top = Copy(source);

}

template void Stack::operator=(const Stack

&source)

{

}

Clear(); //xóa dữ liệu cũ của stack top = Copy(source); //trỏ tới dữ liệu mới

Phương thức khác template bool Stack::IsEmpty() const {

return (top==nullptr);

}

template NodeType &Stack::Peek() const {

return top ->item;

}

Thử nghiệm

#include #include #include #include "Stack.cpp" #include "Node.cpp" using namespace std;

void main(){

Stack sString, sStr; sString.Push("you !"); sString.Push("love"); sString.Push("I"); sStr = sString; while (!sStr.IsEmpty()) {

cout<< sStr.Peek() << " "; sStr.Pop();

} cout<< endl; cin.get();

}

Thử nghiệm

void main(){

try{ Stack s; for(int i=1;i<100000000;i++){

s.Push(i); cout << "Cap phat # " << i<

}

}catch(exception &e){

cout<< e.what()<< endl;

} cin.get();

}

Ứng dụng của Stack

 Sử dụng trong nhiều bài toán, thuật toán…  Khử đệ qui  Kí pháp nghịch đảo Ba Lan (Reserve Polish Notation)

Ước lượng biểu thức

 Cho trước biểu thức: (2+4)*5 – (3-2)*4

 Biểu thức trung tố (infix)

1. Có thể biểu diễn biểu thức ở dạng khác mà không

cần dấu ( ) hay không? 2 4 + 5 * 3 2 – 4 * - o

o Biểu thức tiền tố (postfix)

2. Lượng giá biểu thức như thế nào?

2 4 + 5 * 3 2 – 4 * -  6 5 * 3 2 – 4 * -  30 3 2 – 4 * -

o  30 1 4 * -  30 4 -  26

Lượng giá biểu thức postfix

 Đọc lần lượt các thành phần của biểu thức từ trái sang phải, với

mỗi thành phần được đọc thực hiện các bước sau:

 Nếu thành phần được đọc là toán hạng od thì đẩy nó vào ngăn

xếp, tức là S. Push (od).

 Nếu thành phần được đọc là phép toán op thì lấy ra các toán

hạng ở đỉnh ngăn xếp:

od 2 = S.PopAndPeek( ) od 1 = S.PopAndPeek( )

 Thực hiện phép toán op với các toán hạng là od 1 và od 2, kết

quả được đẩy vào ngăn xếp: r = od 1 op od 2 S. Push(r)

 Lặp lại hai bước trên cho tới khi thành phần cuối cùng của biểu thức được đọc qua. Khi đó ngăn xếp chứa kết quả của biểu thức.

Ví dụ  Input: 5 8 3 1 - / 3 * +

1. Push(5); Push(8); Push(3); Push(1); 2.

4 1217 3 1 2

r = 3-1 =2; Push(r); r = 8 / 2 =4; Push(r);

54 5 8 3

5 8 5

5

3. 4. Push(3); 5.

6.

r = 4*3=12; Push(r); r = 5 + 12 =17; Push(r);

Chuyển đổi infix thành postfix

 Thứ tự ưu tiên của toán tử: (), * / , + -

1. Nếu thành phần được đọc là toán hạng thì viết nó vào biểu thức postfix. 2. Nếu thành phần được đọc là phép toán (phép toán hiện thời), thì thực hiện các

bước sau: 1. Nếu ngăn xếp không rỗng thì nếu phần tử ở đỉnh ngăn xếp là phép toán có quyền ưu tiên cao hơn hay bằng phép toán hiện thời, thì phép toán đó được kéo ra khỏi ngăn xếp và viết vào biểu thức postfix. Lặp lại bước này. 2. Nếu ngăn xếp rỗng hoặc phần tử ở đỉnh ngăn xếp là dấu mở ngoặc hoặc phép toán ở đỉnh ngăn xếp có quyền ưu tiên thấp hơn phép toán hiện thời, thì phép toán hiện thời được đẩy vào ngăn xếp.

3. Nếu thành phần được đọc là dấu mở ngoặc thì nó được đẩy vào ngăn xếp. 4. Nếu thành phần được đọc là dấu đóng ngoặc thì thực hiện các bước sau:

1.

(Bước lặp) Loại các phép toán ở đỉnh ngăn xếp và viết vào biểu thức postfix cho tới khi đỉnh ngăn xếp là dấu mở ngoặc.

2. Loại dấu mở ngoặc khỏi ngăn xếp.

5. Sau khi toàn bộ biểu thức infix được đọc, loại các phép toán ở đỉnh ngăn xếp và

viết vào biểu thức postfix cho tới khi ngăn xếp rỗng.

Ví dụ  Input: a * ( b – c + d) + e / f

a b c – d + * e f / +

CÁM ƠN VÌ ĐÃ LẮNG NGHE!