🎁个人主页：我们的五年
🔍系列专栏：初阶数据结构刷题
🎉欢迎大家点赞👍评论📝收藏⭐文章
🚗 1.问题描述：
题目中说了只能使用两个栈实现队列，并且只能使用基本的栈操作。比如：在栈顶进行入栈操作，在栈顶进行出栈，取栈顶元素，还有判空这些基本的栈操作函数。然后使用这些函数实现队列的基本操作，队列的特点就是在队尾插入数据，在队头删除数据，在对头取数据。
题中说使用两个栈实现，也给了我们提示。
🚗 2.问题分析：
假如先在一个栈中插入三元素1.2.3。
当使用StackPush函数在PushST进行三次插入以后，就变成了上面的情形，但是如果我们要进行队列取队头的数据，进行队列删除队头的数据，我们就要先把上面的3和2拿走。从而我们就想到了把左边栈里面的元素的放到右边去。
进行上面的操作以后，我们就调用栈的取栈顶的函数就可以拿到元素1，也可以进行取删除元素1，就可以达到和队列一样的性质：先进先出。
插入数据的时候，我们还是在PushST中插入数据，加入先插入4，5.
如果要进行删除操作，取元素操作也是可以直接在PopST栈中直接取。也是满足队列的要求的。但是当我们把PopST的元素都取完以后，我们就要再一次把PushST栈里面的元素导到PopST栈里面。
按照上面的步骤就可以实现队列的操作。
🚗 3.代码层面进行解析：
栈的函数接口
先给出栈的接口：
typedef int SLDataType;
typedef struct Stack{
SLDataType* a;
int top;
int capacity;
}Stack;
//对栈进行初始化
void StackInit(Stack* ptr);
//对栈进行销毁
void StackDestroy(Stack* ptr);
//在栈顶插入元素
void StackPush(Stack* ptr, SLDataType x);
//获取栈顶元素
SLDataType StackTop(Stack* ptr);
//对栈进行判断，如果为空，返回true，否则返回false
bool StackEmpty(Stack* ptr);
//销毁栈的栈顶元素
void StackPop(Stack* ptr);
用栈的函数实现队列
先定义我自己结构体的类型：
根据上面分析也是用两个栈实现队列，也就是说我的队列类型中保护了两个栈，并且我把这两个队列命名为PushST和PopST
typedef struct {
Stack PushST; //把元素新的元素放在这个栈，也就是在这个栈里面实现插入操作
Stack PopST; //在这个栈中取数据，删除数据
} MyQueue;创建队列，在堆区上申请一块空间，并且对队列里面的栈进行初始化
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->PushST); //对PushST和PopST栈进行初始化
StackInit(&obj->PopST);
return obj;
}取队头元素
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->PopST)) //PopST栈为空的时候就要把PushST栈里面的元素导过来
{
while(!StackEmpty(&obj->PushST)) //导元素
{
int Pop=StackTop(&obj->PushST);
StackPop(&obj->PushST);
StackPush(&obj->PopST,Pop);
}
}
return StackTop(&obj->PopST); 返回PopST栈顶的元素
}销毁队头元素，并且返回队头元素。首先应该保存PopST栈的栈顶元素，然后销毁栈顶元素。
一个特别巧妙的点就是，我们在进行取队头元素的时候，如果PopST为空，取队头元素函数就会把PushST里面的元素导到PopST里面，这样我们在myQueuePop中就避免了导元素这一步骤。
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(obj); //取队头元素
StackPop(&obj->PopST);
return top;
}最后的push函数和判空函数还有销毁函数也是比较简单的
//直接在PushST队列中进行插入
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
//队列判空，当队列里面的两个队列都为空时才为空
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}
//销毁队列
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PopST);
StackDestroy(&obj->PushST);
}🚗 最终代码:
typedef int SLDataType;
typedef struct Stack{
SLDataType* a;
int top;
int capacity;
}Stack;
//对栈进行初始化
void StackInit(Stack* ptr);
//对栈进行销毁
void StackDestroy(Stack* ptr);
//在栈顶插入元素
void StackPush(Stack* ptr, SLDataType x);
//获取栈顶元素
SLDataType StackTop(Stack* ptr);
//对栈进行判断，如果为空，返回true，否则返回false
bool StackEmpty(Stack* ptr);
void StackPop(Stack* ptr);
//栈的初始化
void StackInit(Stack* ptr)
{
assert(ptr);
ptr->a = NULL;
ptr->capacity = ptr->top = 0;
}
//销毁栈
void StackDestroy(Stack* ptr)
{
assert(ptr);
free(ptr->a);
ptr->a = NULL;
ptr->capacity = ptr->top = 0; //初始化时，top=0，表示指向栈顶的下一个元素
}
//在栈顶插入元素
void StackPush(Stack* ptr, SLDataType x)
{
assert(ptr);
if (ptr->top == ptr->capacity)
{
int newcapacity = ptr->capacity == 0 ? 4 : ptr->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ptr->a, newcapacity*sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ptr->a = tmp;
ptr->capacity = newcapacity;
}
ptr->a[ptr->top++] = x;
}
//取栈顶元素
SLDataType StackTop(Stack* ptr)
{
assert(ptr);
assert(!StackEmpty(ptr));
return ptr->a[ptr->top - 1];
}
//栈判空
bool StackEmpty(Stack* ptr)
{
assert(ptr);
return ptr->top == 0;
}
//销毁栈顶元素
void StackPop(Stack* ptr)
{
assert(ptr);
assert(!StackEmpty(ptr));
ptr->top--;
}
typedef struct {
Stack PushST;
Stack PopST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->PushST);
StackInit(&obj->PopST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->PushST,x);
}
int myQueuePop(MyQueue* obj) {
int top=myQueuePeek(obj);
StackPop(&obj->PopST);
return top;
}
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->PopST))
{
while(!StackEmpty(&obj->PushST))
{
int Pop=StackTop(&obj->PushST);
StackPop(&obj->PushST);
StackPush(&obj->PopST,Pop);
}
}
return StackTop(&obj->PopST);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->PopST)&&StackEmpty(&obj->PushST);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->PopST);
StackDestroy(&obj->PushST);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/ 
