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

Hàng đợi (Queue)

 Sử dụng mảng  Sử dụng con trỏ  Ứng dụng của hàng đợi

Mô tả queue

 Một queue là một cấu trúc dữ liệu mà việc thêm vào được thực hiện ở một đầu (rear) và việc lấy ra được thực hiện ở đầu còn lại (front)

 Phần tử vào trước sẽ ra trước – FIFO (First In First Out)

Bus Stop Queue

Bus Stop

rear rear rear rear

 Lấy 1 người ra khỏi Queue

front rear

Bus Stop Queue

Bus Stop

front rear rear

rear

Bus Stop Queue

Bus Stop

front rear

rear

Bus Stop Queue

Bus Stop

front rear

 Thêm một người vào Queue.  Queue là một cấu trúc FIFO (First-In, First-Out).

rear

Thiết kế của Queue

template class Queue { public: Queue(void); //phương thức khởi tạo Queue(const Queue &source); //phương thức khởi tạo ~Queue(void); //phương thức hủy bool IsEmpty() const; //kiểm tra queue rỗng bool IsFull() const; //kiểm tra queue đầy void Enqueue(NodeType &item); //thêm phần tử vào cuối queue void Dequeue(); //lấy phần tử ra khỏi đầu queue NodeType &Peek() const; //xem phần tử đầu queue void Clear(); //xóa sạch các phần tử trong queue int GetSize() const; //trả về kích cỡ của queue };

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

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

const int MAX =20; template class Queue{ public:

Queue(void); //phương thức khởi tạo ~Queue(void); //phương thức hủy bool IsEmpty() const;//kiểm tra rỗng bool IsFull() const;//kiểm tra đầy void Enqueue(const NodeType& item);//thêm phần tử vào cuối queue

void Dequeue();//lấy phần tử ra từ đầu queue NodeType &Peek();//xem phần tử ở đầu queue void Clear();//xóa nội dung của queue int GetSize() const;//trả về kích cỡ của queue

private:

int front, rear; //đầu và cuối queue int count; //số phần tử của queue NodeType data[MAX];

};

Queue là array vòng (circular array)

Array vòng với ngôn ngữ C++  Xem array như là một vòng:

 phần tử cuối của array nối với phần tử đầu của array

 Tính toán vị trí kề:

 i = ((i + 1) == MAX) ? 0 : (i + 1);  if ((i + 1) == MAX) i = 0; else i = i + 1;  i = (i + 1) % MAX;

Điều kiện biên của queue vòng

Các phương thức

template bool Queue::IsEmpty() const{

template Queue::Queue(void) {

return count ==0;

}

count=0; front =0; rear = MAX-1;

}

template bool Queue::IsFull() const{

template void Queue::Clear(){

return count ==MAX;

}

count=0; front =0; rear = MAX-1;

for(int i=0; i

data[i]=0;

template int Queue::GetSize() const{

}

return count;

}

Thêm phần tử vào Queue

 Thêm một phần tử

 Di chuyển ‘rear’ một đơn vị theo chiều kim đồng hồ.  Gán phần tử vào data[rear].

16

Phương thức Enqueue

template void Queue::Enqueue(const NodeType &item) {

if(!IsFull()){

rear = (rear +1) % MAX; count ++; data[rear] = item;

}else{

throw exception("Queue is full");

}

}

Gỡ phần tử ra khỏi Queue

 Gỡ bỏ một phần tử

 Di chuyển front một đơn vị theo chiều kim đồng hồ.

18

Phương thức Dequeue

template void Queue::Dequeue(){

if(!IsEmpty()){

front = (front +1) % MAX; count --;

}else{

throw exception("Queue is empty");

}

}

template NodeType &Queue::Peek(){

return data[front];

}

Thử nghiệm

#include "Queue.cpp" #include "Queue.h" #include #include using namespace std;

void main(){ Queue queue; for(int i=1;i<=10;i++)queue.Enqueue(i); while (!queue.IsEmpty()) {

cout<

}

cout<

}

Cài đặt Queue sử dụng con trỏ

http://www.cs.usfca.edu/~galles/visualization/QueueLL.html

Thiết kế Node

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=nullptr);

//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

Queue liên kết  Thiết kế:

 Dùng hai con trỏ chỉ đến đầu và cuối của danh sách dữ

liệu (front và rear)

rear

front

 Khởi tạo rỗng: gán cả front và rear về NULL

front middle last

front rear

Thiết kế Queue

template class Queue { public:

Queue(void); Queue(const Queue &source); ~Queue(void); bool IsEmpty() const; void Enqueue(const NodeType &item); void Dequeue(); NodeType &Peek() const; void operator=(const Queue &source); void Clear();

private:

Node *front; Node *rear; void Copy(const Queue &source,

Node* & destFront, Node* & destRear));

};

Thêm phần tử vào một queue liên kết

 Giải thuật:

1. Tạo một node mới với dữ liệu cần thêm vào 2. Nếu queue đang rỗng

2.1. front và rear là node mới

3. Ngược lại

new_rear

3.1. Nối node mới vào sau rear 3.2. rear chính là node mới new_last

rear front

front middle last

Phương thức Enqueue

template void Queue::Enqueue(const NodeType &item) {

Node *newNode = new Node(item); //tạo node mới

if(newNode != nullptr){

if(front==nullptr){front=rear= newNode; }//Queue đang rỗng

else{

rear -> next = newNode; rear = newNode;

}

}else {

throw exception("Not enough memory");

}

}

