【LeetCode刷题指南】--队列实现栈，栈实现队列

🔥个人主页：@草莓熊Lotso

🎬作者简介：C++研发方向学习者

📖个人专栏： 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言：生活是默默的坚持，毅力是永久的享受。 

 前言：我们学完了队列和栈之后，还是需要通过做题来检验和巩固我们所学知识的，今天想给大家分享一下队列实现栈，栈实现队列这两个经典的力扣题。

目录

1.队列实现栈 

解题过程：

代码演示： 

 2.栈实现队列

解题过程： 

代码演示：

1.队列实现栈 

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

题目描述： 

题目示例： 

思路： 

• 入栈：往不为空的队列插入数据(能保证后续插入数据后最后也是先进后出)
• 出栈：非空队列中的前size-1个数据挪到另一个队列中，再将最后一个数据出队列
• 取栈顶：(不出数据)返回非空队列中的队尾数据

解题过程：

1.先定义一个结构，两个队列，再创建栈，动态申请一个空间，再初始化两个队列直接调用队列的方法就可以

2.入栈：往不为空的队列中插入数据，分情况讨论，q1不为空就往q1里插入数据，q2不为空就往q2里插入数据

3.出栈：先假设一个为空，再用一个if语句进行确定，假设错了就在if语句里面改过来。将非空队列中前size-1个数据挪到另一个队列中即空队列，所以当非空队列中的数据个数大于1时进行循环，重复取非空队列队头数据，插入到空队列中，再出数据的操作。循环结束后，非空队列中就剩下一个数据，因为返回类型为int，我们先利用取队头数据的方法将它保存下来，再出队列然后返回保存下来的数据

4.取栈顶：取栈顶数据不用出栈，所以谁为空我们直接取它的队尾数据然后返回就可以了

5.判空和销毁：全为空即为空，销毁的话先调用队列的销毁方法销毁掉两个队列，最后将栈释放掉后置空就可以了 

具体过程图示如下： 

代码演示： 

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

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size;//队中有效数据个数
}Queue;

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	//pq->size = 0;
}

//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newcode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newcode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;

	//如果队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newcode;
		//pq->size++;
	}
	else
	{
		pq->ptail->next = newcode;
		pq->ptail = pq->ptail->next;
		//pq->size++;
	}
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//出队
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//如果队伍中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
		//pq->size--||pq->size=0
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
		//pq->size--;
	}
}

//取队首数据
QDataType QueueHead(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾数据
QDataType QueueTail(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//队列有效数据个数
int QueueSize(Queue* pq)
{
	//如果使用了size记录直接返回就可以了
	//return pq->size;

	//如果没有就遍历
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur=pcur->next;
	}
	return size;
}

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}


//----------------------以上是队列结构的定义和常用方法----------------------------
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//创建一个栈
MyStack* myStackCreate() {
    MyStack*pter=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pter->q1);
    QueueInit(&pter->q2);

    return pter;
}

