- 队列是限制在两端进行插入操作和删除操作的线性表
- 允许进行存入操作的一端称为“队尾”允许进行删除操作的一端称为“队头”
- 当线性表中没有元素时，称为“空队”
- 特点 ：先进先出（FIFO）或后进后出
- 普通队列的缺点：
- 出队后前面的空间无法重用，会造成“假溢出”
- 当 sq->front > 0 且 sq->rear == N 时，虽然数组前面有空位，但队列已满
- 在实际应用中，循环队列是更高效的选择，因为它避免了元素的移动，空间利用率更高。
- 普通队列的主要缺点是空间浪费或需要移动元素的开销
- 功能实现
#include<stdio.h>#include<stdlib.h>#include<string.h>sequeue*queue_create(){sequeue*sq;if((sq=(sequeue*)malloc(sizeof(sequeue)))==NULL){printf("malloc failed\n");returnNULL;}memset(sq->data,0,sizeof(sq->data));sq->front=sq->rear=0;returnsq;}intenqueue(sequeue*sq,datatype x){if(sq==NULL){printf("sq is NULL\n");return-1;}if(sq->rear==N){printf("sequeue is full\n");return-1;}sq->data[sq->rear]=x;sq->rear++;return0;}datatypedequeue(sequeue*sq){datatype ret;if(sq==NULL||sq->front==sq->rear){printf("queue is empty or NULL\n");return(datatype)-1;}ret=sq->data[sq->front];sq->front++;// 可选:当队列为空时，重置指针以重用空间if(sq->front==sq->rear){sq->front=sq->rear=0;}returnret;}intqueue_empty(sequeue*sq){if(sq==NULL){printf("sq is NULL\n");return-1;}return(sq->front==sq->rear?1:0);}intqueue_full(sequeue*sq){if(sq==NULL){printf("sq is NULL\n");return-1;}return(sq->rear==N?1:0);}intqueue_clear(sequeue*sq){if(sq==NULL){printf("sq is NULL\n");return-1;}sq->front=sq->rear=0;return0;}sequeue*queue_free(sequeue*sq){if(sq==NULL){printf("sq is NULL\n");returnNULL;}free(sq);returnNULL;}intqueue_length(sequeue*sq){if(sq==NULL){return-1;}returnsq->rear-sq->front;}- 头文件
#defineN100// 队列最大容量typedefintdatatype;// 数据类型typedefstruct{datatype data[N];// 存储队列元素intfront;// 队头指针intrear;// 队尾指针}sequeue;sequeue*queue_create();intenqueue(sequeue*sq,datatype x);datatypedequeue(sequeue*sq);intqueue_empty(sequeue*sq);intqueue_full(sequeue*sq);intqueue_clear(sequeue*sq);sequeue*queue_free(sequeue*sq);intqueue_length(sequeue*sq);- 测试文件
#include<stdio.h>#include"sequeue.h"intmain(intargc,constchar*argv[]){sequeue*sq;if((sq=queue_create())==NULL){return-1;}enqueue(sq,10);enqueue(sq,100);enqueue(sq,1000);while(!queue_empty(sq)){printf("dequeue:%d\n",dequeue(sq));}queue_free(sq);return0;}
)