队列及笔试题

队列

先进先出

使用单链表进行队尾插入队头删除

其中带头结点直接尾插，不带头结点第一次操作要判断一下

但是带头结点需要malloc和free

函数传需要修改的参数方法

1、二级指针

2、带哨兵位的头结点

3、返回值

4、如果有多个值，用结构体封装起来

可以把头指针和尾指针放到结构体里面，就不用二级指针了。

他们是结构体成员，想要改变就可以用结构体指针

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDataType;typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;void QInit(Queue* pq);
void QDestroy(Queue* pq);
void QPush(Queue* pq, QDataType x);
void QPop(Queue* pq);//取队头的数据
QDataType QFront(Queue* pq);//取队尾的数据
QDataType QBack(Queue* pq);//判断链表是否为空
bool QEmpty(Queue* pq);//求队长度
int QSize(Queue* pq);

Queue.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Queue.h"void QInit(Queue* pq) {assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QDestroy(Queue* pq) {assert(pq);QNode* cur = pq->phead;while (cur) {pq->phead = pq->phead->next;free(cur);cur = pq->phead;pq->size --;}pq->ptail = NULL;
}void QPush(Queue* pq, QDataType x) {assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc");return;}newnode->next = NULL;newnode->val = x;if (pq->phead == NULL) {pq->phead = newnode;pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}void QPop(Queue* pq) {assert(pq);assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL) {pq->ptail = NULL;}pq->size--;
}//取队头的数据
QDataType QFront(Queue* pq) {assert(pq);assert(pq->phead);return pq->phead->val;
}//取队尾的数据
QDataType QBack(Queue* pq) {assert(pq);assert(pq->phead);return pq->ptail->val;
}//判断链表是否为空
bool QEmpty(Queue* pq) {assert(pq);return pq->phead == NULL;
}//求队长度
int QSize(Queue* pq) {assert(pq);return pq->size;
}

Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include"Queue.h"int main() {Queue q;QInit(&q);QPush(&q, 1);QPush(&q, 2);QPush(&q, 3);QPush(&q, 4);QPush(&q, 5);int size = QSize(&q);printf("%d\n", size);while (!QEmpty(&q)) {printf("%d ", QFront(&q));QPop(&q);}printf("\n");size = QSize(&q);printf("%d\n", size);QDestroy(&q);
}