队列与堆的相互实现（纯c实现）

链接: 用队列实现栈

解题思路：
此题可以用两个队列去实现一个栈，每次始终保持一个队列为空，
入栈操作相当于给非空队列进行入队操作
出栈操作相当于非空队列的队尾元素出队，此时需要把非空队列除最后一个元素之外的其余元素入队到空队列，然后出队最后一个队尾元素

代码：

#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;



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


//销毁
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;


}


//放数据
void QueuePush(Queue* pq, QDataType x)
{
    


    assert(pq);
    //开辟空间
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
    
        printf("malloc fail\n");
        exit(-1);
    }


    //添加数据
    newnode->data = x;
    newnode->next = NULL;


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


}


//判断空
bool QueueEmpty(Queue* pq)
{
    
    assert(pq);
    return pq->head == NULL;
}


//删除
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;
    }


}



//取头
QDataType QueueFront(Queue* pq)
{
    


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


    return pq->head->data;
}


//取尾
QDataType QueueBack(Queue* pq)
{
    


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


    return pq->tail->data;
}


//长度
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;
    }


    //移到另一个数列，删除返回栈顶元素
    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); */

链接: 用栈实现队列

解题思路：
此题可以用两个栈实现，一个栈进行入队操作，另一个栈进行出队操作
出队操作： 当出队的栈不为空是，直接进行出栈操作，如果为空，需要把入队的栈元素全部导入到出队的栈，然后再进行出栈操作

代码：

#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;

//初始化
void StackInit(ST* ps)
{
    

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

}

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

	assert(ps);

	//判断是否扩容
	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;

}


//判断空
bool StackEmpty(ST* ps)
{
    
	assert(ps);

	return ps->top == 0;
}


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

	ps->top -= 1;

}

//取出
STDataType StackTop(ST* ps)
{
    
	assert(ps);
	assert(!StackEmpty(ps));

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

}

//销毁
void StackDestroy(ST* ps)
{
    

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

}

//长度
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))
    {
    
        //如果pop栈为空，把push栈倒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))
    {
    
        //如果pop栈为空，把push栈倒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); */