Giới thiệu về queue:
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 <queue>
|
Các phương thức thành viên:
| Capacity: | |
| size() | Trả về số lượng phần tử của queue |
| empty() | 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 <iostream>
#include <queue>
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<int> myQueue (5) để khai báo 5 phần tử rỗng tương tự như vector hay list vì queue không cho phép ta khai báo phần tử rỗng.
Tương tự, ta không thể khai báo queue<int> myQueue (5,100) để khai báo 5 phần tử của queue có giá trị 100.
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 <iostream>
#include <queue>
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 <iostream>
#include <queue>
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 <iostream>
#include <queue>
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 <iostream>
#include <queue>
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.
Tương tự như stack, không thể sử dụng vòng lặp với biến iterator như đối list để in tất cả các phần tử vì queue chỉ cho phép truy xuất duy nhất phần tử ở đầu queue. Ví dụ, mã lệnh truy xuất queue như bên dưới là sai:
|
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 <iostream>
#include <queue>
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.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// swap queues
#include <iostream> // std::cout
#include <queue> // std::queue, std::swap(queue)
using namespace std ;
int main ()
{
queue<int> queue1,queue2;
queue1.push(1);
queue1.push(3);
queue1.push(5); // size of queue1 is 3
queue2.push(2);
queue2.push(4); // size of queue2 is 2
// exchange 2 queues
swap(queue1,queue2);
cout << “size of queue1: “ << queue1.size() << ‘n’;
cout << “size of queue2: “ << queue2.size() << ‘n’;
return 0 ;
}
|
