[force buckle] realize stack with queue

225. Using queue to implement stack - Power button （LeetCode）

subject ：

Please use only two queues to implement one LIFO （LIFO） The stack , And supports all four operations of ordinary stack （push、top、pop and empty）.

Realization MyStack class ：

void push(int x) Put the element x Press into the top of the stack .
int pop() Remove and return the top element of the stack .
int top() Back to top of stack element .
boolean empty() If the stack is empty , return true ; otherwise , return false .
 

Be careful ：

You can only use the basic operations of the queue —— That is to say  push to back、peek/pop from front、size and  is empty  These operations .
The language you use may not support queues .  You can use list （ list ） perhaps deque（ deque ） To simulate a queue  , As long as it's a standard queue operation .

Ideas ：

The queue is characterized by first in, first out , The characteristic of stack is first in first out

This question requires two queues

Code ：

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;

}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* temp = cur->next;
		free(cur);
		cur = temp;
	}
	pq->head = NULL;
	pq->tail = NULL;
}
// The tail into the head 
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	assert(newNode);
	newNode->data = x;
	newNode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}
void QueuePop(Queue* pq)
{
	assert(pq);

	if (pq->head->next)
	{
		QueueNode* headNext = pq->head->next;
		free(pq->head);
		pq->head = headNext;
	}
	else
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
}
size_t QueueSize(Queue* pq)
{
	size_t size = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}

typedef struct
{
	Queue Q1;
	Queue Q2;
} MyStack;


MyStack* myStackCreate()
{
	MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&stack->Q1);
	QueueInit(&stack->Q2);
	return stack;
}

void myStackPush(MyStack* obj, int x)
{
	Queue* qNotNull = obj->Q1.head != NULL ? &obj->Q1 : &obj->Q2;// Queue that is not empty 
	QueuePush(qNotNull, x);
}

int myStackPop(MyStack* obj)
{
	Queue* qNotNull ;
	Queue* qNull;
	if (obj->Q1.head)
	{
		qNotNull = &obj->Q1;
		qNull = &obj->Q2;
	}
	else
	{
		qNotNull = &obj->Q2;
		qNull = &obj->Q1;
	}
	QueueDataType temp = 0;
	while (qNotNull->head != qNotNull->tail)
	{
		temp = qNotNull->head->data;
		QueuePop(qNotNull);
		QueuePush(qNull, temp);
	}
	temp = qNotNull->head->data;
	QueuePop(qNotNull);
	return temp;
}

int myStackTop(MyStack* obj)
{
	Queue qNotNull;
	Queue qNull;
	if (obj->Q1.head)
	{
		qNotNull = obj->Q1;
		qNull = obj->Q2;
	}
	else
	{
		qNotNull = obj->Q2;
		qNull = obj->Q1;
	}
	QueueDataType temp = 0;

	temp = qNotNull.tail->data;

	return temp;
}

bool myStackEmpty(MyStack* obj)
{
	if (obj->Q1.head == NULL && obj->Q2.head == NULL)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void myStackFree(MyStack* obj)
{
	QueueDestroy(&obj->Q1);
	QueueDestroy(&obj->Q2);
}