栈和队列的互相实现

用队列实现栈

OJ链接

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

队列：先进先出，后进后出

栈：先进后出，后进先出 

思路：一个队列存数据；另一个队列用来出数据时，导数据

用单链表实现队列 代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
 
typedef int QDataType;
 
//创建队列节点
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
 
//创建维护队列的指针
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;//原本是需要遍历的，写在结构体里可以很好的是时间复杂度由O(N)变为O(1)
}Queue;
 
//初始化
void QueueInit(Queue* pq);
 
//空间释放
void QueueDestroy(Queue* pq);
 
//尾插
void QueuePush(Queue* pq, QDataType x);
 
//头删
void QueuePop(Queue* pq);
 
//取队头的数据
QDataType QueueFront(Queue* pq);
 
//取队尾的数据
QDataType QueueBack(Queue* pq);
 
//判断是否为空
bool QueueEmpty(Queue* pq);
 
//队列元素个数
int QueueSize(Queue* pq);

 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
 
void QueueDestroy(Queue* pq)
{
	assert(pq);
 
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
 
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
 
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
 
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
 
	newnode->val = x;
	newnode->next = NULL;
 
	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
 
	pq->size++;
}
 
void QueuePop(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);
 
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
 
	if (pq->phead == NULL)
		pq->ptail = NULL;
 
	pq->size--;
}
 
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);
 
	return pq->phead->val;
}
 
QDataType QueueBack(Queue* pq)
{
	assert(pq); 
	assert(pq->ptail);
 
	return pq->ptail->val;
}
 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
 
	return pq->phead == NULL;
}
 
int QueueSize(Queue* pq)
{
	assert(pq);
 
	return pq->size;
}

声明栈MyStack

//匿名结构体
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;//结构体类型
//如果不加typedef，MyStack就是结构体变量

创建&初始化栈myStackCreate

//初始化
MyStack* myStackCreate() {
    //MyStack mystack;出了作用域就销毁了
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

压栈myStackPush

哪个队列不为空就往哪个队列里面插入

//插入元素
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //找不为NULL的队列依次插入
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);//尾插
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

出栈并返回栈顶元素myStackPop 

这里有一个问题：如何知道q1和q2谁为空谁不为空？

  • 首先用假设法，假设其中一个队列是空，另一个队列不是空，然后进行验证。如果验证第一个队列不是空，就交换位置。
  • 然后就开始找栈顶元素。先将非空队列里的元素一个一个导入到空队列，（记得Pop！）直到非空队列里只剩下一个元素的时候停止。这个元素就是栈顶元素，然后返回它。最后不要忘记Pop一下。
//出栈
int myStackPop(MyStack* obj) {
    assert(obj);
    //判断为空/非空------假设法
    Queue*nonempty=&obj->q1;
    Queue*empty=&obj->q2;
    if(QueueEmpty(&obj->q1))//
    {
        nonempty=&obj->q2;
        empty=&obj->q1;//创建
    }

    //直到队列里只剩下一个元素，剩下的这个元素就是我们要找的栈顶元素
    while(QueueSize(nonempty)>1)//队列里面的元素个数 > 1
    {
        QueuePush(empty, QueueFront(nonempty));//把队头的元素一个一个放到空队列，
                                               
        QueuePop(nonempty);//把刚放的那个元素从原队列删除
    }

    int top=QueueFront(nonempty);//队列尾的元素——栈顶元素
    QueuePop(nonempty);
    return top;
}

返回栈顶元素myStackTop

我们要能够发现，栈顶的元素也就是队尾的元素。所以我们直接返回队尾元素就可以了。

//栈顶元素
int myStackTop(MyStack* obj) {
	if(!QueueEmpty(&obj->q1)) 
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

判断栈是否为空myStackEmpty

//判断是否为空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);//&&
}

释放空间myStackFree

//释放空间
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj=NULL;
}

总代码

//匿名结构体
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;//结构体类型
//如果不加typedef，MyStack就是结构体变量

//初始化
MyStack* myStackCreate() {
    //MyStack mystack;出了作用域就销毁了
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

//插入元素
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //找不为NULL的队列依次插入
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);//尾插
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

