编程C本: 帖子 16 – 建筑队列 (队列)
[qads]
队列 (队列) 是在FIFO下用于存储数据结构的对象的工作 (英文缩写: 先进先出), 意味着 “先出” 在队列, 对象可以被添加到队列随时, 但仅加入到第一对象将被允许离开队列. 添加对象总是发生在队列的末尾，并总是一个元件被从队列的头部取出.
内容
1. 安装在阵列上的队列
根本 堆, 我们可以使用计数在堆栈的元素数 1 算 (算) 轻松, 在这节中，我将使用队列计数器结构.
#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 初始化一个空队列.
要开始，我们需要创建在前面一个空的队列位置 0, 后方 -1, COUT约 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 检查队列为空, 满
检查全镂空只检查数量比 0 和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 将元素添加到队列的末尾 (推)
后排位置增加 1 并提供有关位置的数据
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 除去第一元件队列 (流行的)
首先要检查队列为空, 如果不是empty're在循环中的第一行的行中进行移动元件 (就像排队买的时候) 进而降低后和倒计时.
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 查看第一个元素队列
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 排队轮 (队列通知)
由于我们所建立的基于队列的阵列, 看看 1 缺点是删除队列我们需要移动的身前身后的所有元素的第一个元素. 为了解决这个问题，我们可以看到阵列 1 与分子阵列排圆.
然后，我们可以添加, 简单地删除元素, 然而应当指出的添加和删除时元素后和前在阵列的端 (马克斯 - 1). 为了克服鸿沟前后超额利差为最大. 前部和后部因此，如果最大值将返回到位置 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 完整的程序 (完整的代码)
#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. 用光标队列设置
2.1 建筑结构
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 初始化.
初始化前后队列我们NULL指针, 数= 0.
void Init(Queue &Q)
{
Q.Front = Q.Rear = NULL;
Q.count = 0;
}
2.3. 检查空
int Isempty (Queue Q) //kiem tra Queue rong
{
if (Q.count == 0) //so phan tu = 0 => rong
return 1;
return 0;
}
2.4 创建 1 节点P
Node *MakeNode(item x) //tao 1 Node
{
Node *P = (Node*) malloc(sizeof(Node));
P->Next = NULL;
P->Data = x;
return P;
}
2.5 将元素添加到队列的末尾
添加元素, 我们检查是否有一个空行, 如果该行是空的，正面和背面均指向包含该元素的新创建的P节点X更. 如果不为空一点后轮>接下来的点P和后P. 增加计数 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 除去第一元件队列
我检查了队列为空, 如果没有检查空 1 和更 1 元素, 如果有 1 元素，我们初始化队列, 如果一个以上的点到下一个的前端. 减少倒计时 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 完整的程序 (完整的代码)
#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. 使用Queu用C 提供
如 堆仲C , 队列建成，我们只只使用.
#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. 队列中的应用
队列是用来消除递归, 机构根据该宽度和回溯保持搜索过程的轨道, 详细, 在操作系统中组织管理和分配过程, 组织键盘缓冲区.
[RPS-包括交=”2703″ 简码=”假”]
服务员, 每节课你可以添加一些练习是不是你?
每个岗位的任务啊. 中小企业, a sẽ cố gắng 🙂
哦，他可以让他的.doc文件以了解我们是下跌了约设施不是你
按CTRL + s被保存在这个整篇文章. 经过短短打开HTML文件保存为处理完毕.
我弟弟拷贝材料您发布队列设置光标其中k运行再见DC
我仍然运行正常. 创建和保存文件为*的.cpp (VD TEST.CPP) NHE.
是的… 保存文件作为电子邮件的.c先生时，误机
h I类希望我的这种结构项目k的只有
的typedef INT项目
要保存NTN
typedef结构{
焦炭hoten[30];
INT masv;
车队DTB;
}项目;
他们必须解决上述NTN先生代码
我感谢你
同时，只有更换时只进口货. 例如，下面是项目在原料进口型, 您随后进口的结构的结构. Ở đây so sánh giá trị nguyên thì bạn so sánh 1 结构学校.
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ế ạ 😀
无效初始化(队列 &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
空推(队列 &Q, X项); //them phan tu vao cuoi hang doi
INT流行(队列 &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 ạ
颚
+Void Push(Queue *Q, X项); //them phan tu vao cuoi hang doi
+ INT流行(Queue *Q); //Loai bo phan tu khoi dau hang doi
+ 无效初始化(Queue *Q)
và kiểu item của e h k chỉ đơn giản là int nữa mà là kiểu
typedef结构{
焦炭hoten[30];
INT masv;
车队DTB;
}项目;
đ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
写作是 1 事, 全文可在不使用则是另一回事. 我一直在写，让你使用只够.
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++ 🙂
非常感谢你
祝贺 :))
hì'm会写，所有这些年后… 但更具体的记录 2 年 :)) 删除所有剩余的字母ķ “包” :))
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流行(队列 &Q) //Loai bo phan tu khoi dau hang doi
{
如果 (是空的(Q))
{
的printf(“Hang doi rong !”);
回报 0;
}
其他
{
item x = Q.Front->Data;
如果 (Q.count == 1) //neu co 1 phan tu
Init(Q);
其他
Q.Front = Q.Front->下一个;
Q.count –;
return x; //tra ve phan tu lay ra
}
}
声明 : 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, ħ — đi nữa thì nó =-1.
亲爱!
感谢您的反馈. 我会检讨.
感谢您的反馈. 我会检讨.
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, 坦克, 浮动) thì chỗ typedef thay đổi như thế nào đề phù hợp với item ở dưới ạ, em cảm ơn 😄
这一点，他也不清楚.
嗨哥. 你的帖子很不错, 但是，队列未满时的入队部分, 我们可以将后部向后移动 0 而不是将 Queue 的所有元素移到开头, 当然它没有错，但它不会是最佳的. 谢谢
旋转部分的代码看不到旋转, 请查看所有完整代码
您有编辑建议吗？, 贴出来供大家参考.