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

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 stacks are empty , Pick any stack Push; If one of the two stacks is not empty , Then select a stack that is not empty Push
The idea of header deletion ： Found a stack that is not empty --> Before the $n-1$ Elements Push To empty stack --> Will be the first n Elements Pop --> because push The order to the empty stack is the reverse of the original order, so the remaining elements Push To the present empty stack

And questions 【225. Using queue to implement stack 】 The difference is , This needs to be reversed once .

Code

typedef int STDataType;
typedef struct Stack
{
    
	STDataType* a;
	int top;
	int capacity;
}ST;
typedef struct {
    
    ST s1;
    ST s2;
} MyQueue;
// initialization 
void StackInit(ST* ps)
{
    
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
// Push 
void StackPush(ST* ps, STDataType x)
{
    
	assert(ps);
	// Judge whether there is enough space 
	// The space is insufficient 
	if (ps->top == ps->capacity)
	{
    
		int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		// Failed to open up 
		if (tmp == NULL)
		{
    
			printf("realloc fail!");
			exit(0);
		}
		// It's a success 
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
// Out of the stack 
void StackPop(ST* ps)
{
    
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
// Take the top element of the stack 
STDataType StackTop(ST* ps)
{
    
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
// The size of the stack 
int StackSize(ST* ps)
{
    
	assert(ps);
	return ps->top;// Attention is from 0 At the beginning 
}
// Judge whether the stack is empty 
bool StackEmpty(ST* ps)
{
    
	assert(ps);
	return ps->top == 0;//==0 True return true;！=0 Yes false return false
}
// Destruction of the stack 
void StackDestroy(ST* ps)
{
    
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}


MyQueue* myQueueCreate() {
    
    MyQueue* mq=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&mq->s1);
    StackInit(&mq->s2);
    return mq;
}

void myQueuePush(MyQueue* obj, int x) {
    
    if(StackEmpty(&obj->s1))
    {
    
        StackPush(&obj->s2,x);
    }
    else
    {
    
        StackPush(&obj->s1,x);
    }
}

int myQueuePop(MyQueue* obj) {
    
    ST *emptyS=&obj->s1;
    ST* noEmptyS=&obj->s2;
    if(!StackEmpty(emptyS))
    {
    
        emptyS=&obj->s2;
        noEmptyS=&obj->s1;
    }
    while(StackSize(noEmptyS)>1)
    {
    
        StackPush(emptyS,StackTop(noEmptyS));
        StackPop(noEmptyS);
    }
    int top=StackTop(noEmptyS);
    StackPop(noEmptyS);
    emptyS=&obj->s1;
    noEmptyS=&obj->s2;
    if(!StackEmpty(emptyS))
    {
    
        emptyS=&obj->s2;
        noEmptyS=&obj->s1;
    }
     while(StackSize(noEmptyS)>0)
    {
    
        StackPush(emptyS,StackTop(noEmptyS));
        StackPop(noEmptyS);
    }
    return top;
}

int myQueuePeek(MyQueue* obj) {
    
     ST *emptyS=&obj->s1;
    ST* noEmptyS=&obj->s2;
    if(!StackEmpty(emptyS))
    {
    
        emptyS=&obj->s2;
        noEmptyS=&obj->s1;
    }
    while(StackSize(noEmptyS)>0)
    {
    
        StackPush(emptyS,StackTop(noEmptyS));
        StackPop(noEmptyS);
    }
    int top=StackTop(emptyS);
    emptyS=&obj->s1;
    noEmptyS=&obj->s2;
        if(!StackEmpty(emptyS))
    {
    
        emptyS=&obj->s2;
        noEmptyS=&obj->s1;
    }
     while(StackSize(noEmptyS)>0)
    {
    
        StackPush(emptyS,StackTop(noEmptyS));
        StackPop(noEmptyS);
    }
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
}

void myQueueFree(MyQueue* obj) {
    
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
}

/** * 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); */