一.循环队列
1.构建结构
//定义队列的结构
typedef struct{
//队头
int front;
//队尾
int real;
//队空间(静态空间)
SElemType data[MAXSIZE];
} SqQueue;
2.初始化队列
//初始化队列
Status InitQueue(SqQueue *queue){
queue->front = queue->real = 0;
return OK;
}
3.清空队列
//清空队列
Status ClearQueue(SqQueue *queue){
if (!queue) {
return ERROR;
}
queue->front = 0;
queue->real = 0;
return OK;
}
4.判断是否为空队列
//判断队列是否为空
Status EmptyQueue(SqQueue queue){
if (queue.front == queue.real) {
return TRUE;
}
return FALSE;
}
5.获取队列的长度
//获得队列的长度
int GetQueueLength(SqQueue queue){
return (queue.real - queue.front + MAXSIZE)%MAXSIZE;
}
6.便利队列
//遍历队列
Status TraversalQueue(SqQueue queue){
printf("队列内容是:\n");
//从队头开始遍历
int i = queue.front;
//因为是循环队列,所以从队头开始查到队尾结束,%MAXSIZE是为了取具体位置
while ((i + queue.front)%MAXSIZE != queue.real) {
printf("%d\n",queue.data[i]);
i = (i+1)%MAXSIZE;
}
return OK;
}
7.入队
//入队
Status PushQueue(SqQueue *queue, SElemType data){
if ((queue->real + 1)%MAXSIZE == queue->front) {//队满了
return ERROR;
}
queue->data[queue->real] = data;
//以为你是循环队列,所以real不能一直++,估要+1后%MAXSIZE
queue->real = (queue->real + 1)%MAXSIZE;
return OK;
}
8.出队
//出队
Status PopQueue(SqQueue *queue, SElemType *data){
if (queue->front == queue->real) {//空队列
return ERROR;
}
*data = queue->data[queue->front];
printf("出队的是:%d\n",*data);
queue->front = (queue->front + 1)%MAXSIZE;
return OK;
}
二.链式队列
无需关心队列是否满了
内存空间不连续
链式需要关心节点的释放
1.节点结构
//构造队列结点
typedef struct QNode {
SElemType data;
struct QNode *next;
}QNode,*QListNode;
//构造队列
typedef struct{
QListNode front;
QListNode real;
//用来记录队列的长度
int count;
} SQueue;
2.初始化链式队列
//初始化链式队列
Status InitNodeQueue(SQueue *queue){
queue->front = queue->real = (QListNode)malloc(sizeof(QNode));
if (!queue->front) {
return ERROR;
}
//队头指向Null
queue->front->next = NULL;
queue->count = 0;
return OK;
}
3.判断是否为空的链式队列
//是否是空的链式队列
Status EmptyNodeQueue(SQueue queue){
if (queue.front == queue.real) {
return TRUE;
}
return FALSE;
}
4.清空队列
//将链式队列清空
Status ClearNodeQueue(SQueue *queue){
if (queue->front == queue->real) {//如果是空队列
printf("空队列\n");
return ERROR;
}
queue->real = queue->front;
queue->count = 0;
QListNode p = queue->front->next,temp;
queue->front->next = NULL;
while (p) {
temp = p;
free(p);
p = temp->next;
} return OK;
}
5.链式队列的长度
//获得链式队列的长度
int GetNodeQueueLenght(SQueue queue){
/*
//方法一
if (queue.front == queue.real) {//空队列
return 0;
}
int i = 1;
QListNode p = queue.front->next;
while (p) {
p = p->next;
if (p) {
i++;
}
}
return i;
*/
//方法二:
return queue.count;
}
6.便利链式队列
//遍历链式队列
Status TraversalNodeQueue(SQueue queue){
if (queue.front == queue.real) {
printf("空队列\n");
return ERROR;
}
printf("队列内容:");
QListNode p = queue.front->next;
while (p) {
printf("%4d",p->data);
p = p->next;
}
printf("\n");
return OK;
}
7.链式队列入队
//入队
Status PushNodeQueue(SQueue *queue, SElemType data){
//链式队列无需判断队满
QListNode temp = (QListNode)malloc(sizeof(QNode));
temp->data = data;
temp->next = NULL;
//修改队尾指向的结点
queue->real->next = temp;
//更新队尾
queue->real = temp;
//队的长度自增1
queue->count++;
return OK;
}
8.链式队列出队
//出队
Status PopNodeQueue(SQueue *queue, SElemType *data){
if (queue->front == queue->real) {
printf("空队列\n");
return ERROR;
}
//获得队头结点
QListNode temp = queue->front->next;
*data = temp->data;
//更新队头指向的结点
queue->front->next = temp->next;
free(temp);
return OK;
}
网友评论