Bài giảng Cấu trúc dữ liệu: Ngăn xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Ngăn xếp cung cấp cho người học những kiến thức như: Sử dụng mảng; Sử dụng con trỏ; Ứng dụng của ngăn xếp. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Ngăn xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung ThS. Lương Trần Ngọc KhiếtKhoa Công nghệ Thông tin- Đại học Sư phạm TP. HCMNgăn Xếp (Stack) Sử dụng mảng Sử dụng con trỏ Ứng dụng của ngăn xếpMô 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: Q 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: QHoạt động của Stack Thiết kế của Stacktemplate //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ảngconst int MAX=20; //stack có tối đa MAX phần tửtemplateclass Stack{public:Stack(void);~Stack(void);bool IsEmpty() const;//kiểm tra stack rỗngbool IsFull() const; //kiểm tra stack đầyvoid Push(const NodeType &item);NodeType &Peek() const;void Pop();void Clear();private:NodeType data[MAX]; //mảng chứa dữ liệuint top; //đỉnh của stack}; Các phương thứctemplate templateStack::Stack(void) bool Stack::IsEmpty() const{ { top =-1; return top==-1; //stack rỗng} }template templatevoid Stack::Clear() bool Stack::IsFull() const{ { top =-1; return top== MAX-1; //stack đầy} }Các phương thứctemplatevoid Stack::Push(const NodeType &item){ if(!IsFull()){ top++; data[top]= item; }else { throw exception(Stack is full); }}Các phương thứctemplatevoid Stack::Push(const NodeType &item){ if(!IsFull()){ top++; data[top]= item; }else { throw exception(Stack is full); }}templatevoid Stack::Pop(){ if(!IsEmpty()){ top--; }else { throw exception(Stack is empty); }}Thử nghiệm#include Stack.cpp#include #includeusing namespace std;void main(){ Stack s; for(int i=1;iThử nghiệm#include Stack.cpp#include #includeusing namespace std;void main(){ Stack s; try{ for(int i=1;iCài đặt Stack sử dụng con trỏhttp://www.cs.usfca.edu/~galles/visualization/StackLL.htmlThiết kế Node Node Cần: Dữ liệu Con trỏ để trỏ đến node sau ConstructorThiết kế Nodetemplatestruct 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.htemplateNode::Node(){}templateNode::Node(NodeType item,Node *ptr=nullptr){ this->item= item; this->next = ptr;}Ví dụ với Node liên kếtNode 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_nodep0 a b c