队列和栈的模拟实现

张

张建站

2026/5/22 20:25:54

10分钟阅读

目录1.队列1.1队列的结构1.2队列的函数声明1.3队列的函数定义1.4函数调试2.栈2.1栈的结构2.2栈的函数声明2.3栈的函数定义2.4函数调试1.队列队列是一种先进先出的数据结构先进入队列的数据会先进行出队队列的底层逻辑使用链表进行实现我们对比一下数组和链表的结构数组在尾插的时间复杂度是O(1)头插的时间复杂度是O(N)链表头插的时间复杂度是O(1)尾插的时间复杂度是O(N)所以只需看是否能对两种结构进行优化使得两种插入的时间复杂度都是O(1)对于数组无法对头插进行优化但是链表可以通过建立头尾指针入队出队直接使用头尾指针进行操作即可所以最终使用链表作为队列的实现结构1.1队列的结构现在我们知道队列需要有头尾指针所以创建一个队列结构体其中包含两个指针分别指向队列的头尾再创建一个节点的结构体包含两个成员数据和下一个节点的指针对于队列的模拟实现依旧是创建三个文件分别进行编写1.2队列的函数声明因为队列只能在一端插入数据另一端删除数据所以使用的函数会少一点//初始化队列 void QueueInit(Queue* ps); //创建一个节点 QN* QueueNewNode(QueueDatatype x); //入队 void QueuePush(Queue* ps, QueueDatatype x); //出队 void QueuePop(Queue* ps); //队列是否为空 bool QueueEmpty(Queue* ps); //获取队尾元素 QueueDatatype QueueCatchBack(Queue* ps); //获取队头元素 QueueDatatype QueueCatchHead(Queue* ps); //获取队列元素个数 int QueueSize(Queue* ps); //销毁队列 void QueueDestroy(Queue* ps); //打印队列 void QueuePrint(Queue* ps);1.3队列的函数定义#includequeue.h void QueueInit(Queue* ps) { //初始化队列将队列的两个指针先置为NULL assert(ps); ps-head ps-tail NULL; } bool QueueEmpty(Queue* ps) { assert(ps); //判断队列是否为空 //如果头指针为空说明没有节点 //返回true代表为空返回false代表非空 return ps-headNULL; } QN* QueueNewNode(QueueDatatype x) { QN* newnode (QN*)malloc(sizeof(QN)); //创建一个新节点动态分配空间 if (newnode NULL) { //分配失败则报错 perror(malloc); return NULL; } //data赋值为x //将新节点的指向置为NULL newnode-data x; newnode-next NULL; return newnode; } void QueuePush(Queue* ps, QueueDatatype x) { assert(ps); //执行入队操作 QN* newnode QueueNewNode(x); if (QueueEmpty(ps)) { //如果队列为空 //将头尾指针均指向新节点 ps-head ps-tail newnode; return; } //如果队列中已经存在节点 //则更新尾指针以及尾节点的指向 ps-tail-next newnode; ps-tail newnode; } void QueuePop(Queue* ps) { assert(ps !QueueEmpty(ps)); //出队操作需要更新头指针指向它的下一个节点 QN* ret ps-head-next; //释放原头节点的空间更新头指针 free(ps-head); ps-head ret; } QueueDatatype QueueCatchBack(Queue* ps) { //判断队列不为空 assert(ps !QueueEmpty(ps)); //直接返回尾指针指向节点的数据 return ps-tail-data; } QueueDatatype QueueCatchHead(Queue* ps) { //判断队列不为空 assert(ps !QueueEmpty(ps)); //直接返回头指针指向节点的数据 return ps-head-data; } int QueueSize(Queue* ps) { assert(ps); int size 0; if (QueueEmpty(ps)) { return size; } QN* pcur ps-head; while (pcur) { //遍历队列获取链表长度 pcur pcur-next; size; } return size; } void QueueDestroy(Queue* ps) { assert(ps); if (QueueEmpty(ps)) { free(ps-head); ps-head ps-tail NULL; } QN* ret ps-head; while (ret) { ret ret-next; free(ps-head); ps-head ret; } //依次释放节点 //最后将头尾指针均置为空 ps-head NULL; ps-tail NULL; } void QueuePrint(Queue* ps) { assert(ps !QueueEmpty(ps)); QN* ret ps-head; //遍历队列并打印 while (ret) { printf(%d , ret-data); ret ret-next; } printf(\n); }1.4函数调试#define _CRT_SECURE_NO_WARNINGS 1 #includequeue.h void test() { QN queue; QueueInit(queue); QueuePush(queue, 1); QueuePush(queue, 2); QueuePush(queue, 3); QueuePush(queue, 4); printf(当前队列为); QueuePrint(queue); printf(队头元素是%d\n, QueueCatchHead(queue)); printf(队尾元素是%d\n, QueueCatchBack(queue)); QueuePop(queue); QueuePop(queue); printf(当前队列为); QueuePrint(queue); QueueDestroy(queue); } int main() { test(); return 0; }2.栈栈的底层逻辑使用数组进行实现因为出入栈均在一侧实现所以只要用到数组的队尾进行出入栈的操作即可2.1栈的结构栈的结构体中包含一个可以动态申请内存的数组一个表示栈顶位置的top一个空间大小space2.2栈的函数声明//对栈进行初始化 void StackInit(SN* stack); //入栈元素 void StackPush(SN* st, StackDataType x); //出栈元素 void StackPop(SN* st); //获取栈顶元素 StackDataType StackPopCatch(SN* st); //获取栈中元素个数 int StackSize(SN* st); //判断栈是否为空 bool StackEmpty(SN* st); //销毁栈 void DestroyStcak(SN* st); //输出栈 void PrintStack(SN* st);2.3栈的函数定义#includestack.h void StackInit(SN* stack) { //初始化栈 stack-arr (StackDataType*)malloc(2 * sizeof(StackDataType)); //初始先申请两个空间 if (stack-arr NULL) { perror(malloc); return; } //将栈顶置为0 //空间大小置为2 stack-top 0; stack-space 2; } bool StackEmpty(SN* st) { assert(st); //判断栈是否为空 //当top等于0时表示栈空 return st-top 0; } void StackPush(SN* st, StackDataType x) { assert(st); if (st-top st-space) { //如果栈顶到达空间上限时 //对数组进行扩容 StackDataType* p1 (StackDataType*)realloc(st-arr, 2 * (st-space) * sizeof(StackDataTpye)); if (p1 NULL) { perror(realloc); return; } st-arr p1; st-space * 2;//进行二倍扩容 } //进行入栈操作top st-arr[st-top] x; st-top; } void StackPop(SN* st) { assert(!StackEmpty(st));//栈不可为空 //直接top--即可表示出栈 st-top--; } StackDataType StackPopCatch(SN* st) { assert(!StackEmpty(st)); //直接返回栈顶元素 //top-1表示栈顶的下标 return st-arr[st-top - 1]; } int StackSize(SN* st) { assert(st); //top就是栈中的元素个数 return st-top; } void DestroyStcak(SN* st) { assert(st); //直接释放数组 //将其他成员置为0和NULL free(st-arr); st-arr NULL; st-top 0; st-space 0; } void PrintStack(SN* st) { //遍历栈进行打印 assert(st); for (int i 0; i st-top; i) { printf(%d ,st-arr[i]); } printf(\n); }2.4函数调试#define _CRT_SECURE_NO_WARNINGS 1 #includestack.h void test() { SN stack; StackInit(stack); StackPush(stack, 1); StackPush(stack, 2); StackPush(stack, 3); StackPush(stack, 4); printf(当前栈内元素为); PrintStack(stack); printf(当前元素个数为%d\n, StackSize(stack)); printf(当前栈顶元素为%d\n, StackPopCatch(stack)); StackPop(stack); printf(出栈一次当前栈顶元素为%d\n, StackPopCatch(stack)); StackPop(stack); printf(出栈两次当前栈顶元素为%d\n, StackPopCatch(stack)); DestroyStcak(stack); } int main() { test(); return 0; }