力扣——用栈实现队列（C语言）

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

原理：

结构体MyQueue

定义两个栈，分别为pushST，popST，出栈中会讲具体原因。

创建队列MyQueue* myQueueCreate()

这里malloc申请一个MyQueue的结构体指针，直接使用栈的创建的函数，创建pushST，和popST，返回申请的指针。

出队int myQueuePop(MyQueue* obj)

这里栈的出栈是从最后一个出去，而队列是从头出去，所以这里定义的两个栈，先出栈到另一个空栈里面，这样相当于是将原来的栈，顺序颠倒，这样在进行出栈操作就是取出原来栈底的元素，也就是队头的元素，即实现了出队，这里需要注意，如果popST中不为空栈，则可以不用将pushSt中的元素转移到popST中，直接出栈popST中的元素，就是实现出队操作。

读取队头元素int myQueuePeek(MyQueue* obj)

这里和出队一样，只是最后不需要出栈，将队头元素出队，访问返回即可。

入队void myStackPush(MyStack* obj, int x)

入队和入栈一样都是从尾部插入，直接调用入栈的函数，插入到pushST即完成入队操作。

队列判空bool myQueueEmpty(MyQueue* obj)

需要判断pushST，和popST都为空，才能确定队列为空。

销毁队列void myQueueFree(MyQueue* obj)

调用栈销毁的函数，将两个栈销毁，再将MyQueue指针释放掉，置为空，即可。

整体结果：

定义的栈的数据结构，与前面文章栈的数据结构一样；

typedef int STDataType;
//定义栈的数据结构
typedef struct Stack
{
	STDataType* arr;
	int top;          //指向栈顶位置
	int capacity;     //容量
}ST;

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
void STDestroy(ST* ps)
{
	if (ps->arr != NULL)
		free(ps->arr);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}
//入栈--栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//空间满了--增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!\n");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}
//栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//出栈--栈顶
void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));
	--ps->top;
}
//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}
//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}


typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*pq=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->pushST);
    STInit(&pq->popST);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top=StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top=StackTop(&obj->popST);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushST);
    STDestroy(&obj->popST);
    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);
*/