一.题目要求
//用两个栈实现队列~栈只有一个进出入口，队列有两个
//实现以下4个功能
//1.Push
//2.Pop
//3.Peek~返回队列开头的元素
//4.empty
二.代码及思路解析
//一.要先写出实现顺序栈的基本代码//定义数据类型
typedef int STDataType;
//定义结构
typedef struct Stack{//数组STDataType* a;//栈顶int top;//容量int capacity;
}ST;//初始化
void StackInit(ST* ps){assert(ps);ps->a=NULL;//top可以有两个取值//top:0~top指向栈顶数据的下一个（先放后++）//top:1~top指向栈顶数据（先++后放）ps->top=0;ps->capacity=0;
}//栈出数据与入数据都在栈顶进行
//存放数据
void StackPush(ST* ps,STDataType x){assert(ps);//当栈为空或栈中的容量已满时，要realloc/malloc出一个新的节点用来存放数据if(ps->top==ps->capacity){//定义新的数组容量//三目运算符int newcapacity=newcapacity==0?4:ps->capacity*2;//扩容新的节点STDataType* tmp=(STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);//扩容失败，异常退出if(tmp==NULL){cout<<"realloc fail"<<endl;exit(-1);}ps->a=tmp;ps->capacity=newcapacity;}//开始存放数据ps->a[top]=x;ps->top++;
}//释放数据
void StackDestroy(ST* ps){assert(ps);free(ps->a);ps->a=NULL:ps->top=0;ps->capacity=0;
}//删除数据
void StackPop(ST* ps){assert(ps);//要先检查栈中是否还有数据//当栈中没有数据时，栈顶为空assert(ps->top>0);ps->top--;
}//访问数据
//访问栈顶的数据（最后面进来的数据）
STDataType* StackTop(ST* ps){assert(ps);//检查栈是否为空//assert(ps->top>0);//法2：利用判空函数，需要在前面先声明assert(!StackEmpty(ps));return ps->a[ps->top];
}//判空
bool StackEmpty(ST* ps){assert(ps);//当ps为空时，返回真return ps->top==0;
}//计算元素个数
int StackSize(ST* ps){assert(ps);//栈顶即最终栈中元素的数量return ps->top;
}// //~栈如何获取数据
// ST st;
// //初始化
// StackInit(st);
// //插入数据
// StackPush(&st,1);
// StackPush(&st,2);
// StackPush(&st,3);
// StackPush(&st,4);
// StackPush(&st,5);
// //取数据
// while(!StackEmpty(&st)){// cout<<StackTop(&st)<<endl;// //取出栈顶的数据后，记得将该数据Pop掉// StackPop(&st);
// }
// //定义栈后要记得销毁
// StackDestroy(&st);//二.利用两个栈来实现队列//定义两个栈的结构，一个用于入数据，一个用于出数据
typedef struct{//入数据ST PushST;//出数据ST PopST;
}MyQueue;//创建节点
MyQueue* myQueueCreate(){MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));//初始化StackInit(&q->PushST);StackInit(&q->PopST);return q;
}//入数据
void myQueuePush(MyQueue* obj,int x){//入数据的方式与正常栈中操作相同StackPush(&obj->PushST,x);
}//出数据
int myQueuePop(MyQueue* obj){//当PopST中没有数据时，将PushST的数据导过去，就符合先进先出的规则了if(StackEmpty(obj->PopST)){//导入数据while(!StackEmpty(obj->PushST)){StackPush(obj->PopST,StackTop(obj->PushST));//每导入一个数据，要记得Pop掉StackPop(obj->PushST);}}//出数据时，也要记得Pop掉int front=StackTop(obj->PopST);StackPop(obj->PopST);return front;
}//返回队头的数据
int myQueuePeek(MyQueue* obj){//队列规则：先进先出，返回队头的数据对应返回栈底的数据//当PopST中没有数据时，将PushST的数据导过去if(StackEmpty(&obj->PopST)){while(!StackEmpty(&obj->PushST)){StackPush(&obj->PopST,StackTop(&obj->PushST));StackPop(&obj->PushST);}}return StackTop(&obj->PopST);
}//判空
bool myQueueEmpty(MyQueue* obj){//两个栈都为空，才为空，两个栈是绑定在一起的return StackEmpty(obj->PushST)&&StackEmpty(obj->PopST);
}//释放
void myQueueFree(MyQueue* obj){//要先销毁掉两个栈的对象，再释放自身StackDestroy(&obj->PushST);StackDestroy(&obj->PopST);free(obj);
}