void myStackPush(MyStack* obj, int x) {
    //如果q1为空，往q1里插入数据，反之则是往q2里插入数据
    if(!QueueEmpty(&obj->q1))
    {
        //q1
        QueuePush(&obj->q1,x);
    }
    else{
        //q2
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //先假设一个为空
    Queue*emp=&obj->q1;
    Queue*nonemp=&obj->q2;
    if(QueueEmpty(&obj->q2))
    {
        emp=&obj->q2;
        nonemp=&obj->q1;
    }
    //将非空队列中前size-1个数据挪到另一个队列中
    while(QueueSize(nonemp)>1)
    {
        //取队头数据，插入空队列中
        QueuePush(emp,QueueHead(nonemp));
        //出数据
        QueuePop(nonemp);
    }
    //将非空队列中最后一个数据出队列,注意返回类型为int出之前先存一下
    int top=QueueHead(nonemp);
    QueuePop(nonemp);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        //取q1的队尾数据,并返回
        return QueueTail(&obj->q1);
    }
    else{
        //取q2的队尾数据,并返回
        return QueueTail(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    //全为空即为空
    return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
    obj=NULL;
}

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

写这个题之前由于我们是用的C语言，所以需要把之前我们实现好的队列结构拷贝一份上去

 2.栈实现队列

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

题目描述： 

题目示例： 

思路： 

• 入队列：往PushST里面插入数据
• 出队列：PopST不为空直接出数据，为空就把PushST的数据先导入过来再出数据
• 取队首：(不出数据)和出队列类似，但是不出数据，PopST不为空直接取栈顶数据，为空就把PushST的数据先导入过来再取

解题过程： 

1.定义两个栈，创建一个队列，申请一块空间，初始化两个栈，再返回

2.入队列：往PushST里面插入数据

3.出队列：如果PopST不为空直接出数据，注意返回类型，所以要先把PopST的栈顶数据存下来，再出数据，最后直接返回就可以了，但是如果PopST为空，我们先要将PushST的数据全部导入过来，直达PushST为空(重复取PushST栈顶元素，导入到PopST中，再出PushST的栈的操作)，循环完后PopST就不为空了可以直接出数据

4.取队首：操作和出队列一样，就是不用出数据，只用把最后那个PopST出栈的操作去掉就可以

5.判空和销毁：全为空即为空，销毁的话就是先调用栈的方法销毁掉两个栈，最后释放掉队列并置为空

具体过程图示如下：

代码演示：

typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;
	int capacity;
}ST;

//初始化
void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//销毁
void STDestory(ST* ps)
{
	if (ps->arr)
		free(ps->arr);

	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//入栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//检查空间
	//空间不够就增容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//出栈
void STPop(ST* ps)
{
	assert(!STEmpty(ps));
	ps->top--;
}

//取栈顶元素
STDataType STTop(ST* ps)
{
	assert(!STEmpty(ps));
	return 	ps->arr[ps->top - 1];;
}



//求栈中有效数据个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
//--------------------以上是栈结构的定义和常用方法-----------------------------
typedef struct {
    ST PushST;
    ST PopST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue*pq=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->PushST);
    STInit(&pq->PopST);
    return pq;
}

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

int myQueuePop(MyQueue* obj) {
    //PopST为空，先将PushST(不为空)的数据导入过来，再出栈
    if(STEmpty(&obj->PopST))
    {
        //取PushST栈顶数据，导入到PopST中，再出栈
        while(!STEmpty(&obj->PushST))
        {
            STPush(&obj->PopST,STTop(&obj->PushST));
            STPop(&obj->PushST);
        }
    }
    //PopST不为空直接出数据
    int top=STTop(&obj->PopST);
    STPop(&obj->PopST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    //PopST为空，先将PushST(不为空)的数据导入过来
    if(STEmpty(&obj->PopST))
    {
        //取PushST栈顶数据，导入到PopST中，再出栈
        while(!STEmpty(&obj->PushST))
        {
            STPush(&obj->PopST,STTop(&obj->PushST));
            STPop(&obj->PushST);
        }
    }
    //PopST不为空直接取数据
    int top=STTop(&obj->PopST);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    //全为空即为空
    return (STEmpty(&obj->PushST)&&STEmpty(&obj->PopST));
}

void myQueueFree(MyQueue* obj) {
    STDestory(&obj->PopST);
    STDestory(&obj->PushST);
    free(obj);
    obj=NULL;
}

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

往期回顾：

【LeetCode刷题指南】--随机链表的复制

【LeetCode刷题指南】--有效的括号

结语：本篇文章就到此结束了，《LetetCode刷题指南》中的题目比起之间的C语言刷题集中的题目，肯定会更加复杂一些。而且题目形式也不一样，大家需要注意一下。这篇中的栈实现队列，队列实现栈都很经典，大家下去可以多做一下试试。如果文章对你有帮助的话，欢迎评论，点赞，收藏加关注，感谢大家的支持