【LeetCode】Easy | 225. Using queue to realize stack (pure C manual tearing queue)

subject

Ideas

The characteristics of the two structures ：① team ： Tail insertion + Head deletion ② Stack ： Tail insertion + Deletion at the end

The idea of tail insertion ： If both teams are empty , Pick any team Push; If one of the two teams is not empty , Then choose the team that is not empty Push
The idea of tail deletion ： Find a team that is not empty --> Before the $n-1$ Elements Push To the air force --> Will be the first $n$ Elements Pop

law ： In fact, it is not difficult to see that there must be an empty team .

Code

typedef int DataType;
typedef struct QueueNode
{
    
	DataType data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
    
	QueueNode* head;
	QueueNode* tail;
}Queue;
// initialization 
void QueueInit(Queue* pq)
{
    
	assert(pq);
	pq->head = pq->tail = NULL;
}
// The destruction 
void QueueDestroy(Queue* pq)
{
    
	assert(pq);
	// The first layer is deleted : Delete the node in the linked list 
	QueueNode* cur = pq->head;
	while (cur)
	{
    
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	// The second layer is deleted : Put... In the structure head and tail empty 
	pq->head = pq->tail = NULL;
}
// The team 
void QueuePush(Queue* pq, DataType x)
{
    
	assert(pq);
	// New node 
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->data = x;
	newNode->next = NULL;
	// There are no nodes in the queue 
	if (pq->head == NULL)
	{
    
		pq->head = pq->tail = newNode;
	}
	else
	{
    
		pq->tail->next = newNode;//tail Link with new node 
		pq->tail = newNode;// to update tail
	}
}
// Out of the team 
void QueuePop(Queue* pq)
{
    
	assert(pq);
	assert(pq->head);// When the queue is empty 
	QueueNode* next = pq->head->next;// The next node of the tag header 
	free(pq->head);
	pq->head = next;
	// If the queue is empty ,head along with next empty , but tail Became a wild pointer 
	if (pq->head == NULL)
	{
    
		pq->tail = NULL;
	}
}
// Take the team leader element 
DataType QueueFront(Queue* pq)
{
    
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
// Take the tail element 
DataType QueueBack(Queue* pq)
{
    
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
// Size of team 
int QueueSize(Queue* pq)
{
    
	assert(pq);
	assert(pq->head);
	QueueNode* cur = pq->head;
	int n = 0;
	while (cur)
	{
    
		++n;
		cur = cur->next;
	}
	return n;
}
// Determines if the queue is empty 
bool QueueEmpty(Queue* pq)
{
    
	assert(pq);
	return pq->head == NULL;
}
typedef struct {
    
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    
    MyStack* ms=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&ms->q1);
    QueueInit(&ms->q2);
    return ms;
}

void myStackPush(MyStack* obj, int x) {
    
    if(QueueEmpty(&obj->q1))
    {
    
        QueuePush(&obj->q2,x);
    }
    else{
    
        QueuePush(&obj->q1,x);
    }
}

int myStackPop(MyStack* obj) {
    
    Queue*emptyQ=&obj->q1;
    Queue*notEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
    
        emptyQ=&obj->q2;
        notEmptyQ=&obj->q1;
    }
    while(QueueSize(notEmptyQ)>1)
    {
    
        QueuePush(emptyQ,QueueFront(notEmptyQ));
        QueuePop(notEmptyQ);
    }
    int top=QueueFront(notEmptyQ);
    QueuePop(notEmptyQ);
    return top;
}

int myStackTop(MyStack* obj) {
    
    Queue*notEmptyQ=&obj->q1;
    if(QueueEmpty(&obj->q1))
    {
    
        notEmptyQ=&obj->q2;
    }
    return QueueBack(notEmptyQ);
}

bool myStackEmpty(MyStack* obj) {
    
    // Both tables are empty 
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    
	// The first layer releases 
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    // Second Cen release 
    free(obj);

}

/** * Your MyStack struct will be instantiated and called as such: * MyStack* obj = myStackCreate(); * myStackPush(obj, x); * int param_2 = myStackPop(obj); * int param_3 = myStackTop(obj); * bool param_4 = myStackEmpty(obj); * myStackFree(obj); */