#define _CRT_SECURE_NO_WARNINGS 1
#include "assert.h"
#include "stdio.h"
#include "stdbool.h"
#include "stdlib.h"
#include "string.h"
#define N 10
typedef int STDataType;
int data;
//静态栈
//typedef struct Stack {
//	STDataType _a[N];
//	int _top;//栈顶元素
//}Stack;//动态栈
typedef struct ST {STDataType* _a;int _top;//栈顶元素int _capacity;//最大容量
}Stack;//初始化栈
void StackInit(Stack *pst);//入栈
void StackPush(Stack* pst, STDataType x);//出栈
void StackPop(Stack* pst);//获取栈顶元素
STDataType StackTop(Stack* pst);//获取栈的有效元素个数
int StackSize(Stack* pst);//判断栈是否为空，是返回1，非空返回0
bool StackEmpty(Stack* pst);//打印栈同时销毁
void StackPrint(Stack* pst);//销毁栈
void StackDestory(Stack* pst);//初始化栈
void StackInit(Stack* pst)
{assert(pst);pst->_a = NULL;pst->_top = 0;pst->_capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{assert(pst);if (pst->_top == pst->_capacity){STDataType newcapacity = pst->_capacity == 0 ? 4 : (pst->_capacity * 2);STDataType* temp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * newcapacity);if (temp == NULL){printf("realloc fail\n");exit(-1);}pst->_a = temp;pst->_capacity = newcapacity;}pst->_a[pst->_top] = x;pst->_top++;
}//出栈
void StackPop(Stack* pst)
{assert(pst);assert(pst->_top > 0);pst->_top--;
}//获取栈顶元素
STDataType StackTop(Stack* pst)
{assert(pst);assert(pst->_top>0);return pst->_a[pst->_top-1];
}//获取栈的有效元素个数
int StackSize(Stack* pst)
{assert(pst);return pst->_top;
}//判断栈是否为空，是返回1，非空返回0
bool StackEmpty(Stack* pst)
{assert(pst);if (pst->_top == 0)return true;elsereturn false;
}//打印栈
void StackPrint(Stack* pst)
{while (!StackEmpty(pst)){printf("%d\n", StackTop(pst));StackPop(pst);}
}//销毁栈
void StackDestory(Stack* pst)
{assert(pst);free(pst->_a);pst->_a = NULL;pst->_top = pst->_capacity = 0;
}//队列先进先出，栈先进后出
typedef struct {Stack st1;Stack st2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq=(MyQueue*)malloc(sizeof(MyQueue));if(pq==NULL)return NULL;StackInit(&pq->st1);StackInit(&pq->st2);return pq;
}void myQueuePush(MyQueue* obj, int x) {if(StackEmpty(&obj->st1)){StackPush(&obj->st2,x);}if(StackEmpty(&obj->st2)){StackPush(&obj->st1,x);}
}int myQueuePop(MyQueue* obj) {if(StackEmpty(&obj->st1)){while((&obj->st2)->_top!=1){StackPush(&obj->st1,StackTop(&obj->st2));StackPop(&obj->st2);}data=StackTop(&obj->st2);StackPop(&obj->st2);while((&obj->st1)->_top!=0){StackPush(&obj->st2,StackTop(&obj->st1));StackPop(&obj->st1);}return data;}else if(StackEmpty(&obj->st2)){while((&obj->st1)->_top!=1){StackPush(&obj->st2,StackTop(&obj->st1));StackPop(&obj->st1);}data=StackTop(&obj->st1);StackPop(&obj->st1);while((&obj->st2)->_top!=0){StackPush(&obj->st1,StackTop(&obj->st2));StackPop(&obj->st2);}}return data;
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->st1)){while((&obj->st2)->_top!=0){StackPush(&obj->st1,StackTop(&obj->st2));StackPop(&obj->st2);}data=StackTop(&obj->st1);while((&obj->st1)->_top!=0){StackPush(&obj->st2,StackTop(&obj->st1));StackPop(&obj->st1);}return data;}if(StackEmpty(&obj->st2)){while((&obj->st1)->_top!=0){StackPush(&obj->st2,StackTop(&obj->st1));StackPop(&obj->st1);}data=StackTop(&obj->st2);while((&obj->st2)->_top!=0){StackPush(&obj->st1,StackTop(&obj->st2));StackPop(&obj->st2);}}return data;
}bool myQueueEmpty(MyQueue* obj) {if(StackEmpty(&obj->st1)&&StackEmpty(&obj->st2))return true;return false;
}void myQueueFree(MyQueue* obj) {StackDestory(&obj->st1);StackDestory(&obj->st2);free(obj);obj=NULL;
}/*** 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);
*/