Mutual implementation of queue and heap (pure C implementation)

link : Using queue to implement stack

Their thinking ：
This problem can use two queues to realize a stack , Keep one queue empty at a time ,
The stack entry operation is equivalent to the queue entry operation for the non empty queue
The out of stack operation is equivalent to the out of queue of the tail element of the non empty queue , At this time, you need to queue the other elements of the non empty queue except the last element to the empty queue , Then out of the team, the last end of the team

Code ：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int QDataType;
typedef struct QueueNode
{
    
    struct QueueNode* next;
    QDataType data;
}QNode;


typedef struct 
{
    
    QNode* head;
    QNode* tail;
}Queue;



// initialization 
void QueueInit(Queue* pq)
{
    
    assert(pq);
    pq->head = pq->tail = NULL;
}


// The destruction 
void QueueDestroy(Queue* pq)
{
    


    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
    
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }


    pq->head = pq->tail = NULL;


}


// Put the data 
void QueuePush(Queue* pq, QDataType x)
{
    


    assert(pq);
    // Open up space 
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
    
        printf("malloc fail\n");
        exit(-1);
    }


    // Add data 
    newnode->data = x;
    newnode->next = NULL;


    // link 
    if (pq->tail == NULL)
    {
    
        pq->head = pq->tail = newnode;
    }
    else
    {
    
        pq->tail->next = newnode;
        pq->tail = newnode;
    }


}


// Judge empty 
bool QueueEmpty(Queue* pq)
{
    
    assert(pq);
    return pq->head == NULL;
}


// Delete 
void QueuePop(Queue* pq)
{
    


    assert(pq);
    assert(!QueueEmpty(pq));


    if (pq->head->next == NULL)
    {
    
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
    
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }


}



// Take the head 
QDataType QueueFront(Queue* pq)
{
    


    assert(pq);
    assert(!QueueEmpty(pq));


    return pq->head->data;
}


// Take the tail 
QDataType QueueBack(Queue* pq)
{
    


    assert(pq);
    assert(!QueueEmpty(pq));


    return pq->tail->data;
}


// length 
int QueueSize(Queue* pq)
{
    


    assert(pq);


    QNode* cur = pq->head;
    int count = 0;
    while (cur)
    {
    
        ++count;
        cur = cur->next;
    }


    return count;
}





typedef struct 
{
    
    Queue q1;
    Queue q2;
} MyStack;



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


    return obj;
}


void myStackPush(MyStack* obj, int x) 
{
    


    if(!QueueEmpty(&obj->q1))
    {
    
        QueuePush(&obj->q1, x);
    }
    else
    {
    
        QueuePush(&obj->q2, x);
    }


}


int myStackPop(MyStack* obj) 
{
    


    Queue* empyQ=&obj->q1;
    Queue* nonEmptyQ=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
    
        empyQ=&obj->q2;
        nonEmptyQ=&obj->q1;
    }


    // Move to another sequence , Delete the element returning to the top of the stack 
    while(QueueSize(nonEmptyQ)>1)
    {
    
        QueuePush(empyQ, QueueFront(nonEmptyQ));
        QueuePop(nonEmptyQ);
    }
    int top= QueueFront(nonEmptyQ);
    QueuePop(nonEmptyQ);


    return top;


}


int myStackTop(MyStack* obj)
{
    


    if(!QueueEmpty(&obj->q1))
    {
    
        return QueueBack(&obj->q1);
    }
    else
    {
    
        return QueueBack(&obj->q2);
    }


}


bool myStackEmpty(MyStack* obj) 
{
    
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}


void myStackFree(MyStack* obj) 
{
    
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);


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

link : Using stack to realize queue

Their thinking ：
This problem can be realized with two stacks , A stack for queue operation , Another stack performs out of line operations
Out of line operation ： When the stack out of the queue is not empty , Directly perform stack out operation , If it is empty , You need to import all the stack elements in the queue into the stack out of the queue , Then perform the stack out operation

Code ：

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>


typedef int STDataType;
typedef struct STack
{
    
	STDataType* data;
	int top;
	int capacity;
}ST;

// initialization 
void StackInit(ST* ps)
{
    

	assert(ps);
	ps->top = ps->capacity = 0;
	ps->data = NULL;

}

// Insert 
void StackPush(ST* ps, STDataType x)
{
    

	assert(ps);

	// Judge whether to expand capacity 
	if (ps->top == ps->capacity)
	{
    

		int newcapacity = ps->capacity ? (ps->capacity) * 2 : 3;
		STDataType* newdata = (STDataType*)realloc(ps->data, sizeof(STDataType) * newcapacity);
		if (newdata == NULL)
		{
    
			printf("newdata::file");
			exit(-1);
		}

		ps->data = newdata;
		ps->capacity = newcapacity;

	}

	ps->data[ps->top] = x;
	ps->top += 1;

}


// Judge empty 
bool StackEmpty(ST* ps)
{
    
	assert(ps);

	return ps->top == 0;
}


// Delete 
void StackPop(ST* ps)
{
    
	
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top -= 1;

}

// Take out 
STDataType StackTop(ST* ps)
{
    
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->data[ps->top - 1];

}

// The destruction 
void StackDestroy(ST* ps)
{
    

	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity=ps->top = 0;

}

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

}


typedef struct 
{
    
    ST pushst;
    ST popst;
} MyQueue;


MyQueue* myQueueCreate() 
{
    
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushst);
    StackInit(&obj->popst);

    return obj;

}

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

int myQueuePop(MyQueue* obj) 
{
    

    if(StackEmpty(&obj->popst))
    {
    
        // If pop The stack is empty. , hold push Stack down pop
        while(!StackEmpty(&obj->pushst))
        {
    
            StackPush(&obj->popst, StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }

    int front=StackTop(&obj->popst);
    StackPop(&obj->popst);
    return front;

}

int myQueuePeek(MyQueue* obj) 
{
    

    if(StackEmpty(&obj->popst))
    {
    
        // If pop The stack is empty. , hold push Stack down pop
        while(!StackEmpty(&obj->pushst))
        {
    
            StackPush(&obj->popst, StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }

    return StackTop(&obj->popst);

}

bool myQueueEmpty(MyQueue* obj) 
{
    
    return StackEmpty(&obj->popst) && StackEmpty(&obj->pushst);
}

void myQueueFree(MyQueue* obj) 
{
    
    StackDestroy(&obj->pushst);
    StackDestroy(&obj->popst);

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