c数据结构第三讲 队列

队列是⼀种特殊的线性表特殊之处就在于它只允许在表的前端进⾏删除操作在表的后端进⾏插⼊操作。和栈⼀样队列也是⼀种操作受到限制的线性表。进⾏插⼊操作的端称之为队尾进⾏删除操作的端称之为队头。队列中没有队列的时候称之为空队列。队列的数据元素⼜叫做队列元素。在队列中插⼊⼀个队列元素称之为⼊队在队列中删除⼀个队列元素称之为出队。因为队列只允许在⼀端插⼊在另⼀端删除所以只有最早进⼊的队列元素才可以从队列中删除故队列⼜称为先进先出线性表。基本逻辑图//队列只允许在一端进行插入操作另一端删除操作的线性表并且没有查找和修改操作 //队尾执行插入操作的一端 //队首执行删除操作的一端 //空队列不含任何数据元素的队列 //特征先进先出后进后出 //添加队首指针f和队尾指针r //采用顺序存储或链式存储 //入队 //出队 //判满 //判空 fr1 //初始化 //为了防止假溢出现象采用取余法 //r(r1)%maxx #includestdio.h #includestdlib.h //单链表的结点结构 typedef struct Node { int data; struct Node* next; }QNode; //声明队列结构 typedef struct { QNode* f;//队首指针 QNode* r;//队尾指针 }Queue; Queue InitQueue() { Queue q; //声明一个头结点 QNode* h (QNode*)malloc(sizeof(QNode)); //if(hNULL) h-next NULL; q.f q.r h; return q; } void EnQueue(Queue* q, int k) { //带尾指针的尾插法 q-r后面插入新结点 QNode* s (QNode*)malloc(sizeof(QNode)); //if(sNULL) s-data k; s-next NULL; q-r-next s; //移动尾指针 指向新的尾结点 q-r s; } void DeQueue(Queue* q) { if (q-f-next NULL) { printf(队空,无法出队\n); } else { QNode* p q-f-next;//p指向首元结点 printf(%d\n, p-data); if (q-r p) { q-r q-f;//防止r成为野指针 } q-f-next p-next; free(p); p NULL; } } int main() { Queue q InitQueue(); EnQueue(q, 1); EnQueue(q, 2); EnQueue(q, 3); DeQueue(q); DeQueue(q); DeQueue(q); EnQueue(q, 7); DeQueue(q); return 0; }顺序存储#includestdio.h #includestdlib.h #define maxx 10 //循环队列 typedef struct { int* data;//数组 int f, r; }Queue; Queue InitQueue() { Queue q; q.data (int*)malloc(sizeof(int) * maxx); //if(q.dataNULL) q.f q.r 0; return q; } void EnQueue(Queue* q, int k) { if (q-f (q-r 1) % maxx) { printf(队满,无法入队\n); } else { q-data[q-r] k; q-r (q-r 1) % maxx; } } int IsEmpty(Queue* q) { if (q-r q-f) { return 1;//空 } return 0;//非空 } void DeQueue(Queue* q) { if (IsEmpty(q) 1) { printf(队空,无法出队\n); } else { printf(%d\n, q-data[q-f]); q-f (q-f 1) % maxx; } } int main() { Queue q InitQueue(); EnQueue(q, 1); EnQueue(q, 2); EnQueue(q, 3); DeQueue(q); DeQueue(q); return 0; }队列的应⽤解决主机与外部设备速度不匹配多⽤户引起的资源竞争问题