【数据结构与算法】队列和栈的相互实现以及循环队列

在这里插入图片描述

目录

  • 🌔一.用队列实现栈
    • 🌙1.题目描述
    • 🌙2.思路分析
    • 🌙3.代码实现
    • ⛈二.用栈实现队列
      • ☔1.题目描述
      • ☔2.思路分析
      • ☔3.代码实现
      • 🌈三.实现循环队列

🌔一.用队列实现栈

🌙1.题目描述

我们先看一下题目链接
在这里插入图片描述

🌙2.思路分析

我们知道栈是后进先出的线性表，题目要求我们使用两个队列来实现，队列的特性是先进先出，从队尾进 队头出,图解如下:
在这里插入图片描述
那我们如何向队列进元素1 2 3 4出队列是4 3 2 1的顺序呢。假设现在队列中有1 2 3 4:
在这里插入图片描述
我们想让4先出队列的话，可以将前面的1 2 3先转移到另一个队列中，再出4，以此类推实现后进先拿出。使得一个队列为空用来出队列时倒元素的目的地，另一个不为空的队列用来插入数据。想要返回栈顶元素 只要返回非空队列的队尾元素即可。

🌙3.代码实现

代码的实现，我们需要先手撕个队列包括队列的基本功能并且定义两个队列:

typedef int QDataType;

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


typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
void QueueInit(Queue* pt);
void QueueDestroy(Queue* pt);

void QueuePush(Queue* pt, QDataType x);
void QueuePop(Queue* pt);

int QueueSize(Queue* pt);

bool QueueEmpty(Queue* pt);

QDataType QueueFront(Queue* pt);
QDataType QueueBack(Queue* pt);



void QueueInit(Queue* pt)
{
	assert(pt);

	pt->head = pt->tail = NULL;
	pt->size = 0;
}

void QueueDestroy(Queue* pt)
{
	assert(pt);
	QNode* cur = pt->head;

	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pt->head = pt->tail = NULL;
	pt->size = 0;
}


void QueuePush(Queue* pt, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->next = NULL;
	newnode->data = x;

	if (pt->head == NULL)
	{
		assert(pt->tail == NULL);
		pt->head = pt->tail = newnode;
	}
	else
	{
		pt->tail->next = newnode;
		pt->tail = newnode;
	}

	pt->size++;

}


void QueuePop(Queue* pt)
{
	assert(pt);
	assert(pt->head != NULL);

	if (pt->head->next == NULL)
	{
		free(pt->head);
		pt->head = pt->tail = NULL;
	}
	else
	{
		QNode* next = pt->head->next;

		free(pt->head);
		pt->head = next;
	}
	pt->size--;
}


int QueueSize(Queue* pt)
{
	assert(pt);
	
	return pt->size;
}

bool QueueEmpty(Queue* pt)
{
	assert(pt);
	
	return pt->size == 0;
}

QDataType QueueFront(Queue* pt)
{
	assert(pt);
	assert(!QueueEmpty(pt));

	return pt->head->data;
}
QDataType QueueBack(Queue* pt)
{
	assert(pt);
	assert(!QueueEmpty(pt));

	return pt->tail->data;
}

紧接着即使栈的实现:

MyStack* myStackCreate() {
    MyStack*ptr=(MyStack*)malloc(sizeof(MyStack));
    if(ptr==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    QueueInit(&ptr->q1);
    QueueInit(&ptr->q2);

    return ptr;

}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))//向非空队列插入数据
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
    
}

int myStackPop(MyStack* obj) {
    Queue* empty=&obj->q1;//先假设空与非空队列
    Queue* noempty=&obj->q2;

    if(!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }

    while(QueueSize(noempty)>1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }

    int ret=QueueFront(noempty);

    QueuePop(noempty);

    return ret;

}

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

⛈二.用栈实现队列

☔1.题目描述

我们先看一下题目链接
在这里插入图片描述

☔2.思路分析

这题相反，需要我们实现两个栈来实现队列。究其本质就是使用两个后进先出显示先进先出，我们用图例来理解下:
在这里插入图片描述
入栈1 2 3 4后出栈顺序为4 3 2 1我们可以依次顺序入到另一个栈中，再将数据从栈中弹出，即可做到出栈1 2 3 4的顺序。图示如下：
在这里插入图片描述

