首页 > 其他分享 >【数据结构】栈与队列OJ题（用队列实现栈）（用栈实现队列）

【数据结构】栈与队列OJ题（用队列实现栈）（用栈实现队列）

时间：2024-09-08 22:25:48浏览次数：11  
标签：ps pq return OJ 队列 assert 用栈 pst

目录

1.用队列实现栈oj题

对比

一、初始化

二、出栈 

三、入栈

四、取队头元素：

2.用栈实现队列 

一、定义

二、入队列

三、出队列

四、队头

五、判空


                                                                                                                                  

前言：如果想了解什么是栈和队列请参考上一篇文章进来一起把【数据结构】的【栈与队列】狠狠玩弄，痛快到大汗淋漓-CSDN博客

本篇不进行详细讲解栈和队列的定义

1.用队列实现栈oj题

. - 力扣（LeetCode）

在这个题目中，用两个队列实现栈，以队列的方法和知识点实现栈

对比

我们先来一个函数对比一下

这是用普通方法来实现的栈的初始化

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

 这是用队列方法实现的初始化

MyStack* MyStackCreat()
{
	MyStack* plt = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&plt->q1);
	QueueInit(&plt->q2);
	return plt;

	}

差异很明显，队列实现的方式明显要复杂很多，哈哈哈，这就是oj题，锻炼的是你的思维

写代码之前，我们用图解先来解析

一、初始化

首先我们要知道的是，我们用队列实现栈，要定义和初始化的是什么，用队列实现栈，实则是用队列的属性实现栈的属性，所以我们在这里要定义队列

但是为什么要定义两个队列？

题目上说了要用两个队列实现

所以我们定义队列，用结构体实现两个不同的队列。

代码：

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

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

	
}

二、出栈 

1.我们先将所有需要的数据入队列，这里要注意的是入队列的时候是队尾入，队头出，也就是FIFO（先进先出）

2.入完队列之后

我们开始模拟出栈思路，栈的属性是先进后出，队列的属性是先进先出，那么问题就来了，怎么用先进先出的两个数列实现先进后出。这个就是核心思路。

对于q1队列来说，此时q2队列是空的

既然是栈的属性先进的后出，所以就是q1的队尾先出，所以要找到q1的队尾。

                           那么你会说这不简单嘛？用指针不就完了？

但是哈，这里要强调，用队列的属性来实现栈的属性，使用的自然是队列的接口。而不是用库函数。

队列的基本操作有什么哪？

入队列，出队列，队列判别空，取队头，取队尾，队列有效个数，销毁

所以第一个思路就来了。

 将队尾前的元素直接移动到空队列q2，这样就q1队列剩下的元素就是队尾元素。

 之后如果再想出栈，再将q2的队尾前的元素移动到空队列q1，队尾元素出栈。

什么时候不能出栈了呢？直到两个队列都为空的时候

这样我们就用两个队列实现了先进后出，后进先出的栈的属性 

void MystackPop(MyStack* pst)
{
	QueueNode* nonequ = &pst->q1;
	QueueNode* emtyqu = &pst->q2;
	if (!QueueEmpty(&pst->q2))
	{

		emtyqu = &pst->q1;
	}

	else
	{
		emtyqu = &pst->q2;
	}

	while (QueueSize(nonequ) > 1)
	{
		int front = QueueFront(nonequ);
		QueuePush(emtyqu, front);
		QueuePop(nonequ);
	}
	int pop = QueueFront(nonequ);
	QueuePop(nonequ);
	return pop;
}

三、入栈

入栈操作相比于出栈先简单很多，入队列和入栈的属性其实是相同的，直接入就行了。所以体现在队列上就是先进的先入栈，所以就是队头入栈。 

void MyStackpush(MyStack* pst,int x)
{
	if (!QueueEmpty(&pst->q1))
	{
		QueuePush(&pst->q1, x);

	}
	else
	{
		QueuePush(&pst->q2, x);
	}

}

四、取队头元素：

取队头元素听起来很复杂，其实就是在栈里就是最后一个进入的，在队列里就是队尾 

直接返回队列的队尾元素即可 

int MystackTop(MyStack* pst)
{
	if (!QueueEmpty(&pst->q1))
	{
		return QueueBack(&pst->q1);
	}
	else
	{
		return QueueBack(&pst->q2);

	}
}

2.用栈实现队列 

232. 用栈实现队列 - 力扣（LeetCode）

对于用栈实现队列其实扒开底层逻辑就好，也不难理解，要实现push，pop，top，empty几种接口，其实就是入栈，出栈，返回栈顶，判断是否为空。至于怎么具体实现，接下来就是详细解释

一、定义

这里要定义两个栈，我们分别命名为pop和push队列

typedef struct
{
	ST pushST;
	ST popST;
}MyQU;

MyQU* MyQueueCreat()
{
	MyQU* pst = (MyQU*)malloc(sizeof(MyQU));
	STInit(&pst->pushST);
	STInit(&pst->popST);
	return pst;
}

二、入队列

两者逻辑差不多，直接入队列即可，

void MyqueuePush(MyQU* obj,int x)
{
	StackPush(&obj->pushST, x);
}

