数据结构有哪些类型和特点？

本文共计1168个文字，预计阅读时间需要5分钟。

各位老友，欢迎大家庭造访本博客！接下来，还是我们的知识迁移运用！奥，太空啊！……+能力！……+知识迁移的能力！……----+OJ_02：请仅使用两个栈实现先进先出的队列，并且支持知识迁移！

各位老友，欢迎大家造访本期博客！

接下来，还是我们的 “知识迁移” 运用！奥，太空啊！！

能力！！知识迁移的能力！！

----> OJ_02 :>

请仅使用两个栈实现先进先出的队列，并且支持队列的四种操作（push, pop, empty, destroy）

下面就让我们设计代码吧！

#inculde <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int capcity; int top; }ST; //初始化 void STInitial(ST* ps) { ps ->a = (STDataType*)malloc(sizeof(STDataType) * 4); if(ps ->a == NULL) { perror("malloc::fail"); return ; } ps ->capcity = 4; ps ->top = 0; } //销毁 void STDestroy() { assert(ps); STEmpty(ps); free(ps ->a); ps ->a = NULL; ps ->capcity = 0; ps ->top = 0; } //压栈 void STPush(ST* ps, STDataType x) { if(ps ->capcity == ps ->top) { STDataType* tamp = (STDataType)realloc(ps ->a, sizeof(STDataType) * ps ->capcity * 2); if(tamp == NULL) { perror("realloc::fail"); return ; } ps ->a = tamp; ps ->capcity *= 2; } ps ->a[ps ->top++] = x; } //出栈 void STPop(ST* ps, STDataType x) { assert(ps); STEmpty(ps); ps ->top--; } //栈内元素个数 STDataType STSize(ST* ps) { assert(ps); STEmpty(ps); return ps ->top; } //栈顶元素 STDataType STTop(ST* ps) { assert(ps); STEmpty(ps); return ps ->a[ps ->top - 1]; } //布尔判空 bool STEmpty(ST* ps) { assert(ps); return ps ->top == 0; } //用栈实现队列 //匿名结构体 typedef struct { ST stPush; ST stPop; }MYQueue; //创建栈式的队列 MYQueue* myQueueCreate() { MYQueue* tamp = (MYQueue*)malloc(sizeof(MYQueue)); if(tamp == NULL) { perror("malloc::fail"); return ; } STInitial(&tamp ->stPush); STInitial(&tamp ->stPop); return tamp; } //入队列 void myQueuePush(MYQueue* obj, int x) { STPush(&obj ->stPush, x); } //返回队列开头元素 int myQueuePeek(MYQueue* obj) { if(STEmpty(&obj ->stPop)) { //倒数据 while(!STEmpty(&obj ->stPush)) { STPush(&obj ->stPop, STTop(&obj ->stPush)); STPop(&obj ->stPush); } } return STTop(&obj ->stPop); } //出队列后移除并返回开头元素 int myQueuePop(MYQueue* obj) { int front = myQueuePeek(obj); STPop(&obj ->stPop); return front; } //布尔判空 bool myQueueEmpty(MYQueue* obj) { assert(obj); return STEmpty(&obj ->stPush) && STEmpty(&obj ->stPop); } //销毁 void myQueueDestroy(MYQueue* obj) { STDestroy(&obj ->stPush); STDestroy(&obj ->stPop); free(obj); }

为了方便各位老友的观感，更好体验代码逻辑的流畅感觉，现特此附上彩色图样：

以上代码是在 OJ 上实现的环节，感兴趣的老友，可以尝试进行运行一下！！

现针对以上的部分代码，进行解析 ::>

首先，我们明确一点，上述的栈区实现，用的是数组！！也就是说：

---> 模块一，易错点

请注意上方彩色方块位置有一个 *4 不可忽略！！这牵扯到前面C语言的学习了！！如果有老友，忽视了这一点儿，或者说，因为这一点儿，而在 OJ 上奔跑不了，那实在是说，还是 C 语言的基础知识不够扎实！！

现在对其解析 :>

*4 的缘故是，我们创建的栈区是一个数组栈，而我们存储的是整形( int )， 而一个整形是 4 个字节，因此，当我们存储一个元素的时候自然需要四个字节大小的空间 ！注意 :> 代码 “sizeof(STDataType) 是一个字节”

从而该栈区 a 是一个存放整形的数组栈 ！！那么，不可避免，需要我们考虑容量大小，显然本人设定成了 4，也就是说，该数组栈最多可以存放 4 个整形元素 ！！

以上就是，易错点 --->模块一 ！！可以说，这是同C语言的基础知识挂钩的！！

对于其他部分的模块，如果你有看不懂的，尤其是 “倒数据”的那个部分！！我建议老友可以看看上一期的 OJ

那里的讲解重点就是她！！

最后，我还是要多啰嗦一两句，我们一定要在实现的时候，想清楚，我们是在用栈的原理来实现队列的原理，而两者的原理刚好相反 ！！

至此，各位老友，我们的本期讲解已经完毕！！欢迎大家踊跃发言！！感谢阅读！