Khai báo queue C++
|
Queue(hàng đợi) là một loại container, được thiết kế để hoạt động theo kiểu FIFO (First- in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách. Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.  Khai báo queue: Để sử dụng queue, ta cần khai báo thư viện queue: 1 #include Các phương thức thành viên: Capacity:size()Trả về số lượng phần tử của queueempty()Trả về true(1) nếu queue rỗng, ngược lại là false (0)Element access:font()Truy xuất phần tử ở đầu queue (phần tử đầu tiên được thêm vào)back()Truy xuất phần tử ở cuối queue (phần tử cuối cùng được thêm vào)Modifier:push (const x)Thêm phần tử có giá trị x vào cuối queue. Kích thước queue tăng thêm 1.pop ()Loại bỏ phần tử ở đầu queue. Kích thước queue giảm đi 1.Capacity: size() Trả về số lượng phần tử của queue. Ví dụ: Tạo một queue có kích thước là 5 và in ra số lượng phần tử của queue này. 1 2 3 4 5 6 7 8 9 10 11 12 #include #include using namespace std; int main() { queue<int> myQueue ; for(int i =0 ; i < 5; i++) { myQueue.push(100) ; // 100 100 100 100 100 } cout << “The size of queue is: “ << myQueue .size()<< endl; return 0; } Lưu ý: Tương tự như stack, ta không thể khai báo queue Tương tự, ta không thể khai báo queue empty() Trả về true(1) nếu queue rỗng, ngược lại là false (0) Ví dụ: Kiểm tra queue có rỗng không và in ra thông báo tương ứng. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include #include using namespace std; int main() { queue<int> myQueue ; if( myQueue.empty()) { cout<<“queue is empty! “<<endl ; } else { cout<<“queue is not empty! “<<endl ; } return 0; } Element access: front() Truy xuất phần tử ở đầu queue (phần tử đầu tiên được thêm vào). Ví dụ: Tạo queue có 5 phần tử có giá trị lần lượt là A,B,C,D,E. Thay đổi phẩn tử đầu tiền thêm vào thành ‘a’. In ra phần tử ở đầu của queue sau khi thay đổi. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include #include using namespace std; int main() { queue<char> myQueue; // create a queue for(int i = 0 ; i<5; i++) { myQueue.push(‘A’+ i ) ; // A B C D E } // change queue cout<<“Before change, front is: “<<myQueue.front()<<endl ; myQueue.front() = ‘e’ ; cout<<“After change, front is: “<<myQueue.front()<<endl ; return 0; } back() Truy xuất phần tử ở cuối queue (phần tử cuối cùng được thêm vào). Ví dụ: Tạo queue có 5 phần tử có giá trị lần lượt là a,b,c,d,e. Thay đổi phẩn tử cuối cùng được thêm vào thành ‘E’. In ra phần tử cuối cùng của queue sau khi thay đổi. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include #include using namespace std; int main() { queue<char> myQueue; // create a queue for(int i = 0 ; i<5; i++) { myQueue.push(‘a’+ i ) ; //a b c d e } // change queue cout<<“Before change, back is: “<<myQueue.back()<<endl ; myQueue.back() = ‘E’ ; cout<<“After change, back is: “<<myQueue.back()<<endl ; return 0; } Modifier: push (const x) Thêm phần tử có giá trị x vào cuối queue. Kích thước queue tăng thêm 1. Phương thức push của queue tương tự như phương thức push_back của list. Ví dụ: Viết chương trình cho người dùng nhập vào kích thước queue và nhập vào giá trị các phần tử. In các phần tử trong queue. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include using namespace std; int main() { queue<int> myQueue; int n; // size of queue cout<<“Size: “ ; cin>>n ; // create queue int tempNumber ; for(int i = 0 ; i<n; i++) { cin>>tempNumber ; myQueue.push(tempNumber ) ; } // print queue for(int i = 0 ; i<n; i++) { tempNumber = myQueue.front() ; myQueue.pop(); cout<<tempNumber<<” “ ; } return 0; } Nhận xét: Khác với stack, thứ tự in các phần tử của queue sẽ giống như thứ tự mà ta nhập vào. 1 2 3 4 5 // WRONG way to print queue queue<int>::iterator it ; for( it = myQueue.begin() ; it!=myQueue.end(); it++) { cout<<*it<<” “ ; } pop () Loại bỏ phần tử ở đầu queue (phần tử đầu tiên được thêm vào queue) . Kích queue giảm đi 1. Ví dụ: Viết chương trình cho người dùng nhập vào kích thước queue và nhập vào giá trị các phần tử. Sau đó, loại bỏ đi một nửa các phần tử ở đầu 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 #include #include using namespace std; int main() { queue<int> myQueue; int n; // size of queue cout<<“Size: “ ; cin>>n ; // create queue int tempNumber ; for(int i = 0 ; i<n; i++) { cin>>tempNumber ; myQueue.push(tempNumber ) ; } // delete element for(int i = 0 ; i<n/2; i++) { myQueue.pop() ; } // print queue n = myQueue.size() ; // after using pop(), the size of queue < n for(int i = 0 ; i<n; i++) { tempNumber = myQueue.front() ; myQueue.pop(); cout<<tempNumber<<” “ ; } return 0; } Không phải hàm thành viên: swap(queue q1, queue q2) : Hoán đổi các phần tử của 2 queue với nhau. Lưu ý: khác với vector và list, swap không phải là hàm thành viên của đối tượng, do đó, hàm swap cần truyền vào 2 tham số. Ví dụ: Tạo queue thứ nhất có 3 phần tử 1,3,5 và queue thứ 2 có 2 phần tử 2,4. Hoán đổi các phần tử của hai queue. In ra kích thước của hai queue sau khi hoán đổi. |
