网站设计制作培训,影视cms哪个好,app运营需要做哪些,网络推广哪家好有效果队列
目录
概念
实现方式
顺序队列
循环队列
队列的数组实现
用循环链表实现队列
STL 之 queue 实现队列
STL 之 dequeue 实现双端队列 概念
队列是一种特殊的线性表#xff0c;它只允许在表的前端#xff08;称为队头#xff0c;front#xff09;进行删除操作…队列
目录
概念
实现方式
顺序队列
循环队列
队列的数组实现
用循环链表实现队列
STL 之 queue 实现队列
STL 之 dequeue 实现双端队列 概念
队列是一种特殊的线性表它只允许在表的前端称为队头front进行删除操作——出队而在表的后端称为队尾rear进行插入操作——入队是一种操作受限的线性表。
最先进入队列的元素最先被删除是“先进先出”的线性表。
实现方式
数组链表C 中可以使用 STL 中的 queue 实现其中 STL 中还包括双端队列 dequeue
顺序队列
必须静态分配或者动态申请空间并设置两个指针管理一个是队头指针 front指向队头元素另一个是队尾指针 rear指向下一个入队元素的存储位置。 队空的判断条件是frontrear队满的条件为rearMAXQSIZE。 循环队列
为了使队列空间可以重复使用可以对循环队列进行改进无论是插入或者删除一旦 rear 指针或者 front 指针超出了所分配的队列空间就让它指向这篇连续空间的起始位置自己从 MAXQSIZE 增 1 变为 1可以用取余运算实现 (rear1)%MAXQSIZE、 (front1)%MAXQSIZE. 其中队空的判断条件为frontrear队满的条件为rear1%MAXQSIZEfront。 队列的数组实现
定义一个结构体实现队列
struct node {int* data;int front;int rear;
};
初始化队列将队头和队尾指针都赋为 1数组长度为 MAXQSIZE开辟一块空间为 MAXQSIZE-1 的数组
//为队列开辟空间并初始化也可以在结构体中定义int data[MAXQSIZE])
void InitQueue(struct node Q) {Q.rear 1;Q.front 1;Q.data (int*)malloc(MAXQSIZE1 * sizeof(int));
}
入队
//入队
int EnQueue(struct node Q,int y) {if (Q.rear ! MAXQSIZE) {Q.data[Q.rear] y;Q.rear;return 1;}return 0;
}
出队
//出队
int DeQueue(struct node Q, int y) {if (Q.rear ! Q.front){y Q.data[Q.front];Q.front;return 1;}return 0;
}
总代码为
//数组实现队列
#includestdio.h
#includestdlib.h
#define MAXQSIZE 100
int queue[MAXQSIZE];
struct node {int* data;int front;int rear;
};
//为队列开辟空间并初始化也可以在结构体中定义int data[MAXQSIZE])
void InitQueue(struct node Q) {Q.rear 1;Q.front 1;Q.data (int*)malloc(MAXQSIZE1 * sizeof(int));
}
//入队
int EnQueue(struct node Q,int y) {if (Q.rear ! MAXQSIZE) {Q.data[Q.rear] y;Q.rear;return 1;}return 0;
}
//出队
int DeQueue(struct node Q, int y) {if (Q.rear ! Q.front){y Q.data[Q.front];Q.front;return 1;}return 0;
}
int main() {int n;int x, y;struct node Q;InitQueue(Q);//以1开头为插入(插入操作输入两个数以0开头为删除printf(输入操作个数(以1开头为插入(插入操作输入两个数以0开头为删除)\n);scanf(%d, n);while (n--) {printf(输入操作);scanf(%d, x);if (x 1){scanf(%d, y);if (EnQueue(Q, y))printf(入队成功\n);elseprintf(入队失败\n);}else if (x 0){if (DeQueue(Q, y) 0)printf(出队失败\n);elseprintf(出队的元素为%d\n,y);}else{printf(输入正确的操作\n);n;}}return 0;
}
用循环链表实现队列
不用循环时将初始化时的 Q-nextQ 删去。
以带头结点的循环链表表示队列并且只设一个指针指向队尾结点不设头指针。
定义一个结构体
struct node {int data;struct node* next;
};
入队
//入队
void EnQueue(struct node* Q, int y) {struct node* p;p (struct node*)malloc(sizeof(struct node));p-data y;p-next Q-next;Q-next p;Q p;
}
出队
//出队
int DeQueue(struct node* Q, int y) {if (Q-next Q)return 0;struct node* p;p Q-next;y p-data;Q-next p-next;free(p);return 1;
}
总代码
//以带头结点的循环链表表示队列
//并且只设一个指针指向队尾结点不设头指针。
#includestdio.h
#includestdlib.h
struct node {int data;struct node* next;
};
//循环队列的初始化
void InitQueue(struct node* Q) {Q-next Q;//初始化循环队列
}
//入队
void EnQueue(struct node* Q, int y) {struct node* p;p (struct node*)malloc(sizeof(struct node));p-data y;p-next Q-next;Q-next p;Q p;
}
//出队
int DeQueue(struct node* Q, int y) {if (Q-next Q)return 0;struct node* p;p Q-next;y p-data;Q-next p-next;free(p);return 1;
}
int main() {struct node* Q;Q (struct node*)malloc(sizeof(struct node));InitQueue(Q);printf(输入操作个数(以1开头为插入(插入操作输入两个数以0开头为删除)\n);int x, y, n;scanf(%d, n);while(n--){printf(输入操作);scanf(%d, x);if(x1){scanf(%d, y);EnQueue(Q, y);printf(入队成功\n);}else if(x0){if (DeQueue(Q, y) 1)printf(%d\n, y);elseprintf(出队失败\n);}}return 0;
}
STL 之 queue 实现队列
要加上头文件#includequeue
对应的函数
构造空队列
queueintq;
总代码
//用queue函数实现队列
#includeiostream
#includequeue
using namespace std;
int main() {queueintq;int n;int x, y;printf(输入操作个数);scanf(%d, n);printf(以1开头为插入(插入操作输入两个数以0开头为删除\n);while (n--) {scanf(%d, x);if (x 1) {scanf(%d, y);q.push(y);}else if(x0){if (!q.empty()) {//判断队列不为空printf(%d\n, q.front());q.pop();}elseprintf(出队失败\n);}else{printf(输入正确的操作\n);n;}printf(队列中元素个数为%d\n, q.size());}return 0;
}
STL 之 dequeue 实现双端队列 //用dequeue实现双端队列
#includeiostream
#includedeque
using namespace std;
struct node {int *data;
}Q;
int main() {dequeintq(10);dequeint::iterator idex;for (int i 0; i 10; i) {q[i] i;}for (int i 0; i 10; i) {printf(%d , q[i]);}printf(\n);//在头尾加入新元素printf(加入新元素后\n);q.push_back(100);//加入队尾q.push_front(10);//加入队头printf(输出deque的数据\n);for (idex q.begin(); idex ! q.end(); idex) {printf(%d , *idex);}printf(\n);//查找int x 5;idex find(q.begin(), q.end(), x);if (idex ! q.end())printf(找到%d元素\n,x);elseprintf(队列中没有%d元素\n,x);//在头尾删除数据q.pop_back();//删除队尾q.pop_front();//删除队头printf(输出deque的数据\n);for (idex q.begin(); idex ! q.end(); idex) {printf(%d , *idex);}return 0;
}