用栈模拟实现队列(c语言版)

2023-06-15 23:43| 来源: 网络整理| 查看: 265

在这里插入图片描述

前言

用"栈实现队列",力扣中一道oj题,可以帮助刚接触"栈"和"队列"的新手更好的理解栈和队列这两种结构.

题目来源于力扣: 题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/ 难度:简单

目录前言一、队列的各接口:1.1 类型的声明(MyQueue):1.2 初始化(myQueueCreate):1.3 入队列(myQueuePush)1.4 出队列(myQueuePop)1.5 队列的判空(myQueueEmpty)1.6 返回队首元素(myQueuePeek):1.7 队列的销毁(myQueueFree): 二、总代码:

一、队列的各接口: 1.1 类型的声明(MyQueue): //模拟队列类型的声明 typedef struct { ST stackpush; //用于模拟队列的入队操作 ST stackpop; //用于模拟队列的出队操作 } MyQueue;

这里是借助两个栈用于模拟队列. ①:stackpush 模拟队列的入队 ②:stackpop 模拟队列的出队

在这里插入图片描述

1.2 初始化(myQueueCreate):

该队列是由两个栈实现的,所以重点关注两个栈的初始化即可.

步骤:

申请两个栈大小的空间. 申请失败时判断一下.对队列中的两个栈,一次调用他们的初始化函数.(这个千万别漏掉了,牛牛漏掉之后找了好久的问题) //队列的初始化 MyQueue* myQueueCreate() { //给队列开辟空间 MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("obj malloc fail"); } //一定要记得这里要初始化(别漏掉了哦) InitST(&obj->stackpush); InitST(&obj->stackpop); return obj; } 1.3 入队列(myQueuePush)

对于入队列的模拟实现很简单,只需要将数据压入栈(模拟入队列:stackpush)即可.

void myQueuePush(MyQueue* obj, int x) { assert(obj); STPush(&obj->stackpush,x); } 1.4 出队列(myQueuePop)

函数要求: 将队首元素出队,并且返回刚刚出队的队首元素.

模拟出队相对复杂一些.

初始状态下或者stackpop(模拟出队的栈)数据出队列到空时,里面是没有数据的,所以先判断stackpop是否有数据. 有数据:则直接获取stackpop的栈顶元素作为队首元素. 无数据:将数据从模拟入队列栈全部倒过来.(倒数据)获取stackpop的栈顶元素作为队首元素,使用top变量记录下来.(因为后面要执行出栈操作).出栈(模拟出队列),并返回top变量. int myQueuePop(MyQueue* obj) { assert(obj); if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列的栈)为空,则向栈(stackpush模拟入队列的栈)要数据 { //下面循环结束的条件是不为空 while(!STEmpty(&obj->stackpush))//将数据从模拟入队列栈全部倒过来 { //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈) STPush(&obj->stackpop,STTop(&obj->stackpush)); STPop(&obj->stackpush); } } int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素; STPop(&obj->stackpop); return top; } 1.5 队列的判空(myQueueEmpty)

当两个栈中都没有元素时,则队列为空.

//写法1

bool myQueueEmpty(MyQueue* obj) { if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈 { return true; } else return false; }

//写法2.

bool myQueueEmpty(MyQueue* obj) { return STEmpty(&obj->stackpush) && STEmpty(&obj->stackpop); } 1.6 返回队首元素(myQueuePeek): stackpop不为空时,则队首元素就是stackpop的栈顶元素.stackpop为空时,则队首元素就是stackpush的栈底元素. 所以这里也需要倒数据. int myQueuePeek(MyQueue* obj) { assert(obj); if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列)为空,则向栈(stackpush模拟入队列)要数据 { while(!STEmpty(&obj->stackpush)) { //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出队列) STPush(&obj->stackpop,STTop(&obj->stackpush)); STPop(&obj->stackpush); } } int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素; return top; }

与myQueuePop(出队列)函数比较,此函数只是将队首元素返回,并没有指向pop出队操作. 所以我们在实现myQueuePop函数时可以复用一下myQueuePeek函数.

int myQueuePop(MyQueue* obj) { int top=myQueuePeek(obj); STPop(&obj->stackpop); return top; } 1.7 队列的销毁(myQueueFree): 释放两个栈初始化开辟的空间释放队列申请的空间. void myQueueFree(MyQueue* obj) { STDestory(&obj->stackpush); STDestory(&obj->stackpop); free(obj); } 二、总代码:

前面的代码是栈的实现,由于c语言不能像c++那样直接调用库.

typedef int stacktype; typedef struct stack//定义栈的类型 { stacktype* data; int top; int capacaity; }ST; void InitST(ST* ps);//初始化栈 void STPush(ST* ps, stacktype x);//压栈 void STPop(ST* ps);//出栈 bool STEmpty(ST* ps);//判断是否为空栈 stacktype STTop(ST* ps);//返回栈顶元素 void STDestory(ST* ps);//栈的销毁 void InitST(ST* ps)//初始化栈 { assert(ps); ps->top = -1; ps->capacaity = 4; ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype)); } void STPush(ST* ps, stacktype x)//压栈 { assert(ps); if (ps->top+1 == ps->capacaity) { ps->capacaity *= 2; ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype)); if(tmp == NULL) { printf("增容失败\n"); } ps->data = tmp; } ps->top++; ps->data[ps->top] = x; } void STPop(ST* ps)//出栈 { assert(ps); assert(!STEmpty(ps)); ps->top--; } bool STEmpty(ST* ps)//判断是否为空栈,是空返回真 { assert(ps); if (ps->top == -1) { return true; } return false; } stacktype STTop(ST* ps)//返回栈顶元素 { assert(ps); return ps->data[ps->top]; } void STDestory(ST* ps)//销毁栈 { assert(ps); free(ps->data); ps->data = NULL; ps->top = -1; ps->capacaity = 0; } //模拟队列类型的声明 typedef struct { ST stackpush; ST stackpop; } MyQueue; //队列的初始化 MyQueue* myQueueCreate() { MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue)); if(obj==NULL) { perror("obj malloc fail"); } //一定要记得这里要初始化 InitST(&obj->stackpush); InitST(&obj->stackpop); return obj; } void myQueuePush(MyQueue* obj, int x) { assert(obj); STPush(&obj->stackpush,x); } int myQueuePop(MyQueue* obj) { assert(obj); if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据 { while(!STEmpty(&obj->stackpush)) { //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈) STPush(&obj->stackpop,STTop(&obj->stackpush)); STPop(&obj->stackpush); } } int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素; STPop(&obj->stackpop); return top; } bool myQueueEmpty(MyQueue* obj) { if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈 { return true; } else return false; //return STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop); } int myQueuePeek(MyQueue* obj) { if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据 { while(!STEmpty(&obj->stackpush)) { //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈) STPush(&obj->stackpop,STTop(&obj->stackpush)); STPop(&obj->stackpush); } } int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素; return top; //return STTop(&obj->stackpop); } void myQueueFree(MyQueue* obj) { STDestory(&obj->stackpush); STDestory(&obj->stackpop); free(obj); }

运行结果: 在这里插入图片描述

【本文地址】

公司简介

联系我们