☔3.代码实现

代码还是需要先手撕个栈以及实现栈的基本功能并定义两个栈分别用来插入和删除:

typedef int STDataType;


typedef struct stack
{
	STDataType* a;
	STDataType top;
	STDataType capacity;
}ST;

void InitST(ST* s);//初始化栈
void DestroyST(ST* s);//销毁栈

void Push(ST* s, int x);//压栈
void Pop(ST* s);//出栈

bool STEmpty(ST* s);//判断栈是否为空栈
STDataType STSize(ST* s);//当前栈的元素个数
STDataType STTop(ST* s);//返回栈顶元素
void InitST(ST* s)
{
	assert(s);
	s->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (s->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	s->capacity = 4;
	s->top = -1;///top记录指向的当前元素
}

void DestroyST(ST* s)
{
	assert(s);
	s->capacity = 0;
	free(s->a);
	s->a = NULL;
	s->top = -1;
}

void Push(ST* s,int x)
{
	assert(s);

	if (s->top+1 == s->capacity)
	{
		s->a = (STDataType*)realloc(s->a,sizeof(STDataType)*s->capacity*2);
		if (s->a == NULL)
		{
			perror("malloc fail");
			return;
		}
		s->capacity *= 2;
	}
	s->a[s->top+1] = x;
	s->top++;

}

void Pop(ST* s)
{
	assert(s);
	assert(!STEmpty(s));

	s->top--;
}

bool STEmpty(ST* s)
{
	assert(s);
	if (s->top == -1)
		return true;
	return false;
}

STDataType STSize(ST* s)
{
	assert(s);

	return s->top + 1;
}

STDataType STTop(ST* s)
{
	assert(s);

	return s->a[s->top];
}

typedef struct {
    ST popst;
    ST pushst;
} MyQueue;

定义时我们就指定了用来插入的栈和删除的栈，我们在创建好自己的队列后，对队列进行插入操作时，只需要向pushst栈插入数据即可，另一个popst栈保持为空，在需要出队列时，将另一个栈的数据倒过来，再出数据 即可保证先进先出的顺序。

MyQueue* myQueueCreate() {
    MyQueue* ptr=(MyQueue*)malloc(sizeof(MyQueue));
    if(ptr == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    InitST(&ptr->popst);
    InitST(&ptr->pushst);
    return ptr;

}

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

int myQueuePop(MyQueue* obj) {
    int ret=myQueuePeek(obj);
    Pop(&obj->popst);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
            Push(&obj->popst,STTop(&obj->pushst));
            Pop(&obj->pushst);           
        }
    }
    return STTop(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popst)&&STEmpty(&obj->pushst);
}

void myQueueFree(MyQueue* obj) {
    DestroyST(&obj->popst);
    DestroyST(&obj->pushst);
    free(obj);

}

🌈三.实现循环队列

线性表有顺序存储和链式存储，栈是线性表，具有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在两种存储方式。队列的链式存储即是进行尾插头删的单链表，所以我们讲解队列的顺序存储———循环队列。
借助题目更好的讲解循环队列题目链接
在这里插入图片描述
首先我们创建结构体用来存储数据，其中包含指向存储数据地址的指针，记录队列有效长度的整形变量，还有两个记录循环队列头和尾数组下标的变量。

typedef struct {
    int *a;
    int rear;
    int front;
    int k;

} MyCircularQueue;

接着我们初始化队列，对于给定的有效长度k我们malloc比k多一的存储空间，方便表示存储满的情况另一种解决方法是增加size变量 用于记录当前数据个数。

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->rear=obj->front=0;
    obj->k=k;
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    return obj;
}

队列为空的即是头尾指针指向同一地方的情况。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

判断队列是否满，由于rear有可能比front大，也可能小，所以尽管他们只相差一个位置时就是满的情况，但可能相差整整一圈。为了避免判断错误，则需要取模判断。

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1) == obj->front;
}

