Xem mẫu
- 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: 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:
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 template
Stack::Stack(void) bool Stack::IsEmpty() const
{ {
top =-1; return top==-1; //stack rỗng
} }
template
template
void Stack::Clear()
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
- Thử nghiệm
#include "Stack.cpp"
#include
#include
using namespace std;
void main(){
Stack s;
try{
for(int i=1;i
- 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
nguon tai.lieu . vn