//出栈
int myStackPop(MyStack* obj) {
    assert(obj);
    //判断为空/非空------假设法
    Queue*nonempty=&obj->q1;
    Queue*empty=&obj->q2;
    if(QueueEmpty(&obj->q1))//
    {
        nonempty=&obj->q2;
        empty=&obj->q1;//创建
    }

    //直到队列里只剩下一个元素，剩下的这个元素就是我们要找的栈顶元素
    while(QueueSize(nonempty)>1)//队列里面的元素个数 > 1
    {
        QueuePush(empty, 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);
    obj=NULL;
}

用栈实现队列

OJ链接

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

一个栈用于push，另一个栈用于pop。当用来出栈的那个栈空了以后，入栈的那个栈里面的元素才能导入另一个栈！这样就可以很好的实现队列的先进先出原则。

用数组实现栈 代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);


void STInit(ST* pst)
{
	assert(pst);
	pst->a = 0;
	pst->top = 0;
	pst->capacity = 0;
}

void Createcapacity(ST* pst)
{
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
}

void STPush(ST* pst, STDatatype x)
{
	assert(pst);
	Createcapacity(pst);
	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}


bool STempty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//为0就是true 为！=0就是为flase
}


int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}


void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

声明队列MyQueue

typedef struct {
    ST stpush;
    ST stpop;
} MyQueue;

创建&初始化队列myQueueCreate 

  • 创建的临时变量出了作用域就销毁了，所以需要malloc才可。
MyQueue* myQueueCreate() {
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
    STInit(&obj->stpush);
    STInit(&obj->stpop);
    return obj;
}

入队列myQueuePush

//入队列
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->stpush, x);
}

返回队头元素myQueuePeek

int myQueuePeek(MyQueue* obj) {
    //当stpop为空的时候
	if(STempty(&obj->stpop))
	{
        //当stpush不为空
		while(!STempty(&obj->stpush))
		{
			int x=STTop(&obj->stpush);
            STPush(&obj->stpop,x);
            STPop(&obj->stpush);
		}
	}
	return STTop(&obj->stpop);
}

从队列的开头移除并返回元素myQueuePop 

可以直接调用myQueuePeek，就会直接把元素都移到stpop，我们只管删除就行了。

int myQueuePop(MyQueue* obj) {
    int first=myQueuePeek(obj);
    STPop(&obj->stpop);
    return first;
}

判断队列是否为空myQueueEmpty

bool myQueueEmpty(MyQueue* obj) {
    return STempty(&obj->stpush) && STempty(&obj->stpop);
}

 释放空间myQueueFree

  • 销毁的时候要先销毁队列开辟的空间，不然会造成野指针。
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->stpush);
    STDestroy(&obj->stpop);
    free(obj);
    obj=NULL;
}

总代码

typedef struct {
	ST stpush;
	ST stpop;
} MyQueue;

MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	STInit(&obj->stpush);
	STInit(&obj->stpop);
	return obj;
}

//入队列
void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->stpush, x);
}

int myQueuePeek(MyQueue* obj) {
	//当stpop为空的时候
	if (STempty(&obj->stpop))
	{
		//当stpush不为空
		while (!STempty(&obj->stpush))
		{
			int x = STTop(&obj->stpush);
			STPush(&obj->stpop, x);
			STPop(&obj->stpush);
		}
	}
	return STTop(&obj->stpop);
}

int myQueuePop(MyQueue* obj) {
	int first = myQueuePeek(obj);
	STPop(&obj->stpop);
	return first;
}

bool myQueueEmpty(MyQueue* obj) {
	return STempty(&obj->stpush) && STempty(&obj->stpop);
}



