Lập trình C: Bài 16 – Xây dựng hàng đợi (Queue)
[qads]
Hàng đợi (Queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng làm việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước” Trong hàng đợi, các đối tượng có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.
Nội dung
1. Queue cài đặt trên mảng
Ở bài Stack, chúng ta có thể đếm số phần tử trong Stack bằng cách dùng 1 biến đếm (count) để cho dễ dàng, và ở phần Queue này tôi sẽ sử dụng biến đếm đó trong cấu trúc.
#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu
struct Queue
{
int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
item Data[Max]; //Mang cac phan tu
int count; //dem so phan tu cua Queue
};
1.1 Khởi tạo Queue rỗng.
Để khởi tạo Queue rỗng ta cần đưa vị trí Front về 0, Rear về -1, cout về 0.
void Init (Queue &Q) //khoi tao Queue rong
{
Q.Front = 0; //phan tu dau
Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
Q.count = 0; //so phan tu bang 0
}
1.2 Kiểm tra Queue rỗng, đầy
Kiểm tra rỗng đầy chỉ cần kiểm tra count so với 0 và max
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
int Isfull (Queue Q) //kiem tra Queue day
{
if (Q.count == Max) //so phan tu = Max => day
return 1;
return 0;
}
1.3 Thêm phần tử vào cuối Queue (Push)
Tăng vị trí của Rear lên 1 và đưa data vào vị trí đó
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
Q.count++; //tang so phan tu len
}
}
1.4 Xóa phần tử đầu Queue (Pop)
Trước tiên phải kiểm tra Queue rỗng không, nếu không rỗng ta thực hiện di chuyển các phần tử trong hàng về đầu hàng bằng vòng for (giống như xếp hàng khi mua hàng) sau đó giảm Rear và count xuống.
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q)) printf("Hang doi rong !");
else
{
item x = Q.Data[Q.Front];
for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
Q.Data[i] = Q.Data[i+1];
Q.Rear--; // giam vi tri phan tu cuoi xuong
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
}
1.5 Xem thông tin phần tử đầu Queue
item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
if (Isempty(Q)) printf("Hang doi rong !");
else return Q.Data[Q.Front];
}
1.6 hàng đợi vòng (Queue Circular)
Như trên chúng ta xây dựng Queue dựa vào mảng, và thấy 1 điểm bất lợi là khi xóa phần tử đầu Queue chúng ta cần di chuyển tất cả các phần tử phía sau về trước. Để khắc phục điều này chúng ta có thể coi mảng đó như 1 mảng với các phân tử được xếp vòng tròn.
Khi đó ta có thể thêm, xóa các phần tử đơn giản, tuy nhiên cần lưu ý khi thêm và xóa phần tử mà Rear và Front ở cuối mảng (Max-1). Để khắc phục ta chia Front và Rear lây dư cho Max. Vậy là Nếu Front và Rear ở Max thì sẽ trở về vị trí 0.
void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[(++Q.Rear) % Max] = x;
//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
Q.count++; //tang so phan tu len
}
}
int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
if (Isempty(Q)) printf("Hang doi rong !");
item x = Q.Data[Q.Front];
Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
1.7 Chương trình hoàn chỉnh (full code)
#include <stdlib.h>
#include <stdio.h>
#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu
struct Queue
{
int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
item Data[Max]; //Mang cac phan tu
int count; //dem so phan tu cua Queue
};
void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
int Isfull(Queue Q); //kiem tra Queue day
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi
void Push_Circular(Queue &Q, item x); //them phan tu vao cuoi hang doi vong
int Pop_Circular(Queue &Q); //Loai bo phan tu khoi dau hang doi vong
void Input (Queue &Q); //Nhap
void Output(Queue Q); //Xuat
void Init (Queue &Q) //khoi tao Queue rong
{
Q.Front = 0; //phan tu dau
Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
Q.count = 0; //so phan tu bang 0
}
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
int Isfull (Queue Q) //kiem tra Queue day
{
if (Q.count == Max) //so phan tu = Max => day
return 1;
return 0;
}
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
Q.count++; //tang so phan tu len
}
}
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q)) printf("Hang doi rong !");
else
{
item x = Q.Data[Q.Front];
for (int i=Q.Front; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
Q.Data[i] = Q.Data[i+1];
Q.Rear--; // giam vi tri phan tu cuoi xuong
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
}
item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
if (Isempty(Q)) printf("Hang doi rong !");
else return Q.Data[Q.Front];
}
void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
if (Isfull(Q)) printf("Hang doi day !");
else
{
Q.Data[(++Q.Rear) % Max] = x;
//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
Q.count++; //tang so phan tu len
}
}
int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
if (Isempty(Q)) printf("Hang doi rong !");
item x = Q.Data[Q.Front];
Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0
Q.count--;//giam so phan tu xuong
return x; //tra ve phan tu lay ra
}
void Input (Queue &Q) //nhap hang doi
{
int n;
item x;
do
{
printf("Nhap so phan tu cua Queue (<%d) :",Max);
scanf("%d",&n);
} while (n>Max || n<1);
for (int i=0; i<n; i++)
{
printf("Nhap phan tu thu %d : ", i+1);
scanf("%d",&x);
Push(Q,x);
Push_Circular(Q,x); //hang vong
}
}
void Output(Queue Q)
{
if (Isempty(Q)) printf("Hang doi rong !");
else
{
for (int i=Q.Front; i<=Q.Rear; i++)
//for (int i=Q.Front, j=0; j<Q.count; j++, i = (i++) % Max) //hang vong
printf("%d ",Q.Data[i]);
printf("\n");
}
}
int main()
{
Queue Q;
Init(Q);
Input(Q);
Output(Q);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra Queue rong");
printf("\n2: Kiem tra Queue day");
printf("\n3: Them phan tu vao Queue");
printf("\n4: Xoa phan tu trong Queue");
printf("\n5: Xuat Queue");
printf("\n6: Thoat");
do
{
printf("\nBan chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(Q)) printf("Queue rong !");
else printf ("Queue khong rong !");
break;
}
case 2:
{
if (Isfull(Q)) printf("Queue day !");
else printf ("Queue chua day !");
break;
}
case 3:
{
item x;
printf ("Nhap phan tu can chen vao Queue: ");
scanf("%d",&x);
Push(Q,x);
//Push_Circular(Q,x); hang vong
break;
}
case 4:
{
Pop(Q);
//Pop_Circular(Q); hang vong
break;
}
case 5:
{
Output(Q);
break;
}
case 6: break;
}
}while (lua_chon !=6);
return 0;
}
2. Queue cài đặt bằng con trỏ
2.1 Xây dựng cấu trúc
typedef int item; //kieu du lieu
struct Node
{
item Data;
Node * Next;
};
struct Queue
{
Node * Front, *Rear; //Node dau va Node cuoi
int count; //dem so phan tu
};
2.2 Khởi tạo.
Khởi tạo Queue ta cho Front và Rear cùng trỏ về NULL, count =0.
void Init(Queue &Q)
{
Q.Front = Q.Rear = NULL;
Q.count = 0;
}
2.3. Kiểm tra rỗng
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
2.4 Tạo 1 Node P
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
2.5 Thêm phần tử vào cuối Queue
Để thêm phần tử, ta kiểm tra xem hàng có rỗng không, nếu hàng rỗng thì cho cả Front và Rear cùng trỏ về Node P mới tạo chứa phàn tử x cần thêm. Nếu không rỗng ta trỏ Rear->Next về P và Rear trỏ về P. Tăng count lên 1
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
Node *P = MakeNode(x); //Neu Q rong
if (Isempty(Q))
{
Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
}
else //Khong rong
{
Q.Rear->Next = P;
Q.Rear = P;
}
Q.count ++ ; //tang so phan tu len
}
2.6 Xóa phần tử đầu Queue
Ta kiểm tra Queue có rỗng không, Nếu không rỗng kiểm tra xem có 1 hay nhiêu hơn 1 phần tử, nếu có 1 phần tử thì ta khởi tạo lại Queue, nếu có nhiều hơn ta cho Front trỏ đến tiếp theo. Giảm count xuống 1.
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q))
{
printf("Hang doi rong !");
return 0;
}
else
{
item x = Q.Front->Data;
if (Q.count == 1) //neu co 1 phan tu
Init(Q);
else
Q.Front = Q.Front->Next;
Q.count --;
return x; //tra ve phan tu lay ra
}
}
2.7 Chương trình hoàn chỉnh (full code)
#include <stdlib.h>
#include <stdio.h>
typedef int item; //kieu du lieu
struct Node
{
item Data;
Node * Next;
};
struct Queue
{
Node * Front, *Rear; //Node dau va Node cuoi
int count; //dem so phan tu
};
void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi
Node *MakeNode(item x); //tao 1 Node
void Input (Queue &Q); //Nhap
void Output(Queue Q); //Xuat
void Init(Queue &Q)
{
Q.Front = Q.Rear = NULL;
Q.count = 0;
}
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
Node *P = MakeNode(x); //Neu Q rong
if (Isempty(Q))
{
Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
}
else //Khong rong
{
Q.Rear->Next = P;
Q.Rear = P;
}
Q.count ++ ; //tang so phan tu len
}
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q))
{
printf("Hang doi rong !");
return 0;
}
else
{
item x = Q.Front->Data;
if (Q.count == 1) //neu co 1 phan tu
Init(Q);
else
Q.Front = Q.Front->Next;
Q.count --;
return x; //tra ve phan tu lay ra
}
}
void Input (Queue &Q) //nhap hang doi
{
int i=0;
item x;
do
{
i++;
printf ("Nhap phan tu thu %d : ",i);
scanf("%d",&x);
if (x != 0) Push(Q,x);
} while(x != 0); //nhap 0 de ket thuc
}
void Output(Queue Q)
{
Node *P = Q.Front;
while (P != NULL)
{
printf("%d ",P->Data);
P = P->Next;
}
printf("\n");
}
int main()
{
Queue Q;
Init(Q);
Input(Q);
Output(Q);
int lua_chon;
printf("Moi ban chon phep toan voi DS LKD:");
printf("\n1: Kiem tra Queue rong");
printf("\n2: Them phan tu vao Queue");
printf("\n3: Xoa phan tu trong Queue");
printf("\n4: Xuat Queue");
printf("\n5: Thoat");
do
{
printf("\nBan chon: ");
scanf("%d",&lua_chon);
switch (lua_chon)
{
case 1:
{
if (Isempty(Q)) printf("Queue rong !");
else printf ("Queue khong rong !");
break;
}
case 2:
{
item x;
printf ("Nhap phan tu can chen vao Queue: ");
scanf("%d",&x);
Push(Q,x);
break;
}
case 3:
{
Pop(Q);
break;
}
case 4:
{
Output(Q);
break;
}
case 5: break;
}
}while (lua_chon !=5);
return 0;
}
3. Sử dụng Quêu có sẵn trong C++
Giống như Stack trong C++, Queue cũng được xây dựng và ta chỉ việc dùng mà thôi.
#include <iostream>
#include <queue> // su dung queue
using namespace std;
int main() {
queue <int> Q; // khai bao queue co kieu nguyen
for (int i = 0; i < 10; i++) {
Q.push(i * 78 + 26); // them phan tu vao queue
}
cout << "So luong phan tu trong queue: " << Q.size() << "\n";
while (!Q.empty()) { // trong khi queue khong rong
int x = Q.front(); // lay gia tri dau hang
Q.pop(); // xoa gia tri dau hang
cout << x << " ";
}
cout << "\n";
return 0;
}
4. Ứng dụng của queue
Queue được dùng để khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.
[rps-include post=”2703″ shortcodes=”false”]
Anh ơi, mỗi một bài học anh có thể cho thêm một vài bài tập được không ạ?
Bài tập của từng bài ah. Ukm, a sẽ cố gắng 🙂
anh ơi anh có thể để file .doc để bọn em down về tiện học không ạ
Bạn ấn ctrl + s là lưu toàn bộ bài này. Sau chỉ việc mở file html đã lưu được là xong.
anh ơi em coppy nguyên cái bài queue cài bằng con trỏ mà k chạy đc anh ạ
Mình vẫn chạy ổn mà. Bạn tạo và lưu file dưới dạng *.cpp (VD test.cpp) nhé.
vâng… máy e lỗi khi lưu file là .c ạ
h em muốn kiểu cấu trúc item của em k chỉ là
typedef int item
mà em muốn lưu ntn
typedef struct{
char hoten[30];
int masv;
float dtb;
}item;
thì đoạn code trên phải sửa ntn ạ
em cám ơn anh
Khi đó thì chỉ cần thay là khi nào nhập item thôi. VD ở đây item là kiểu in thì nhập số nguyên, của bạn là struct thì nhập những cái có trong struct. Ở đây so sánh giá trị nguyên thì bạn so sánh 1 trường trong struct.
theo em đc biết thì biên con trỏ phải có dạng là *Q
cái VD int *Q
còn như anh khai báo int Q có phải là con trỏ đâu nhỉ
Mình viết int Q ở đoạn nào đó bạn, mình chưa tìm thấy? đúng là int *Q thì Q là con trỏ, Nhưng nếu định nghĩa một kiểu như:
typedef int* Quan;
Quan Q
thì Q vẫn là con trỏ nhá.
em chỉ VD thế thôi chứ e k bảo anh code như thế ạ 😀
void Init(Queue &Q)
tại sao không phải void Init(Queue *Q)
thầy giáo em bảo lí do là
sau khi dùng hàm init- hàm tạo 1 cái j đó rỗng (ở đây là tạo queue rỗng ) thì spt thay đổi nên phải dùng *Q. nhưng a dùng &Q vẫn có thể chạy được. anh có thể giải thích cho em quả này đc k ạ. tks a
Cách dùng *Q là của C, còn trong C++ có hỗ trợ dùng &Q, nó hay hơn *Q 😉 Nếu quan tâm bạn có thể search chúng 😉
tương tự với các hàm thêm và xóa
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
tại sao không phải là *Q như thầy e dậy ( thầy e bắt phải dùng *Q) k dùng k đc 😀
mà a dùng thì vẫn mượt ạ….
a có thể sửa hộ em cái code trên mà dùng các hàm sau = *Q đc k ạ
Hàm
+Void Push(Queue *Q, item x); //them phan tu vao cuoi hang doi
+ int Pop(Queue *Q); //Loai bo phan tu khoi dau hang doi
+ void Init(Queue *Q)
và kiểu item của e h k chỉ đơn giản là int nữa mà là kiểu
typedef struct{
char hoten[30];
int masv;
float dtb;
}item;
đc ntn thì e mừng lắm ạ… e đang code nhưng mà sai ở đâu ý tìm mãi k đc… a thử code rồi up nên đây để em so sách với ! em cám ơn anh ạ
Cái này bạn tự làm được mà. 😉 Cố lên!
Bạn ơi cho mình hỏi thế cái hàm int Qfront (Queue Q); //xem thong tin phan tu dau hang doi của bạn ở đâu rồi.
Mình không thấy sử dụng
Viết ra là 1 chuyện, trong bài toàn có cần dùng không là chuyện khác. Mình cứ viết ra cho đủ để các bạn dùng thôi.
Anh ơi anh có thế làm 1 bài hướng dẫn về cây được không ạ ?
Trong menu thuật toán t có viết mấy bài về cây đó bạn.
sau bao 2 năm học c
h em đã pro hơn trước là viết đc code c++ 🙂
cảm ơn anh nhiều
Chúc mừng bạn :))
hì đang định viết là sau bao nhiêu năm… nhưng ghi cụ thể hơn là 2 năm :)) xóa k hết còn chữ “bao” :))
Code này có 2 điểm theo mình là sai:
1> Cấp phát động 1 node Node *P = MakeNode(x); //Neu Q rong
ở hàm push nhưng k giải phóng ở hàm pop==> leak mem, PC thì k sao chứ đặc biệt nguy hiểm ở các ứng dụng nhúng.
2>
int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
if (Isempty(Q))
{
printf(“Hang doi rong !”);
return 0;
}
else
{
item x = Q.Front->Data;
if (Q.count == 1) //neu co 1 phan tu
Init(Q);
else
Q.Front = Q.Front->Next;
Q.count –;
return x; //tra ve phan tu lay ra
}
}
Câu lệnh : Q.count –; phải đặt trong vòng else, nếu không nó sẽ làm cho q_size =-1 vì ở trên nếu queue có size =1 thì nó sẽ pop ra, queue size =0, h — đi nữa thì nó =-1.
Thân!
Cảm ơn bạn đã góp ý. Mình sẽ xem lại.
Cảm ơn bạn đã góp ý. Mình sẽ xem lại.
sao code bằng mảng m chạy bị lỗi ạ ai giúp m vs tks !
Bạn phải xem lỗi gì mới biết cách khắc phục chứ.
Anh ơi cho em hỏi, nếu viết queue mà có thể chạy cho tất cả mọi biến (int, char, float) thì chỗ typedef thay đổi như thế nào đề phù hợp với item ở dưới ạ, em cảm ơn 😄
Cái này anh cũng chưa rõ.
Hi anh. Bài viết của anh khá hay, tuy nhiên phần enqueue khi queue chưa full, ta có thể chuyển rear về 0 thay vì dịch chuyển tất cả các phần tử của Queue về đầu, tất nhiên là nó không sai nhưng sẽ không tối ưu. Thanks
code phần xoay vòng không thấy đc sự xoay vòng, vui lòng xem lại toàn bộ code hoàn chỉnh
Bạn có đề xuất chỉnh sửa không, đưa lên mọi người tham khảo.