225.用队列实现栈（附带源码）

目录

一、思路

二、源码

一、思路

所以，创建两个队列

入栈，那个不空入那个

出栈，移动不空的队列的前n-1个到空队列，出队列第n个

很简单

总的来说，就是

下面直接手撕代码：

二、源码

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;//头
	QNode* rear;//尾
	int size;
}Queue;
// 初始化队列 
void QueueInit(Queue* q)
{
	q->front = q->rear = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	if ( q->front == NULL)
	{
		QNode* temp = (QNode*)malloc(sizeof(QNode));
		if (temp == NULL)
		{
			perror("malloc fail!\n");
			exit(-1);
		}
		temp->data = data;
		temp->next = NULL;
		q->front = q->rear = temp;
		q->size++;
	}
	else
	{
		QNode* temp = (QNode*)malloc(sizeof(QNode));
		if (temp == NULL)
		{
			perror("malloc fail!\n");
			exit(-1);
		}
		temp->data = data;
		temp->next = NULL;
		q->rear->next = temp;
		q->rear = temp;
		q->size++;
	}
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	if (q->front == NULL)
	{
		return;
	}
	QNode* second = q->front->next;
	free(q->front);
	q->front = second;
	q->size--;
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	if(q->rear == NULL)
	{
		return -1;
	}
	return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
	{
		return -1;
	}
	return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->size == 0)
		return  1;
	return 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
	{
		return;
	}
	QNode* cur = q->front;

	while (q->size--)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	printf("销毁成功！\n");
}

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


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

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

int myStackPop(MyStack* obj) {
    //将非空入空队列，留最后一个数据模拟出栈
    // if(QueueEmpty(obj->q1))
    // {
    //     int top = QueueBack(obj->q2);
    //     while(!QueueEmpty(obj->q2))
    //     {
    //         QueuePush(q1,QueueFront(obj->q2));
    //         QueuePop(&obj->q2);
    //     }
       
    // }
    // else
    // {
    //      while(!QueueEmpty(obj->q2))
    //     {
    //         QueuePush(q2,QueueFront(obj->q1));
    //         QueuePop(&obj->q1);
    //     }
     
    // }
    Queue *emptyq = &obj->q1;
    Queue *nonempty = &obj->q2;
    if(QueueEmpty(nonempty))
    {
        emptyq = &obj->q2;
        nonempty = &obj->q1;

    }
    while(QueueSize(nonempty) > 1)
    {
        QueuePush(emptyq,QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int top = QueueFront(nonempty);
    QueuePop(nonempty);
    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);
*/