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

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 trước – LIFO (Last In First Out) Hoạt động của Stack  Stack rỗng:  Đẩy (push) Q vào:  Đẩy A vào:  Lấy (pop) ra một => được A:  Lấy ra một => được Q và stack rỗng: Q Q A Q A 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  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 }; Thiết kế Stack dùng mảng Các phương thức template Stack::Stack(void) { top =-1; } template void Stack::Clear() { top =-1; } template bool Stack::IsEmpty() const { return top==-1; //stack rỗng } template bool Stack::IsFull() const { 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)<<s.Peek(); s.Pop(); } cout<<endl; } 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)<<s.Peek(); s.Pop(); } cout<<endl; }catch(exception &e){ cout<< e.what(); cout<<endl; } } Cài đặt Stack sử dụng con trỏ  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; a first_node p0 b p1 c p2 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_node new_top 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; }else{ throw exception("Not enough memory"); } } 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 old_top top_node old top middle old last 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;  Gán hai stack: cả hai dùng chung một vùng dữ liệu  stack2 = stack1; top middle last top middle last stack0 stack1 stack2 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 bằng tham trị  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 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ụ a b c copy_node new_top new_copy a b c copy.top_node 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<<endl; } }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? o 2 4 + 5 * 3 2 – 4 * - o Biểu thức tiền tố (postfix) 2. Lượng giá biểu thức như thế nào? o 2 4 + 5 * 3 2 – 4 * - 6 5 * 3 2 – 4 * - 30 3 2 – 4 * -  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. r = 3-1 =2; Push(r); 3. r = 8 / 2 =4; Push(r); 4. Push(3); 5. r = 4*3=12; Push(r); 6. r = 5 + 12 =17; Push(r); 8 5 1 3 2 8 5 4 54 3 5 1217 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ấumở 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!