队列操作实现:循环队列和链队列的初始化、求长度、出队、入队、去队头元素等操作。
1. 循环队列
这里通过浪费一个空间来区别队满和队空。
❗注意:rear和front的指针循环加操作、队满的判断、队空的判断,求队长。(因为是循环队列,循环,所以这些操作和平时的操作不一样,需要多注意一些)。
//循环队列
#include<stdio.h>
#include<stdlib.h>#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define MAXSIZE 100typedef int ElemType;
typedef int Status;
typedef struct{ElemType *base; //存储空间的基地址int front,rear; //头指针、尾指针
}SqQueue; //1. 初始化循环队列
Status InitQueue(SqQueue &Q){Q.base=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE); //分配MAXSIZE空间
// Q.base=new ElemType[MAXSIZE];if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; //初始化队头队尾指针指向0return OK;
}//2.求循环队列的长度
//如果Q.rear>Q.front ,length=Q.rear-Q.front;
//如果Q.rear<Q.front, length=MAXSIZE-Q.front+Q.rear
int QueueLength(SqQueue Q){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}//3.入队
Status EnQueue(SqQueue &Q,ElemType e){if((Q.rear+1)%MAXSIZE==Q.front) //牺牲一个存储空间判断(和队空判断区分开来) return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;
} //4.出队
Status DeQueue(SqQueue &Q,ElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;return OK;
} //5.取队头元素
Status GetHead(SqQueue Q,ElemType &e){if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];return OK;
}
2. 链队列(带头节点)
出队的时候需要注意一下当链队列中只有一个元素的情况,需要将rear指针同样指向front.
//链队列(带头结点)
#include<stdio.h>
#include<stdlib.h>#define OK 1
#define OVERFLOW -2
#define ERROR 0typedef int ElemType;
typedef int Status;
//定义一个链表
typedef struct QNode{ElemType data;struct QNode *next;
}QNode,*QueuePtr;//定义两个指针
typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针
}LinkQueue;//1.初始化
Status InitQueue(LinkQueue &Q){Q.front=Q.rear=(QNode*)malloc(sizeof(QNode));
// Q.front=Q.rear=new QNode;Q.front->next=NULL;
// Q.rear->next=NULL; //为什么不需要这步:因为在每次入队的时候都设计了rear->next=NULL return OK;
}//2. 入队
Status EnQueue(LinkQueue &Q,ElemType e){QueuePtr p=(QNode*)malloc(sizeof(QNode));p->data=e;Q.rear->next=p;p->next=NULL;Q.rear=p;return OK;
} //3.出队(抛弃一个空间用于判断是否为空)
Status DeQueue(LinkQueue &Q,ElemType &e){if(Q.front==Q.rear)return ERROR; QueuePtr p=Q.front->next; //要出队的位置 e=p->data;Q.front->next=p->next;
// if(Q.front->next==NULL) //使用这个条件判断也可,但是书上不是以这种方式,所以建议使用下面的代码 if(Q.rear==p) //最后一个元素被删 Q.rear=Q.front;free(p);return OK;
} //5.取队头元素
Status GetHead(LinkQueue Q,ElemType &e){if(Q.rear==Q.front) //队列为空 return ERROR;e=Q.front->next->data;return OK;
}