HÀNG ĐỢI
QUEUE

KHÁI NIỆM

Hàng đợi là một danh sách tuyến tính,
trong đó:

Việc bổ sung một phần tử vào hàng đợi được
thực hiện ở một đầu gọi là cuối hàng

Việc loại bỏ một phần tử ra khỏi hàng đợi được
thực hiện ở đầu kia gọi là đầu hàng.

Danh sách kiểu hàng đợi còn gọi là danh
sách FIFO – First In First Out.

KHÁI NIỆM
A B C D E F
Đầu hàng Cuối hàng
Loại bỏ
Bổ sung
Hình vẽ biểu diễn hàng đợi

BIỂU DIỄN CẤU TRÚC DỮ LIỆU

Giả sử các phần tử của HĐ có kiểu dữ liệu là Item, độ dài của HĐ
là N

HĐ được lưu trong BNMT bởi mảng 1 chiều (lưu trữ kế tiếp).


CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
void Initialize (Queue &Q)
{
Q.front = 0;
Q.rear = -1;
}

1. Khởi tạo hàng đợi rỗng
int Empty (Queue Q)
{
return (Q.rear == -1);
}

2. Kiểm tra hàng đợi rỗng

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
1 2 3 4 5 6 7 8 9
Max=10
front = 0 rear = -1
E
Biểu diễn hàng đợi rỗng
0

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI

3. Kiểm tra hàng đợi đầy
int Full (Queue Q)
{
reurn (Q.rear == Max-1);

4. Bổ sung một phần tử vào cuối hàng đợi
G
0
X

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
A B C D E F G
1 2 3 4 5 6 7 8 9
10 = Max
front = 2 rear = 8
E
Mảng lưu trữ hàng đợi

4. Bổ sung một phần tử vào cuối hàng đợi
0

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
int AddQ(Queue &Q, Item X)
{
If (Full(Q))
return 0;
else
{
Q.rear++;
Q.E[Q.rear] = X;
return 1;
}
}
Hàm AddQ thực hiện bổ sung một phần tử vào cuối hàng, hàm trả về 1
nếu bổ sung thành công, ngược lại hàm trả về 0

X

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
B
1 2 3 4 5 6 7 8 9
10 = Max
front = 3
rear = 3
E
Mảng lưu trữ hàng đợi

5. Lấy ra một phần tử ở đầu hàng đợi

Trường hợp hàng đợi có 1 phần tử
0
X

CÁC PHÉP TOÁN TRÊN HÀNG ĐỢI
1 2 3 4 5 6 7 8 9
10 = Max
front = 0 rear = -1
E
Hàng đợi rỗng

5. Lấy ra một phần tử ở đầu hàng đợi

Trường hợp hàng đợi có 1 phần tử
B
0
X