线性表之队列

• 队列是限制在两端进行插入操作和删除操作的线性表
• 允许进行存入操作的一端称为“队尾”允许进行删除操作的一端称为“队头”
• 当线性表中没有元素时，称为“空队”
• 特点 ：先进先出（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;}