链队:采用链表来存储队列
链队类型的使用
#include<stdio.h> #include<stdlib.h> #define maxsize 100 typedef struct QNode { int data; struct QNode *next; }QNode; typedef struct { QNode *front; QNode *rear; }Liqueue;
初始化链队
void initQueue(Liqueue *&lqu) { lqu=(Liqueue*)malloc(sizeof(Liqueue)); lqu->front=lqu->rear=NULL; }
判断队空
int isQueueEmpty(Liqueue *lqu) { if(lqu->rear==NULL||lqu->front==NULL) return 1; else return 0; }
入队算法
void enQueue(Liqueue *lqu,int x) { QNode *p; p=(QNode*)malloc(sizeof(QNode)); p->data=x; p->next=NULL; if(lqu->rear==NULL)//若队列空,新结点是队首结点,也是队尾结点 lqu->front=lqu->rear=p; else { lqu->rear->next=p; lqu->rear=p;//新结点链接到队尾,p指向它 } }
出队算法
int deQueue(Liqueue *lqu,int &x) { QNode *p; if(lqu->rear==NULL)//队空不能出队 return 0; else p=lqu->front; if(lqu->front==lqu->rear)//队列只有一个结点的处理 lqu->front=lqu->rear=NULL; else lqu->front=lqu->front->next; x=p->data; free(p); return 1; }
虽然链队特点不存在队列满上溢
这里有个bug就是队列满的时候还继续入队,内存满