void myQueueFree(MyQueue* obj) {
	STDestroy(&obj->stpush);
	STDestroy(&obj->stpop);
	free(obj);
	obj = NULL;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/231827.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Qexo博客后台管理部署

Qexo博客后台管理部署

Qexo博客后台管理部署 个人主页 个人博客 参考文档 https://www.oplog.cn/qexo/本地部署 采用本地Docker部署管理本地Hexo 下载代码包 若无法下载使用科学工具下载到本地在上传到服务器 wget https://github.com/Qexo/Qexo/archive/refs/tags/3.0.1.zip# 解压 unzip Qexo…
阅读更多...
Python 中检查一个数是不是另一个数的整数次幂

Python 中检查一个数是不是另一个数的整数次幂

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com 在数学和计算中&#xff0c;确定一个数是否为另一个数的整数次幂是一个常见而重要的问题。例如&#xff0c;我们可能需要判断一个数是否是某个数的平方、立方或其他幂次。本文将探讨在Python中如何实现这一功能&…
阅读更多...
算数运算符和算数表达式

算数运算符和算数表达式

基本算数运算符 算数运算符&#xff1a; &#xff08;加法运算符或正值运算符&#xff09;、-&#xff08;减法运算符或负值运算符&#xff09;、*&#xff08;乘&#xff09;、/&#xff08;除&#xff09;、%&#xff08;求余数&#xff09; 双目运算符&#xff1a; 双目…
阅读更多...
【QED】小樱的问题

【QED】小樱的问题

目录 题目描述输入格式输出格式 测试样例样例说明 思路核心代码 题目描述 在 f u f u fufu fufu乐园&#xff0c;每天都会有各种各样精彩的内容发生。就比如说&#xff0c;今天&#xff0c;小樱的米饭店开张啦&#xff01; 为了吸引 f u f u fufu fufu们前来购买小樱的大米&a…
阅读更多...
唱响主旋律——建行江门市分行推动服务实体经济高质量发展

唱响主旋律——建行江门市分行推动服务实体经济高质量发展

建行江门市分行主动对接当地战略部署&#xff0c;在侨乡热土踏歌而行&#xff0c;全力当好服务实体经济的主力军和维护金融稳定的压舱石&#xff0c;在助力再造一个现代化新江门上贡献建行力量。 输血实体 为实体经济服务是金融的天职。建行江门市分行积极发挥在重大基建领域…
阅读更多...
异步回调模式

异步回调模式

异步回调 所谓异步回调&#xff0c;本质上就是多线程中线程的通信&#xff0c;如今很多业务系统中&#xff0c;某个业务或者功能调用多个外部接口&#xff0c;通常这种调用就是异步的调用。如何得到这些异步调用的结果自然也就很重要了。 Callable、Future、FutureTask publi…
阅读更多...
C/C++之输入输出

C/C++之输入输出

文章目录 一.C语言的输入输出1.printfi. 输出整数ii. 浮点数iii.字符 & 字符串 2.scanfi.整数ii.浮点数iii. 字符 & 字符串 3.特殊用法i. * 的应用ii. %n 的应用iii. %[] 的应用 二.C中的输入输出1.couti. 缓冲区&#xff08;buffer&#xff09;ii. cout之格式化输出 2…
阅读更多...
python爬虫学习-批量爬取图片

python爬虫学习-批量爬取图片

python爬虫学习-批量爬取图片 爬虫步骤爬取前十页图片到本地根据页码获取网络源码使用xpath解析网页解析网页并下载图片主函数如下 爬取的网站为站长素材&#xff08;仅做学习使用&#xff09; 爬取的目标网站为 https://sc.chinaz.com/tupian/qinglvtupian.html如果爬取多页&…
阅读更多...
有什么进销存软件能对接微信小程序？

有什么进销存软件能对接微信小程序？

有什么进销存软件能对接微信小程序&#xff1f; 据我所知&#xff0c;很多进销存软件都有配套的微信小程序吧。 以我们现在用的这个为例&#xff0c;这也是同行推荐过来的&#xff0c;很好用&#xff0c;而且性价比很高—— 在线平台&#xff0c;无需下载APP&#xff0c;搭载…
阅读更多...
Python Cupy 模块：加速大规模数值计算

Python Cupy 模块：加速大规模数值计算

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com Cupy是一个基于NumPy的库&#xff0c;专门设计用于在GPU上进行高性能计算。它提供了与NumPy相似的API&#xff0c;因此用户可以很容易地将现有的NumPy代码迁移到Cupy上&#xff0c;从而充分利用GPU的并行计算能力…
阅读更多...
Java数据结构06——树

Java数据结构06——树

1.why: 数组&链表&树 2. 大纲 2.1前中后序 public class HeroNode {private int no;private String name;private HeroNode left;//默认为nullprivate HeroNode right;//默认为nullpublic HeroNode(int no, String name) {this.no no;this.name name;}public int …
阅读更多...
基于Python的前程无忧、51job、智联招聘等招聘网站数据获取及数据分析可视化大全【代码+演示】

基于Python的前程无忧、51job、智联招聘等招聘网站数据获取及数据分析可视化大全【代码+演示】

需要本项目的可以私信博主&#xff0c;获取&#xff0c;或者文末卡片获取 import pandas as pd import glob import warnings warnings.filterwarnings("ignore")# 指定目录 directory ./data/# 使用glob来获取所有.xlsx文件 excel_files glob.glob(directory *.x…
阅读更多...
软件科技成果鉴定测试需提供哪些材料?

软件科技成果鉴定测试需提供哪些材料?

为了有效评估科技成果的质量&#xff0c;促进科技理论向实际应用转化&#xff0c;所以需要进行科技成果鉴定测试。申请鉴定的科技成果范围是指列入国家和省、自治区、直辖市以及国务院有关部门科技计划内的应用技术成果&#xff0c;以及少数科技计划外的重大应用技术成果。 　　…
阅读更多...
高项备考葵花宝典-项目进度管理输入、输出、工具和技术(下，很详细考试必过)

高项备考葵花宝典-项目进度管理输入、输出、工具和技术(下，很详细考试必过)

项目进度管理的目标是使项目按时完成。有效的进度管理是项目管理成功的关键之一&#xff0c;进度问题在项目生命周期内引起的冲突最多。 小型项目中&#xff0c;定义活动、排列活动顺序、估算活动持续时间及制定进度模型形成进度计划等过程的联系非常密切&#xff0c;可以视为一…
阅读更多...
Bash脚本处理ogg、flac格式到mp3格式的批量转换

Bash脚本处理ogg、flac格式到mp3格式的批量转换

现在下载的许多音乐文件是flac和ogg格式的&#xff0c;QQ音乐上下载的就是这样的&#xff0c;这些文件尺寸比较大&#xff0c;在某些场合使用不便&#xff0c;比如在车机上播放还是mp3格式合适&#xff0c;音质这些在车机上播放足够了&#xff0c;要求不高。比如本人就喜欢下载…
阅读更多...
unity 2d 入门 飞翔小鸟 Cinemachine 镜头跟随小鸟 多边形碰撞器 解决镜头不会穿模问题（十二)

unity 2d 入门 飞翔小鸟 Cinemachine 镜头跟随小鸟 多边形碰撞器 解决镜头不会穿模问题（十二)

