Programming C: Posts 16 – Construction queue (Queue)
[qads]
Queues (Queue) is a data structure used to store objects work under the FIFO (acronym in English: First In First Out), mean “in first-out” In the queue, Objects can be added to the queue at any time, but only added to the first object will be allowed to get out of the queue. Adding an object always takes place at the end of the queue and always an element is removed from the head of the queue.
Content
1. Queue installed on the array
At all Stack, we can count the number of elements in the stack using 1 count (count) for easy, and in this section I will use Queue counter that the structure.
#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 Initialize an empty Queue.
To start we need to create an empty Queue location on Front 0, Rear of -1, cout about 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 Check Queue is empty, full
Check full hollow just check count than 0 and 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 Adding elements to the end of Queue (Push)
Rear position to increase 1 and provide data on the position
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 Remove the first element Queue (Pop)
First to check Queue empty, if not empty're done moving elements in the row of the first row in loop (Like queue when buying) then reduce Rear and count down.
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 View first element 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 queues round (Queue Circular)
As we build on the Queue-based array, and see 1 disadvantage is the first element removed Queue we need to move all the elements behind the front. To remedy this we can see the array as 1 with the molecular array ranked circle.
Then we can add, simply remove the element, however it should be noted when adding and removing elements that Rear and Front at the end of the array (Max-1). To overcome the divide Front and Rear excess spread for Max. Front and Rear So if Max will return to the position 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 Complete program (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 settings with the cursor
2.1 Building structures
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 Initialization.
Initialize Front and Rear Queue us for the NULL pointer, count =0.
void Init(Queue &Q)
{
Q.Front = Q.Rear = NULL;
Q.count = 0;
}
2.3. Check Empty
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
2.4 Create 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 Adding elements to the end of Queue
To add an element, we check if there is an empty line, if the row is empty, Front and Rear both pointing to the newly created P Node containing the element x to more. If not empty one point Rear->Next on the point P and Rear P. Increase count up 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 Remove the first element Queue
I checked Queue empty, If not check for null 1 and much more 1 element, if there 1 element, we initialize the Queue, if more than one point to the next for the Front. Reduced count down 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 Complete program (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. Use Queu available in C
Like Stack trong C , Queue is built and we only use only.
#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. Application of the queue
Queue is used to eliminate recursion, organizations keep track of the search process according to the width and backtracking, exhaustive, organizational management and distribution processes in the operating system, organization keyboard buffer.
[rps-include post=”2703″ shortcodes=”false”]
Waiter, each lesson you can add a few exercises are not you?
Exercise of each post ah. Sme, a sẽ cố gắng 🙂
My brother he could to .doc file to learn we were down to no sir amenities
You hit ctrl + s is to save this entire article. After just open the html file is saved to be completed.
em-copy the original darling queue all set with your cursor where k run a bye DC
I still run fine. You create and save the file as * .cpp (VD test.cpp) nhé.
yes… machine error saving e .c file ạ
h I want to type my item k structure is only
typedef int item
where you want to save ntn
typedef struct{
char threats[30];
int masv;
float dtb;
}item;
it must fix the code on ntn ạ
thank you
Meanwhile, only replaced when only imported item. For example here in the imported item is type integer, then enter your struct ones in struct. Here compare integer values, you compare 1 field in struct.
DC Kids know the margin under the cursor should look like is * Q
cái VD int *Q
even as he declared int Q Is pointers anyway
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 ạ
Jaw
+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 threats[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); //see molecular information in your head of the queue Where.
I do not see use
Writing is 1 matter, full article can be used in not is another story. I keep writing to let you use only enough.
Anh ơi anh có thế làm 1 tutorial is not sir tree ?
In algorithmic menu t have written several articles about your tree.
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 year :)) xóa k hết còn chữ “newspaper” :))
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 element
Init(Q);
else
Q.Front = Q.Front->Next;
Q.count –;
return x; //molecular investigation lay out
}
}
Statement : Q.count –; must book within else, otherwise it will make q_size = -1 as above if there is a queue size = 1, it will pop out, queue size =0, h — away it = -1.
God!
Thank you for feedback. I will review.
Thank you for feedback. I will review.
star array m run code by faulty sir anybody help m vs tks !
You have to see what error knows how to fix rather.
Waiter let me ask, nếu viết queue mà có thể chạy cho tất cả mọi biến (int, tank, 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õ.
Hello. 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 section not see DC rotate rotation, please review the entire code complete
You have not proposed edits, bring up people refer.