剩余代码

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear++]=value;
    obj->rear%=(obj->k+1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return false;
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    int x=obj->rear == 0? obj->k:obj->rear-1;//防止数据存储到最后一位
    return obj->a[x];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

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

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

相关文章

大数据技术之Hive SQL题库-初级

大数据技术之Hive SQL题库-初级

第一章环境准备1.1 建表语句hive>-- 创建学生表 DROP TABLE IF EXISTS student; create table if not exists student_info(stu_id string COMMENT 学生id,stu_name string COMMENT 学生姓名,birthday string COMMENT 出生日期,sex string COMMENT 性别 ) row format delim…
阅读更多...
STM32学习（九）

STM32学习（九）

IWDG的本质 Independent watchdog，即独立看门狗。 本质是：能产生系统复位信号的计时器。 递减的计数器。时钟由独立的RC振荡器提供（不是来自于主时钟HSE或HSI），可在待机或者停止模式下运行。看门狗被激活后&#xff…
阅读更多...
【云原生 • Docker】cAdvisor+Prometheus+Grafana 10分钟搞定Docker容器监控平台

【云原生 • Docker】cAdvisor+Prometheus+Grafana 10分钟搞定Docker容器监控平台

文章目录cAdvisorPrometheusGrafana 10分钟搞定Docker容器监控平台cAdvisor部署Prometheus部署Grafana部署cAdvisorPrometheusGrafana 10分钟搞定Docker容器监控平台 cAdvisor(Container Advisor) 是 Google 开源的一个容器监控工具，可用于对容器资源的使用情况和性…
阅读更多...
【网络安全必备知识】本地提权漏洞分析

【网络安全必备知识】本地提权漏洞分析

0. 前言 CVE-2023-21752 是 2023 年开年微软第一个有 exploit 的漏洞，原本以为有利用代码会很好分析，但是结果花费了很长时间，难点主要了两个：漏洞点定位和漏洞利用代码分析，欢迎指正。 1. 漏洞简介 根据官方信息&a…
阅读更多...
【数据结构】二叉树的遍历以及基本操作

【数据结构】二叉树的遍历以及基本操作

目录 1.树形结构 1.概念 2.二叉树 2.1概念 2.2 两种特殊的二叉树 2.3二叉树的存储 2.4二叉树的基本操作 1.手动快速创建一棵简单的二叉树 2.二叉树的遍历 (递归) 3.二叉树的层序遍历 4.获取树中节点的个数 5.获取叶子节点的个数 6.获取第K层节点的个数 7.获取二叉…
阅读更多...
Python深度学习实战：人脸关键点(15点)检测pytorch实现

Python深度学习实战：人脸关键点(15点)检测pytorch实现

引言 人脸关键点检测即对人类面部若干个点位置进行检测，可以通过这些点的变化来实现许多功能，该技术可以应用到很多领域，例如捕捉人脸的关键点，然后驱动动画人物做相同的面部表情；识别人脸的面部表情，让机…
阅读更多...
线程池的讲解和实现

线程池的讲解和实现

🚀🚀🚀🚀🚀🚀🚀大家好,今天为大家带来线程池相关知识的讲解,并且实现一个线程池 🌸🌸🌸🌸🌸🌸🌸🌸…
阅读更多...
DM的学习心得和知识总结（一）|DM数据库Real Application Testing之Database Reply实操(一)

DM的学习心得和知识总结（一）|DM数据库Real Application Testing之Database Reply实操(一)

目录结构 注：提前言明 本文借鉴了以下博主、书籍或网站的内容，其列表如下： 1、达梦数据库产品及解决方案，点击前往 2、达梦技术文档，点击前往 3、武汉达梦数据库有限公司 官网首页，点击前往 1、本文内容全部…
阅读更多...
OpenFeign#1 - FeignClient 是如何注册的?

OpenFeign#1 - FeignClient 是如何注册的?

文章目录EnableFeignClientsFeignClientsRegistrarregisterDefaultConfigurationregisterFeignClientsFeignClientFeignClientFactoryBeanFeignContextfeign(FeignContext)EnableFeignClients 该注解会导致 FeignClientsRegistrar 的注入. Retention(RetentionPolicy.RUNTIME…
阅读更多...
如何用canvas制作一个华容道小游戏（乞丐版）

如何用canvas制作一个华容道小游戏（乞丐版）

我大抵是废了φ(．．) ，横竖都学不进去，上课知识不进脑子，学习光想划水摸鱼，心中仅剩的良知告诉我这样下去是铁定不行的哇，既然学不进去，何不打把游戏，既然要打游戏&#x…
阅读更多...
HTML5 Video(视频)

HTML5 Video(视频)

HTML5 Video(视频) 在本节内容中，你将了解到在HTML5中视频是如何工作的、主流浏览器支持的视频格式以及如何对网页中的视频进行控制。 很多站点都会使用到视频. HTML5 提供了展示视频的标准。 检测您的浏览器是否支持 HTML5 视频： Web站点上的视频 直…
阅读更多...
SeNet论文解读/总结

SeNet论文解读/总结

此文章为深度学习在计算机视觉领域的图片分类经典论文SeNet（Squeeze-and-Excitation Networks）论文总结。 此系列文章是非常适合深度学习领域的小白观看的图像分类经典论文。系列文章如下： AlexNet：AlexNet论文解读/总结_alexnet…
阅读更多...
在CentOS上安装Docker引擎

在CentOS上安装Docker引擎

1,先决条件#### 1-1操作系统要求1-2 卸载旧版本 2,安装方法2-1使用存储库安装设置存储库安装 Docker 引擎 本文永久更新地址: 官方地址：https://docs.docker.com/engine/install/centos/ 1,先决条件 #### 1-1操作系统要求 要安装 Docker Engine，您需要…
阅读更多...
【基础算法】链表相关题目

【基础算法】链表相关题目

系列综述： 💞目的：本系列是个人整理为了秋招算法的，整理期间苛求每个知识点，平衡理解简易度与深入程度。 🥰来源：材料主要源于代码随想录进行的，每个算法代码参考leetcode高赞回答和…
阅读更多...
官宣｜Apache Flink 1.17 发布公告

官宣｜Apache Flink 1.17 发布公告

Apache Flink PMC（项目管理委员）很高兴地宣布发布 Apache Flink 1.17.0。Apache Flink 是领先的流处理标准，流批统一的数据处理概念在越来越多的公司中得到认可。得益于我们出色的社区和优秀的贡献者，Apache Flink 在 Apache 社区…
阅读更多...
STM32F407控制微型推拉式电磁铁（通过继电器）

STM32F407控制微型推拉式电磁铁（通过继电器）

1、继电器 继电器相当于开关，单片机通过io口高低电平的控制来控制继电器的开闭。采用继电器的好处除了能够用低电压控制高电压（如32单片机控制220V的电压）外，还可以防止电流反冲，弄烧单片机。 本文采用3.3v的电磁铁&am…
阅读更多...
三、MyBatis核心配置文件详解

三、MyBatis核心配置文件详解

核心配置文件中的标签必须按照固定的顺序(有的标签可以不写，但顺序一定不能乱)： properties、settings、typeAliases、typeHandlers、objectFactory、objectWrapperFactory、reflectorFactory、plugins、environments、databaseIdProvider、mappers 一、…
阅读更多...
b01lers(php.galf)

b01lers(php.galf)

目录 前文 正文 前文 <?phpclass A{public $codeNULL;public $argsNULL;public function __construct($code,$argsNULL){$this->code$code;$this->args$args;print_r("2333") ;} public function __invoke($code,$args){echo $code;print_r("执行inv…
阅读更多...
记一次若依后台管理系统渗透

记一次若依后台管理系统渗透

前言 最近客户开始hw前的风险排查&#xff0c;让我们帮他做个渗透测试&#xff0c;只给一个单位名称。通过前期的信息收集&#xff0c;发现了这个站点&#xff1a; 没有验证码&#xff0c;再加上这个图标&#xff0c;吸引了我注意&#xff1a; 从弱口令开始 若依默认口令为ad…
阅读更多...
Android 12.0 Settings主页面去掉FocusRecyclerView相关功能

Android 12.0 Settings主页面去掉FocusRecyclerView相关功能

1.前言 在12.0的系统rom产品定制化开发中，在系统Settings主页面的主菜单中，在测试某些功能的时候，比如开启护眼模式和改变系统密度会在主菜单第一项的网络菜单头部增加 自定义您的设备和设置护眼模式时间安排 等等相关的设置模块 这对于菜单布局显示相当不美观，所以根据系…
阅读更多...
最新文章

Copyright @ 2022~2023