数据结构-->用栈实现队列（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

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

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

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