数据结构：队列和栈的相互实现

文章目录前言一、队列实现栈1.2 代码的实现1.2.1结构体的构建1.2.2 初始化1.2.3 模型入栈1.2.4 模拟出栈并返回栈顶元素1.2.5 获取栈顶元素1.2.6 判空1.2.7 释放二 栈实现队列2.1 思路分析2.2 代码实现2.2.1 结构体的构建2.2.2 初始化2.2.3 将元素 x 推到队列的末尾(模拟入队)2.2.4 返回队列开头的元素2.2.5 从队列的开头移除并返回元素(模拟出队)2.2.6 判空2.2.7 销毁前言虽然在实践中没有什么意义但是可以帮助我们熟悉和了解栈和队列一、队列实现栈思路如下图所示队列的规则是先进先出而栈的规则是后进先出如图中q1我们入队1、2、3、4按照栈我们出栈的是4因此我们将q1中的红色框中的数据导给q2然后剩下44直接出队就达到了效果。当我们出完4后当我们想入数据是给q1还是q2呢q2假设我们入给q1如下图所示然后我们需要6出队该怎么出呢是不是想将5导入到q2再出6那如果我再出5你是不是要让q2的1、2、3、4导给q1然后出5。如果再进行push呢又给q2吗这样会一直导来导去逻辑会混乱。那栈顶的数据我们就不知道是在q1还是在q2。因此我们需要向非空的队列中去push数据。1.2 代码的实现首先需要了解队列的实现#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintQDataTpye;typedefstructQueueNode{QDataTpye val;structQueueNode*next;}QueueNode;typedefstructQueue{QueueNode*ptail;QueueNode*phead;intsize;}Queue;//初始化voidQueueInit(Queue*pq);//队尾插入voidQueuePush(Queue*pq,QDataTpye x);//队头删除voidQueuePop(Queue*pq);//取队头队尾的数据QDataTpyeQueueFront(Queue*pq);QDataTpyeQueueBack(Queue*pq);//个数intQueueSize(Queue*pq);//判空boolQueueEmpty(Queue*pq);//销毁voidQueueDestory(Queue*pq);voidQueueInit(Queue*pq){assert(pq);pq-pheadpq-ptailNULL;pq-size0;}voidQueuePush(Queue*pq,QDataTpye x){assert(pq);QueueNode*newnode(QueueNode*)malloc(sizeof(QueueNode));if(newnodeNULL){perror(QueuePush::malloc);return;}newnode-nextNULL;newnode-valx;//空的if(pq-pheadNULL){pq-pheadpq-ptailnewnode;}else//尾插{pq-ptail-nextnewnode;pq-ptailnewnode;}pq-size;}intQueueSize(Queue*pq){assert(pq);returnpq-size;}voidQueuePop(Queue*pq){assert(pq);assert(pq-size!0);//一个节点if(pq-phead-nextNULL){free(pq-phead);pq-pheadpq-ptailNULL;}else{QueueNode*nextpq-phead-next;free(pq-phead);pq-pheadnext;}pq-size--;}QDataTpyeQueueFront(Queue*pq){assert(pq);assert(pq-phead);returnpq-phead-val;}QDataTpyeQueueBack(Queue*pq){assert(pq);assert(pq-ptail);returnpq-ptail-val;}boolQueueEmpty(Queue*pq){assert(pq);returnpq-size0;}voidQueueDestory(Queue*pq){assert(pq);QueueNode*curNULL;curpq-phead;while(cur){QueueNode*temcur-next;free(cur);curtem;}pq-pheadpq-ptailNULL;pq-size0;在实现队列的基础上再来用两个队列实现栈1.2.1结构体的构建首先我们需要封装一个结构体来管理这两个队列typedefstructMyStack{Queue q1;Queue q2;}MyStack;1.2.2 初始化对结构体进行初始化MyStack*MyStackCreat(){MyStack*pst(MyStack*)malloc(sizeof(MyStack));if(pstNULL){perror(MyStackCreat::malloc);exit(1);}QueueInit((pst-q1));QueueInit((pst-q2));returnpst;}1.2.3 模型入栈谁不为空就入给谁都为空随便入voidmyStackPush(MyStack*obj,QDataTpye x){if(!QueueEmpty((obj-q1))){QueuePush((obj-q1),x);}else{QueuePush((obj-q2),x);}}1.2.4 模拟出栈并返回栈顶元素intmyStackPop(MyStack*obj){//假设法MyStack*Empty(obj-q1);MyStack*nonEmpty(obj-q2);if((obj-q2)NULL){nonEmpty(obj-q1);Empty(obj-q2);}//不为空前size-1导走删除最后一个就是栈顶数据while(QueueSize(nonEmpty)1){QueuePush(Empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}inttopQueueFront(nonEmpty);QueuePop(nonEmpty);returntop;}1.2.5 获取栈顶元素找到不为空的队列返回队尾元素就是栈顶元素intmyStackTop(MyStack*obj){if(!QueueEmpty((obj-q1))){returnQueueBack(((obj-q1)));}else{returnQueueBack(((obj-q2)));}}1.2.6 判空也就是判断两个队列是否为空boolmyStckEmpty(MyStack*obj){returnQueueEmpty((obj-q2))QueueEmpty((obj-q1));}1.2.7 释放直接释放obj没有当我们直接释放掉obj时除了释放掉了obj后面的都没有释放掉会造成内存泄漏voidmyStackFree(MyStack*obj){QueueDestory((obj-q1));QueueDestory((obj-q2));free(obj);}这里obj置不置空都行它是一级指针只起到传值的作用改变不了实参。二 栈实现队列2.1 思路分析首先我们需要明白栈是后进先出而队列是先进先出。和上面队列实现栈一样我们将一个不为空的栈导到另外一个栈去然后出栈是不是就达到效果了。此时第一个栈就变成空如果我们再想入栈数据该怎么办呢是向非空的栈入数据的话我们就需要保持之前的顺序需要将第二个栈的数据导到第一个栈然后入栈数据然后再将这个数据导入到第二个栈中出栈这也是可以的但是很麻烦。因此我们只需要将一个栈作为入栈另一个栈出栈就好了比如之前导好后的数据我们需要再入栈就向最开始导的栈中入然后等另外一个栈所有的数据完成出栈后再将数据导入进去。2.2 代码实现首先我们需要在实现栈的基础上完成。typedefintSTDataType;typedefstruct{STDataType*arr;//指向栈数组空间的指针inttop;//栈顶位置intcapacity;//容量}Stack;//栈的初始化voidStackInit(Stack*s);//栈的销毁voidStackDestory(Stack*s);//核心逻辑//x元素入栈voidStackPush(Stack*s,STDataType x);//将栈顶元素出栈并返回栈顶元素STDataTypeStackPop(Stack*s);//获取栈顶元素并返回STDataTypeStackTop(Stack*s);//获取栈中有效元素个数intStackSize(Stack*s);//检测栈是否为空如果是空返回真否则返回假boolStackEmpty(Stack*s);voidStackInit(Stack*s){assert(s);s-arr(STDataType*)malloc(4*sizeof(STDataType));//开辟四个元素的空间if(s-arrNULL){perror(StackInit::malloc);return;}// 初始化时top 0表⽰top指向的是栈顶元素的下⼀个位置// 初始化时top -1表⽰top指向的是栈顶元素s-top0;s-capacity0;}voidStackPush(Stack*s,STDataType x){assert(s);//空间扩容if(s-capacitys-top){intnewcapacitys-capacity0?4:2*s-capacity;STDataType*tem(STDataType*)realloc(s-arr,sizeof(STDataType)*newcapacity);if(temNULL){perror(tem::realloc);exit(1);}s-arrtem;s-capacitynewcapacity;}//入栈s-arr[s-top]x;}STDataTypeStackPop(Stack*s){assert(s);//判断是否为空如为空就没有出栈的必要if(!StackEmpty(s))returns-arr[--s-top];}STDataTypeStackTop(Stack*s){assert(s);if(!StackEmpty(s))returns-arr[s-top-1];//top0,指向的是栈顶下一个位置}intStackSize(Stack*s){assert(s);returns-top;}boolStackEmpty(Stack*s){assert(s);returns-top0;}voidStackDestory(Stack*s){assert(s);if(s-arr){free(s-arr);s-arrNULL;s-top0;s-capacity0;}}2.2.1 结构体的构建在栈的结构上构建两个栈一个栈作为入栈一个栈作为出栈typedefstructSTQ{Stack s1;//栈1入栈Stack s2;//栈2出栈}MyQueue;2.2.2 初始化MyQueue*myQueueCreate(){MyQueue*obj(MyQueue*)malloc(sizeof(MyQueue));if(objNULL){perror(myQueueCreate::malloc);exit(1);}StackInit((obj-s1));StackInit((obj-s2));returnobj;}2.2.3 将元素 x 推到队列的末尾(模拟入队)voidmyQueuePush(MyQueue*obj,intx){assert(obj);StackPush((obj-s1),x);}2.2.4 返回队列开头的元素我们先确定s2是否为空为空我们需要将s1的数据导入s2中然后去s2的栈顶元素即可intmyQueuePeek(MyQueue*obj){assert(obj);if(StackEmpty((obj-s2))){//导数据while(!StackEmpty((obj-s1))){inttopStackTop((obj-s1));StackPush((obj-s2),top);StackPop((obj-s1));}}returnStackTop((obj-s2));}2.2.5 从队列的开头移除并返回元素(模拟出队)这个和上面的2.2.4差不多都需要导入数据但是导入数据后只需要pop就可以了。intmyQueuePop(MyQueue*obj){assert(obj);inttopmyQueuePeek((obj-s2));StackPop((obj-s2));returntop;}2.2.6 判空boolmyQueueEmpty(MyQueue*obj){assert(obj);returnStackEmpty((obj-s1))StackEmpty((obj-s1));}2.2.7 销毁voidmyQueueFree(MyQueue*obj){StackDestory(obj-s1);StackDestory(obj-s2);free(obj);}