数据结构 -- 队列 & 循环队列 -- 数组实现

数据结构 -- 队列 & 循环队列 -- 数组实现

队列是一种特殊的​​线性表​​，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

以数组实现的队列结构，如果是普通队列，频繁增删元素，会造成数组内存空间的大量流失，所以便有了循环队列，以填补流失的内存空间。

1. 普通队列实现代码：

#include #include #include #include using namespace std;#define MAXN 100#define PUSH_ERROR 0x1#define POP_ERROR 0x2/*front : 队列头队列大小为MAXNtail : 队列尾*/typedef struct que{ int arr[MAXN]; int front,tail;};//初始化队列void init_que(que *q){ q->front = 0; q->tail = 0;}//入队列int push(que *q , int val){ if (q->tail < MAXN) { q->arr[q->tail++] = val; }else{ return PUSH_ERROR; } return 0;}//出队列int pop(que *q){ if (q->front != q->tail) { q->front++; }else{ return POP_ERROR; } return 0;}//求队列大小int calc_size(que *q){ return q->tail-q->front;}//求队列头元素int front(que *q){ return q->arr[q->front];}int main(void){ int test = 0; que *q = (que*)malloc(sizeof(que)); init_que(q); push(q,1); push(q,3); push(q,2); test = calc_size(q); printf("QUE_SIZE : %d\n",test); pop(q); test = front(q); printf("QUE_FRONT : %d\n",test); pop(q); test = calc_size(q); printf("QUE_SIZE : %d\n",test); return 0;}

2. 循环队列实现代码：

#include #include #include #include using namespace std;#define MAXN 4#define PUSH_ERROR 0x1#define POP_ERROR 0x2/*front : 队列头由于front指针指向元素置为空，所以队列大小为MAXN-1tail : 队列尾*/typedef struct que{ int arr[MAXN]; int front,tail;};//初始化队列void init_que(que *q){ q->front = 0; q->tail = 0;}//入队列int push(que *q , int val){ q->tail++; if (q->tail != q->front) { q->arr[(q->tail)%MAXN] = val; }else{ return PUSH_ERROR; } return 0;}//出队列int pop(que *q){ q->front++; if (q->front != q->tail) { q->front = (q->front)%MAXN; }else{ return POP_ERROR; } return 0;}//求队列大小int calc_size(que *q){ return q->tail-q->front;}//求队列头元素int front(que *q){ return q->arr[q->front+1];}int main(void){ que *q = (que*)malloc(sizeof(que)); init_que(q); push(q,1); push(q,3); push(q,2); pop(q); push(q,20); printf("QUE_SIZE : %d\n",calc_size(q)); printf("QUE_FRONT : %d\n",front(q)); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。