当前位置: 首页 > article >正文

数据结构算法题:栈与队列的使用(一)

目录

  • 用队列实现栈
    • 题目
    • 解题思路
    • 代码实现
      • 创建栈的结构体
      • 栈的初始化
      • 入栈
      • 出栈
      • 获取栈顶数据
      • 判断栈是否为空
      • 销毁栈

用队列实现栈

题目

题目描述:
在这里插入图片描述
示例:
在这里插入图片描述

解题思路

题目要求使用两个队列实现栈的入栈、出栈、获取栈顶元素、检查栈是否为空栈的基本操作。
既然要用到队列,我们首先得有能够实现队列基本操作的代码,这里直接复制之前已经写好的队列代码。

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* 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;
}

//取队尾数据
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;
}

现在有了队列的代码,继续分析如何通过队列实现栈的操作。
队列是先进先出,栈的话是先进后出。
他说要使用两个队列,我们就先创建两个队列:
在这里插入图片描述
这两个队列就是我们的栈,当我们入栈时,就是将数据放入队列内。
第一种情况:这里假设栈里面没有数据,我们放入哪个队列都可以。
第二种情况:这里假设栈里面有数据,我们就需要放入不为空的队列内。
在这里插入图片描述
如上面这种情况,我们就需要放入Q1内,这样当我们取栈顶数据时,才可以正确出栈。
综合一下就是入栈的数据放入不为空的队列内。

出栈的操作:假设我们入栈放入的是Q1
在这里插入图片描述
根据栈先进后出的特性,我们取栈顶取的是3,有什么方法可以取出来?
显然我们可以将Q1内的数据出队列存入到Q2,但是不是全部转移,在队列结构体里面我们定义了有效数据个数size,我们只要转移size-1个数据,剩下的就是栈顶的数据。

根据上面这个例子,我们转移2个数据,当转移完后,我们就剩下了3,而3刚好就是我们需要的数据,在出栈后我们释放栈顶及释放队列头节点空间即可。
在这里插入图片描述

入栈出栈了解完了,再了解一下取栈顶数据。
数据是放在队列里面的,队列是有头指针phead和尾指针ptail的,我们找到不为空的队列,直接返回队列的尾节点数据即可。

这里注意我们的队列无论在什么时候,两个队列是肯定有一个为空的。
在这些操作例,能改变队列是否为空的操作就只有入栈跟出栈,但是入栈时我们放的是不为空的队列,出栈我们在取出数据后会删除栈顶的数据,这样无论如何我们都会保持一个队列为空队列。

因为不能通过视频的方式讲解,会显得比较凌乱,可以在之上通过画图来帮助自己理解。

代码实现

这里队列的操作函数在上面已经提供了,这些代码在前面讲解队列时全部讲解过了,有不了解的可以去回顾一下哈。

创建栈的结构体

typedef struct {
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;

栈的初始化

栈是由两个队列实现的,那初始化就是初始化两个队列。

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

入栈

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//判断是否为空队列
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

出栈

int myStackPop(MyStack* obj) {
	//定义两个变量分别指向空队列和不为空队列
    Queue* empq=&obj->q1;
    Queue* noneq=&obj->q2;
    if(!QueueEmpty(&obj->q1))//这里判断Q1是否为空,不为空就要替换一下
    {
        empq=&obj->q2;
        noneq=&obj->q1;
    }
    while(QueueSize(noneq)>1)//转移数据到空队列
    {
        int pop=QueueFront(noneq);
        QueuePush(empq,pop);
        QueuePop(noneq);
    }
    //出队列
    int pop =QueueFront(noneq);
    QueuePop(noneq);
    return pop;
}

获取栈顶数据

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);//销毁队列1
    QueueDestroy(&obj->q2);//销毁队列2
    free(obj);
    obj=NULL;
}

感谢观看,有错请在评论区指正,谢谢。
最后赏赐小编一个三连吧各位看官老爷们。

原文地址:https://blog.csdn.net/qq_71391318/article/details/142941716
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/349752.html

相关文章:

  • 追逐AGI!微软AI副总裁、Phi小模型领导者Bubeck将加入OpenAI
  • JVM的GC算法以及常见垃圾回收器
  • 多级缓存-
  • HTML5实现古典音乐网站源码模板1
  • 分布式数据库:构建高效、可靠的数据存储与管理系统
  • 观察者模式的思考
  • CSS 实战录: 双栏、四等分、不等间距、自适应...
  • STL --- list(C++)
  • 线程局部存储(TLS)
  • C++11的新特性
  • 【C++算法】10.滑动窗口_无重复字符的最长子串
  • JSON 详解
  • JavaScript 数据类型
  • uniapp做的app实现首页左滑退出应用
  • 深度学习 | Pytorch的GPU版本查看GPU是否可用、GPU版本、GPU数量
  • 13.3寸三防平板大尺寸+高速运行提升工业软件操作体验
  • 数据结构之顺序表——动态顺序表(C语言版)
  • linux和端口相关的命令总结
  • JAVA软开-面试经典题(7)-字符串常量池
  • Flutter打包错误解决指南