#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int Stdatatype;

typedef struct stack
{
	Stdatatype* arr;
	int top;
	int capacity;
}ST;
//初始化
void StackInit(ST* ps)
{
	assert(ps);


	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = 0;//top定义为0的话那么就对应输入值的下一位，即先输入再++，，若是-1为初始化，就是先++再输入
}

//入栈
void StackPush(ST* ps, Stdatatype x)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		Stdatatype* temp = (Stdatatype*)realloc(ps->arr, newcapacity * sizeof(Stdatatype));
		if (!temp)
		{
			printf("realloc:fail\n");
			exit(-1);//错误就无法进行了，直接退出
		}
		ps->capacity = newcapacity;
		ps->arr = temp;
	}

	ps->arr[ps->top] = x;
	ps->top++;

}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//等于0就说明没有数据了。不能删了

	ps->top--;

}


//判空
bool StackEmpty(ST* ps)
{
	assert(ps);

	//无需三目或者条件
	//直接返回
	return ps->top == 0;
}

//判断栈顶元素
Stdatatype Stacktop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->arr[ps->top - 1];
}

//栈销毁
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->arr);
	ps->capacity = 0;
	ps->top = 0;
	ps->arr = NULL;
	//free(ps)		注意这里不确定ps这个结构体是否为malloc出来的，不应该free掉他，应该由外部结构释放
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//栈实现队列，设立一个push栈，一个pop栈
typedef struct {
	ST push;
	ST pop;

} MyQueue;

//初始化队列
MyQueue* myQueueCreate() {
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
	if (queue == NULL)
		return NULL;
	StackInit(&queue->push);
	StackInit(&queue->pop);
	return queue;
}

//利用栈的push添加到队列中
void myQueuePush(MyQueue* obj, int x) {
	assert(obj);
	StackPush(&obj->push, x);
}

//把push栈中的元素导到pop栈中，再出栈，也就是出队列头的元素
int myQueuePop(MyQueue* obj) {
	assert(obj);
	Stdatatype top;
	if (StackEmpty(&obj->pop))//pop栈中不为空直接pop最后一个元素就是队列的pop
	{
		while (!StackEmpty(&obj->push))
		{
			Stdatatype temp = Stacktop(&obj->push);
			StackPop(&obj->push);
			StackPush(&obj->pop, temp);//把push栈中的top导到pop栈中
		}
	}
	
	top = Stacktop(&obj->pop);
	StackPop(&obj->pop);
	
	return top;
}


//返回队列开头的元素
int myQueuePeek(MyQueue* obj) {
	assert(obj);
	if (!StackEmpty(&obj->pop))
	{
		return Stacktop(&obj->pop);//如果pop栈中的元素不为空，那么栈顶的元素就是队列开头元素
	}
	else
	{
		while (StackSize(&obj->push) > 0)		//如果pop栈中的没有元素，就把push栈中的元素全部导过来
		{
			Stdatatype temp = Stacktop(&obj->push);
			StackPop(&obj->push);
			StackPush(&obj->pop, temp);//把push栈中的top导到pop栈中
		}
		return Stacktop(&obj->pop);
	}
}

bool myQueueEmpty(MyQueue* obj) {
	assert(obj);                        //两个为空才是空
	return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
	assert(obj);
	StackDestroy(&obj->pop);
	StackDestroy(&obj->push);//利用栈销毁，实现队列销毁
	free(obj);
}
//
//int main()
//{
//	MyQueue* s = myQueueCreate();
//	myQueuePush(s, 0);
//	myQueuePush(s, 1);
//	Stdatatype a = myQueuePeek(s);
//	printf("%d\n", a);
//	a = myQueuePop(s);
//	printf("%d\n", a);
//
//	myQueueEmpty(s);
//	return 0;
//}