题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty)。
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
题目链接
用栈实现队列
思路分析
题目的意思是要用两个栈来模拟实现一个队列。仅可以用栈的基本功能实现队列的基本功能。所以需要创建两个栈。所以这两个栈st1,st2可用一个结构体包含。本质就是用两个后进先出的栈,来模拟一个先进先出的队列。
思路:
1.st2这个栈用来压栈,st1的作用:把st2的所有值压到st1中,然后经过st1出栈。这样就达到了队列先进先出的性质。
2.st2一直用来压栈。如果st1为空则将st2里面的值全都转移到st1,如果st1不为空,则继续出栈,知道st1为空为止。
代码实现
ypedef char stdatatype; typedef struct stack { stdatatype* a; int top; int capacity; }st; //初始化结构体 void stackinit(st* ps); //销毁结构体 void stackdestroy(st* ps); //压栈 void stackpush(st* ps, stdatatype x); //出栈 void stackpop(st* ps); //得到栈顶的值 stdatatype stacktop(st* ps); //判断栈是否为空 bool stackempty(st* ps); //得到栈的长度 int stacksize(st* ps); //初始化结构体 void stackinit(st* ps) { assert(ps); ps->a = null; ps->capacity = 0; ps->top = 0; } //销毁结构体 void stackdestroy(st* ps) { assert(ps); free(ps->a); ps->a = null; ps->capacity = 0; ps->top = 0; } //压栈 void stackpush(st* ps, stdatatype x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; stdatatype* new = (stdatatype*)realloc(ps->a, sizeof(stdatatype) * newcapacity); if (new == null) { printf("realloc failn"); exit(-1); } ps->a = new; ps->capacity = newcapacity; } ps->a[ps->top] = x; ps->top++; } void stackpop(st* ps) { assert(ps); assert(ps->top > 0); ps->top--; } stdatatype stacktop(st* ps) { assert(ps); assert(ps->top>0); return ps->a[ps->top-1]; } bool stackempty(st* ps) { assert(ps); return ps->top == 0; } //得到栈的长度 int stacksize(st* ps) { assert(ps); return ps->top; } //创建了两个栈 typedef struct { st st1; st st2; } myqueue; //对两个栈进行初始化。 myqueue* myqueuecreate() { myqueue* newqueue = (myqueue*)malloc(sizeof(myqueue)); assert(newqueue); stackinit(&newqueue->st1); stackinit(&newqueue->st2); return newqueue; } void myqueuepush(myqueue* obj, int x) { assert(obj); stackpush(&obj->st2, x); } int myqueuepop(myqueue* obj) { assert(obj); if(stackempty(&obj->st1)) { while(!stackempty(&obj->st2)) { stackpush(&obj->st1, stacktop(&obj->st2)); stackpop(&obj->st2); } } int top = 0; if(!stackempty(&obj->st1)) { top = stacktop(&obj->st1); stackpop(&obj->st1); } return top; } int myqueuepeek(myqueue* obj) { assert(obj); if(stackempty(&obj->st1)) { while(!stackempty(&obj->st2)) { stackpush(&obj->st1, stacktop(&obj->st2)); stackpop(&obj->st2); } } if(!stackempty(&obj->st1)) { return stacktop(&obj->st1); } return 0; } bool myqueueempty(myqueue* obj) { return stackempty(&obj->st1) && stackempty(&obj->st2); } void myqueuefree(myqueue* obj) { stackdestroy(&obj->st1); stackdestroy(&obj->st2); free(obj); }
到此这篇关于c语言用栈模拟实现队列问题详解的文章就介绍到这了,更多相关c语言 栈实现队列内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C语言用栈模拟实现队列问题详解,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1072590.html