Cách cài đặt queue trong c++
Bài viết hôm nay mình sẽ hướng dẫn các bạn cách cài đặt queue có sử dụng template trong ngôn ngữ c++.
Nếu bạn chưa biết template là gì thì có thể xem tại đây.
Queue là gì: Queue hay còn gọi là hàng đợi, là một cấu trúc dữ liệu thường dùng trong các ngôn ngữ lập trình. Các bạn có thể tưởng tượng queue như là việc bạn phải xếp hàng để mua vé xem phim vậy. Người nào đến trước thì sẽ được mua vé trước, người nào đến sau thì phải chờ những người ở trước.
Các hoạt động cơ bản trên queue
Trong queue có các hoạt động cơ bản sau:
- Hoạt động isFull(): Kiểm tra xem hàng đợi đã đầy hay chưa.
- Hoạt động isEmpty(): Kiểm tra xem hàng đợi có trống hay không.
- Hoạt động peek(): Lấy phần tử ở đầu hàng đợi, mà không xóa phần tử này.
- Hoạt động enqueue(): Thêm (hay lưu trữ) một phần tử vào trong hàng đợi.
- Hoạt động dequeue(): Xóa một phần tử từ hàng đợi.
Cách cài đặt queue trong c++
Cách cài đặt queue ? Mình sẽ cài đặt queue dưới dạng một class.
Khai báo một lớp queue
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
template<class T> class Queue { private: int front; int rear; T *data; int size; public: Queue(int = 10); ~Queue(); bool isFull(); bool isEmpty(); bool peek(T&); bool enqueue(const T); bool dequeue(T&); }; |
Trong lớp queue sẽ có các thuộc tính như sau:
- front: Chính là biến để lưu vị trí đầu tiên của hàng đợi. Mặc định khởi tạo
front = 0. - rear: Chính là biến để lưu vị trí cuối cùng của hàng đợi. Mặc định khởi tạo
rear = -1. - size: Chính là kích thước của hàng đợi. Nếu không khởi tạo hoặc khởi tạo sai thì mặc định có 10 phần tử.
- data: Chính là con trỏ dùng để lưu trữ dữ liệu của hàng đợi.
Cài đặt construction cho hàng đợi
|
1 2 3 4 5 6 7 8 9 10 11 |
template<class T> Queue<T>::Queue(int size) { if (size > 0 && size < 1000) this->size = size; else this->size = 10; rear = -1;// Queue rỗng front = 0; data = new T[size]; } |
Cài đặt destruction cho hàng đợi
|
1 2 3 4 5 |
template<class T> Queue<T>::~Queue() { delete[] data; } |
Trong destruction ta tiến hành xóa dữ liệu của con trỏ data.
Cài đặt hoạt động isEmpty()
|
1 2 3 4 5 6 7 |
template<class T> bool Queue<T>::isEmpty() { if (rear == -1) return true; return false; } |
Hoạt động isEmpty() sẽ trả về giá trị true nếu như hàng đợi trống và ngược lại.
Cài đặt hoạt động isFull()
|
1 2 3 4 5 6 7 |
template<class T> bool Queue<T>::isFull() { if (rear == size) return true; return false; } |
Hoạt động isFull() sẽ trả về giá trị true nếu hàng đợi đã đầy và ngược lại.
Cài đặt hoạt động peek()
|
1 2 3 4 5 6 7 8 9 |
template<class T> bool Queue<T>::peek(T& Item) { /*Nếu queue rỗng thì trả về false*/ if (isEmpty() == true) return false; Item = data[rear]; return true; } |
Hoạt động peek() sẽ trả về giá trị phần tử đầu tiên của hàng đợi bằng tham chiếu mà không xóa nó. Nếu hàng đợi rỗng thì hoạt động peek() sẽ trả về giá trị false.
Cài đặt hoạt động enqueue()
|
1 2 3 4 5 6 7 8 9 10 |
template<class T> bool Queue<T>::enqueue(const T Item) { /*Nếu ngăn xếp đầy thì trả về false*/ if (isFull() == true) return false; rear++; data[rear] = Item; return true; } |
Hoạt động enqueue() sẽ trả về giá trị true nếu đã thêm thành công một phần tử vào hàng đợi và ngược lại.
Cài đặt hoạt động dequeue()
|
1 2 3 4 5 6 7 8 9 10 |
template<class T> bool Queue<T>::dequeue(T &Item) { /*Nếu ngăn xếp rỗng thì trả về false*/ if (isEmpty() == true || front > rear) return false; Item = data[front]; front++; return true; } |
Tương tự như peek() nhưng sau khi lấy phần tử đầu tiên của hàng đợi thì sẽ xóa phần tử đó đi.
Chạy thử chương trình cài đặt queue
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <iostream> #include<math.h> using namespace std; template<class T> class Queue { private: int front; int rear; T *data; int size; public: Queue(int = 10); ~Queue(); bool isFull(); bool isEmpty(); bool peek(T&); bool enqueue(const T); bool dequeue(T&); }; template<class T> Queue<T>::Queue(int size) { if (size > 0 && size < 1000) this->size = size; else this->size = 10; rear = -1;// Queue rỗng front = 0; data = new T[size]; } template<class T> Queue<T>::~Queue() { delete[] data; } template<class T> bool Queue<T>::isFull() { if (rear == size) return true; return false; } template<class T> bool Queue<T>::isEmpty() { if (rear == -1) return true; return false; } template<class T> bool Queue<T>::peek(T& Item) { /*Nếu queue rỗng thì trả về false*/ if (isEmpty() == true) return false; Item = data[rear]; return true; } template<class T> bool Queue<T>::enqueue(const T Item) { /*Nếu ngăn xếp đầy thì trả về false*/ if (isFull() == true) return false; rear++; data[rear] = Item; return true; } template<class T> bool Queue<T>::dequeue(T &Item) { /*Nếu ngăn xếp rỗng thì trả về false*/ if (isEmpty() == true || front > rear) return false; Item = data[front]; front++; return true; } int main() { Queue<int> q(100); q.enqueue(1); q.enqueue(2); q.enqueue(3); q.enqueue(4); q.enqueue(5); q.enqueue(6); q.enqueue(7); int temp; while (q.dequeue(temp) ) { cout << temp << endl; } return 0; } |
|
1 2 3 4 5 6 7 |
1 2 3 4 5 6 7 |
Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !
