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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:48

Thêm vào BST

Báo xấu

28
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu: Hàng đợi cung cấp cho người học những kiến thức như: Mô tả queue; Bus Stop Queue; Thiết kế của Queue; Cài đặt Queue sử dụng mảng; Thiết kế Queue dùng mảng; Array vòng với ngôn ngữ C++; Điều kiện biên của queue vòng; Phương thức Enqueue;... Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu: Hàng đợi - 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ế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 front rear rear rear rear rear  Lấy 1 người ra khỏi Queue
Bus Stop Queue Bus Stop front rear rear rear
Bus Stop Queue Bus Stop front rear rear
Bus Stop Queue Bus Stop front rear rear  Thêm một người vào Queue.  Queue là một cấu trúc FIFO (First-In, First-Out).
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 template Queue::Queue(void) bool Queue::IsEmpty() { const{ count=0; front =0; return count ==0; rear = MAX-1; } } template template bool Queue::IsFull() const{ void Queue::Clear(){ return count ==MAX; count=0; front =0; } rear = MAX-1; for(int i=0; i
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