Bỏ phần tử khỏi một queue liên kết

 Giải thuật:

1. Dùng một con trỏ để giữ lại front hiện tại 2. Nếu queue có một phần tử

3. Ngược lại

3.1. Trỏ front đến nút kế sau

rear

4. Xóa nút cũ đi

2.1. Gán front và rear về NULL

front

front middle last

old_front

Phương thức Dequeue

template void Queue::Dequeue() {

if(front !=nullptr){ //queue không rỗng

Node *oldFront = front; front=oldFront->next; if(front==nullptr)rear = nullptr; delete oldFront;

}else{

throw exception("Queue is emty");

}

}

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

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

 delete queue0;

queue0

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

top middle last

 queue2 = queue1;

queue2

top middle last

queue1

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 Queue

template void Queue::Clear(){

while (!IsEmpty()) {

Dequeue();

}

}

template Queue::~Queue(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

template void Queue::Copy(const Queue &source, Node* & destFront, Node * & destRear){

Node *curS, *curD; curS= source.front; if(curS == nullptr)return; //queue rỗng destFront = curD = new Node(curS -> item); while(curS -> next != nullptr){//vẫn còn phần tử cần duyệt

curS = curS -> next; curD -> next = new Node(curS ->item); curD = curD -> next;

} destRear = curD;

}

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

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

Copy(source, front, rear);

}

template void Queue::operator=(const Queue &source) {

Clear(); Copy(source, front, rear);

}

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

return front==nullptr;

}

template NodeType &Queue::Peek() const {

return front -> item;

}

Thử nghiệm

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

void main(){

Queue q; q.Enqueue("I"); q.Enqueue("love !"); q.Enqueue("you"); while(!q.IsEmpty()){

cout << q.Peek() << " "; q.Dequeue();

} cout << endl;

}

Ứng dụng của Queue

 Sử dụng trong nhiều bài toán, thuật toán…  Thuật toán điều phối CPU của hệ điều hành  Biểu diễn các đa thức, tính toán đa thức

Ứng dụng: tính toán đa thức

 Thiết kế cấu trúc dữ liệu cho đa thức:

 Một bản ghi có thành phần mũ và hệ số  Một danh sách các bản ghi theo thứ tự giảm của số mũ  Có thể dùng queue

Giải thuật cộng hai đa thức 1

Algorithm Equals_sum1

Input: p,q là hai đa thức Output: đa thức tổng

1.1. Lấy phần tử front của p và q thành p_term, q_term 1.2. Nếu bậc của p_term lớn (hoặc nhỏ) hơn bậc của q_term

1. Trong khi p và q chưa rỗng

1.2.1. Đẩy p_term (hoặc q_term) vào kết quả 1.2.2. Bỏ phần tử đầu trong p (hoăc trong q)

1.3.1. Tính hệ số mới cho số hạng này 1.3.2. Đẩy vào kết quả

1.3. Ngược lại

2. Nếu p (hoặc q) chưa rỗng

2.1. Đẩy toàn bộ p (hoặc q) vào kết quả

End Equals_sum1

Ví dụ cộng hai đa thức bằng giải thuật 1

<3.0, 6>

< -2.0, 4>

<1.0, 3>

<4.0, 0>

p = 3x6 – 2x4 + x3 + 4

q = 5x5 + 2x4 + 4x2 + 2x

<5.0, 5> <2.0, 4> <4.0, 2> <2.0, 1>

<3.0, 6>

<5.0, 5>

<1.0, 3>

<4.0, 2>

p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4

<2.0, 1> <4.0, 0>

Giải thuật cộng hai đa thức 2

Algorithm Equals_sum2

Input: p,q là hai đa thức Output: đa thức tổng

Algorithm Bac_da_thuc 1. Trong khi p hoặc q chưa rỗng

1.1. Nếu bậc của p lớn hơn bậc của q Input: đa thức Output: bậc của đa thức

1.1. Trả về -1

1.1.1. Lấy từ p thành term 1.1.2. Đẩy term vào kết quả 1. Nếu đa thức rỗng 1.2. Nếu bậc của q lớn hơn bậc của p

2. Trả về bậc của phần tử đầu 1.2.1. Lấy từ q thành term 1.2.2. Đẩy term vào kết quả

1.3. Ngược lại End Bac_da_thuc

1.3.1. Lấy p_term, q_term từ p và q 1.3.2. Tính tổng hai hệ số 1.3.3. Nếu hệ số kết quả khác không

1.3.3.1. Đẩy vào kết quả

End Equals_sum2

Ví dụ cộng hai đa thức bằng giải thuật 2

-1 6 0 3 4

<3.0, 6>

< -2.0, 4>

<1.0, 3>

<4.0, 0>

1-1 degree(p) = 5 2 4

degree(p) = p = 3x6 – 2x4 + x3 + 4

q = 5x5 + 2x4 + 4x2 + 2x

<5.0, 5> <2.0, 4> <4.0, 2> <2.0, 1>

<3.0, 6>

<5.0, 5>

<1.0, 3>

<4.0, 2>

p + q = 3x6 + 5x5 + x3 + 4x2 + 2x + 4

<2.0, 1> <4.0, 0>

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