三、出队列

其实出队列的逻辑跟出栈的逻辑是相反的，跟上面的逻辑正好是倒过来的，底层逻辑是怎么用两个先进后出的栈实现先进先出的队列但其实方法是大相径庭的。

判断pop是否为空，为空的将push的数据全部出栈，然后入栈给pop。不会空直接出栈，相当于出队列

步骤一 

过程二： 

 

过程三： 

int MyQueuePop(MyQU* obj)
{
	if (StackEmpty(&obj->popST))
	{
		while (&obj->pushST)
		{
			StackPush(&obj->popST, StackTop(&obj->pushST));
			StackPop(&obj->pushST);
		}
	}
	int pop = StackTop(&obj->popST);
	StackPop(&obj->popST);
	return pop;

	
}

四、队头

队列中的队头限速是先进的那个元素，在栈中是最后出栈的那个元素，所以我们将栈的最后元素当作队头即可

五、判空

 判断队列是空的时候，相当于push和pop的栈都为空，只有两个都为空的时候才是空。

要用到的队列和栈的接口源码

队列的接口源码

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请新节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

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

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

// 出队列，队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		//删除队头元素、
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->phead->data;
}

//取队尾数据QU
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	/*int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++ ;
		pcur = pcur->next;
	}
	return size;*/
	return pq->size;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

 栈的接口

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

void STDestroy(ST* ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//1.判断空间是否足够
	if (ps->capacity == ps->top)
	{
		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 StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}


//取栈顶元素
STDataType StackTop(ST* ps)
{

	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

标签：ps,pq,return,OJ,队列,assert,用栈,pst
From： https://blog.csdn.net/wheeldown/article/details/141924334

相关文章

  • BZOJ 1396 识别子串 题解
    Statement给\(S\)，令\(x\)为\(S\)的第\(k\)个字符，称\(T=S[i..j]\)为关于\(x\)的识别子串，当且仅当：\(i\lek\lej\)（含\(x\)这一位）\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度，\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先......
  • BZOJ 4231 回忆树
    以下为自己口胡，未经网上搜索题解验证Statement一棵\(n\)个点的树，每条边有一个小写字母边权，\(m\)次询问，每次给定\(u,v,s\)，问字符串\(s\)在\(u\tov\)路径组成的字符串中出现了几次。\(n,m\le10^5,\sum|s|\le3\cdot10^5\).SolutionSol1把\(u\tov\)路径拆成\(u\t......
  • BZOJ 3796 Mushroom追妹纸 题解
    Statement给\(s_1,s_2,s_3\)，求最长的\(w\)的长度，满足\(w\)是\(s_1\)子串\(w\)是\(s_2\)子串\(s_3\)不是\(w\)子串Solution1以下是我没看题解瞎胡的首先一个弱智想法是，枚举\(s_1\)上\(w\)的左端点，二分右端点，判定时\(s_2\)用SAM，\(s_3\)用单串AC自动......
  • BZOJ 4502 串 题解
    妙妙数数题key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。我觉得难点通常在于“盯出一些充要条件”，......
  • DAY11 栈与队列part02
      逆波兰式求值代码随想录(programmercarl.com)1classSolution{2public:3intevalRPN(vector<string>&tokens){4stack<longlong>st;5for(inti=0;i<tokens.size();i++)6{78if(tokens[i]=="+......
  • LOJ4218 「IOI2024」尼罗河船运 题解
    题目描述有\(n\)件手工艺品，第\(i\)件重量为\(w_i\)，有参数\(a_i\)和\(b_i\)。每艘船最多可以运输两件手工艺品：如果只运输第\(i\)件，重量没有要求，代价为\(a_i\)。如果同时运输第\(i\)和第\(j\)件，要求\(|w_i-w_j|\leD\)，代价\(b_i+b_j\)。\(q\)次询问，给......
  • FreeRTOS 队列 Queue 源码解析
    目录一、队列1、队列结构体2、队列类型二、队列相关操作1、初始化1.1静态创建队列1.2动态创建队列1.3队列的初始化1.4队列的重置2、队列的发送2.1任务级入队函数2.1.1入队函数2.1.2队列锁2.1.3portYIELD_WITHIN_API2.2中断级入队函数3、任务的读取3.1任务......
  • 【代码随想录Day10】栈与队列Part01
    232.用栈实现队列题目链接/文章讲解/视频讲解：用栈实现队列classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=newStack<>();}publicvoidpush(int......
  • 【洛谷 P1996】约瑟夫问题 题解（队列+模拟+循环）
    约瑟夫问题题目描述个人围成一圈，从第一个人开始报数,数到的人出列，再由下一个人重新从开始报数，数到的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友，而该题是全部出圈。输入......
  • 多线程篇（阻塞队列- BlockingQueue）（持续更新迭代）
    目录一、了解什么是阻塞队列之前，需要先知道队列1.Queue（接口）二、阻塞队列1.前言2.什么是阻塞队列3.Java里面常见的阻塞队列三、BlockingQueue（接口）1.前言2.简介3.特性3.1.队列类型3.2.队列数据结构2.简介4.核心功能入队（放入数据）出队（取出数据）总结四......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99