1、安装 window->package manager 2、创建Cinemachine 右键->Cinemachine->2D Carmera 3、创建空对象和多边形控制器如图 记得勾选 is Trigger 空对象位置记得要和小鸟保持一致&#xff0c;不然等下写完脚本后&#xff0c;镜头一开始会移动一下 4、将多边形触…
阅读更多...
课堂练习3.3：进程的调度

课堂练习3.3：进程的调度

3-6 课堂练习3.3&#xff1a;进程的调度 在内存中一般存放着数目远大于计算机 CPU 个数的进程&#xff0c;进程调度的作用是选择合适的进程来使用CPU&#xff0c;进程调度器对系统性能有重要影响。本实训分析Linux 0.11的进程调度算法&#xff0c;该操作系统采用了一种时间片与…
阅读更多...
文件重命名：轻松高效，批量重命名文件只需掌握一点技巧

文件重命名：轻松高效，批量重命名文件只需掌握一点技巧

在日常工作和生活中&#xff0c;经常要对文件进行重命名。有时候可能要对一批文件进行重命名&#xff0c;如果一个个手动重命名&#xff0c;不仅费时费力&#xff0c;还容易出错。如何掌握一些文件重命名的技巧&#xff0c;那就能轻松高效地完成这项任务。接下来就讲解云炫文件…
阅读更多...
华为ensp实验——基于全局地址池的DHCP组网实验

华为ensp实验——基于全局地址池的DHCP组网实验

目录 前言实验目的实验内容实验结果 前言 该实验基于华为ensp&#xff0c;版本号是1.3.00.100 V100R003C00SPC100&#xff0c;只供学习和参考&#xff0c;不作任何商业用途。 具体的DHCP命令可以看系列文章链接&#xff0c;计算机网络实验&#xff08;华为eNSP模拟器&#xff…
阅读更多...
win11+RTX4070Ti 安装 CUDA + cuDNN（图文教程）

win11+RTX4070Ti 安装 CUDA + cuDNN（图文教程）

win11RTX4070TI 安装 CUDA cuDNN&#xff08;图文教程&#xff09; 教程基本信息介绍查看电脑是否有最新显卡驱动并确定已安装下载CUDA安装CUDA查看CUDA是否安装成功安装cuDNN验证cuDNN是否安装成功 教程基本信息介绍 此教程为本人安装记录&#xff0c;仅供参考 本教程时间&am…
阅读更多...
最新文章

Copyright @ 2022~2023