☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼

准备好了么

目录:

一·用两个队列实现栈:

1·思路: 

2·画图理解:

3·代码解答: 

二·用两个栈实现队列:

 1·思路:

  2·画图理解:

3·代码解答:

三·设计循环队列: 

1·思路: 

2·画图理解:

3·代码解答:


一·用两个队列实现栈:

源:oj链接:. - 力扣(LeetCode)​​​​​​

1·思路: 

我们首先调用创建好的队列代码,然后假设令这两个队列作为一个栈,由于我们画图可以得出一个结论:

①当有两个空队列的时候,我们push时随便push,一直往不为空的队列里面push。

②当我们要移除并返回栈顶元素的时候,我们要把不为空的队列里n-1个元素push到另一个空的队列里面,最后得到将要pop与return的元素。

③只返回栈顶元素只需要返回不为空队列的尾指针指向的元素即可。

④判空的话,就是两个队列都为空才行。

2·画图理解:

3·代码解答: 

typedef int qdatatype;
typedef struct Qnode {
	struct Qnode* next;
	qdatatype data;
}Qnode;
typedef struct queue {
	int size;
	Qnode* head;
	Qnode* tail;
}queue;

void Queueinit(queue* p) {
	assert(p);

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


void Queuedestroy(queue* p) {
	assert(p);
	Qnode* cur = p->head;
	while (cur) {
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	p->size = 0;
	p->tail = p->head = NULL;
}


void Queuebackpush(queue* p, qdatatype x) {
	assert(p);
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	if (newnode == NULL) {
		perror(malloc);
		return;
	}
	newnode->next = NULL;
	newnode->data = x;
	if (p->tail == NULL) {
		p->head = p->tail = newnode;
	}
	else {
		p->tail->next = newnode;
		p->tail = newnode;
	}
	p->size++;


}

void Queuefrontpop(queue* p) {
	assert(p);
	assert(p->size > 0);
	if (p->head->next == NULL) {
		free(p->head);
		p->head = p->tail = NULL;
	}
	else {
		Qnode* next = p->head->next;
		free(p->head);
		p->head = next;
	}
	p->size--;
}


qdatatype Queuefrontdata(queue* p) {
	assert(p);
	assert(p->size > 0);
	return p->head->data;
}


qdatatype Queuebackdata(queue* p) {
	assert(p);
	assert(p->size > 0);
	return p->tail->data;
}


int Queuesize(queue* p) {
	assert(p);
	return p->size;
}


bool QueueEmpty(queue* p) {
	assert(p);
	return p->size == 0;
}


//以上是引用的队列的创建

typedef struct {
    queue p1;
    queue p2;

} MyStack;//这里定义了一个结构体类型:我的栈:里面放了两个队列结构体类型的变量


MyStack* myStackCreate() {
    MyStack*pst=(MyStack*)malloc(sizeof(MyStack));
     Queueinit(&(pst->p1));
     Queueinit(&(pst->p2));
     return pst;

}//在这里将MyStack结构体里面的两个队列初始化,并得到MyStack类型的指针

void myStackPush(MyStack* obj, int x) {
   if( !QueueEmpty(&(obj->p1))){
    Queuebackpush(&(obj->p1),x);
   }
   else{
    Queuebackpush(&(obj->p2),x);

   }

//这里我们在两个队列里面插入数据,故由于让看起来像栈的形式,我们就找有数据的队列插入新的数据即
//找不为空的队列插入


}

int myStackPop(MyStack* obj) {
    //这里我们用假设法来得到空与非空队列
    queue*empty=&(obj->p1);
    queue*noempty=&(obj->p2);
    if(!QueueEmpty(&(obj->p1))){
        //如果假设不成立执行下面
        noempty=&(obj->p1);
        empty=&(obj->p2);
    }
    //以上操作我们就可以得到noempty empty 分别为空与非空的队列
    while( Queuesize(noempty)>1){
        Queuebackpush(empty,Queuefrontdata(noempty));
        Queuefrontpop(noempty);
    }
    //下面防止找不到要得到的栈顶元素,我们在pop之前要先保存一下
    int data=Queuefrontdata(noempty);
    Queuefrontpop(noempty);
    return data;

}//首先我们要找到空的队列,然后把非空队列获得头部元素进行插到原来空的队列里,插入n-1个

int myStackTop(MyStack* obj) {
    if( !QueueEmpty(&(obj->p1))){
    return Queuebackdata(&(obj->p1));
   
   }
   else{
    return Queuebackdata(&(obj->p2));
    

   }
   //这里返回栈顶元素即就是我们不为空的队列的队尾元素

    
}

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&(obj->p1))&&QueueEmpty(&(obj->p2));
}

void myStackFree(MyStack* obj) {
     Queuedestroy(&(obj->p1));
     Queuedestroy(&(obj->p2));
     free(obj);
     obj=NULL;
//这里由于我们在 MyStack里开辟了两个队列的链表类型空间故需要先释放掉,
//再释放obj

}

测试: 

​
int main()
{
    MyStack* st = myStackCreate();
    myStackPush(st, 1);
    myStackPush(st, 2);

    int ret = myStackTop(st);

    printf("%d",ret);
    mystackFree(st);
    return 0;
}

​

二·用两个栈实现队列:   

源:oj链接:. - 力扣(LeetCode)​​​​​​

 1·思路:

这里首先建立两个栈作为MyQueue,大致思路和两个队列实现栈相差不大,这里只不过是调用的事先创建的队列改成栈了,此外再删去元素的时候会多排序一次。

①push:还是找空的栈然后,依次入栈

②pop:类似于上面的实现,但是当我们把n-1个元素放到另一个空栈里面顺序与原来是相反的故需要颠倒一下,此时就要再入一次栈入到原栈里,(先保存再返回,再删除)。

③peek:由于我每次使用函数的时候,这两个栈必然有一个空有一个非空,只需要返回非空栈的下标为0的元素即可。

④empty:这里判空也是两个均为空。

  2·画图理解:

3·代码解答:

typedef int typedata;
typedef struct stack {
	typedata* a;
	int top;
	int capacity;
 } ST;

void STinit(ST* p) {
	assert(p);
	p->a = NULL;
	p->capacity = p->top = 0;
}
void STpush(ST* p,typedata x) {
	assert(p);
	//扩容
	if (p->top == p->capacity) {
		int newcapacity = p->capacity == 0 ? 4 : (p->capacity) * 2;
		typedata* tmp = (typedata*)realloc(p->a, sizeof(typedata)*newcapacity);
		if (tmp == NULL) {
			perror("realloc");
			return;
		}
		p->a = tmp;
		p->capacity = newcapacity;

	}
	p->a[p->top] = x;
	p->top++;
}
void STpop(ST* p) {
	assert(p);
	assert(p->top);
	p->top--;


}

typedata STTop(ST* p) {
	assert(p);
	assert(p->top);
	return p->a[p->top - 1];

}
bool STempty(ST* p) {
	assert(p);
	return p->top == 0;
}
int STsize(ST* p) {
	assert(p);
	return p->top;
}
void STdestroy(ST* p) {
	assert(p);
	free(p->a);
	p->a = NULL;
	p->capacity = p->top = 0;
}

//以上是对栈的实现

typedef struct {
    ST s1;
    ST s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* q=(MyQueue* )malloc(sizeof(MyQueue));
    STinit(&(q->s1));
    STinit(&(q->s2));
    return q;
//在MyQueue内开辟两个栈的空间

}

void myQueuePush(MyQueue* obj, int x) {
    if(!STempty(&(obj->s1))){
        STpush(&(obj->s1),x);
    }
    else{
        STpush(&(obj->s2),x);
         
    }//这里也是找到非空栈进行插入数据
}

int myQueuePop(MyQueue* obj) {
    ST*empty=&(obj->s1);
    ST*noempty=&(obj->s2);
    if(!STempty(&(obj->s1))){
        noempty=&(obj->s1);
        empty=&(obj->s2);
    }
    //通过假设法得到真实的非空与空的栈
    while(STsize(noempty)>1){
        STpush(empty,STTop(noempty));
         STpop(noempty);
        
    }
    //首先第一个循环是得到n-1个数据到原来空的栈里面,但是顺序是反的

    int data=STTop(noempty);
    STpop(noempty);
    //在这里保存队列即栈的第一个元素,并把它pop
    while(STsize(empty)>0){
         STpush(noempty,STTop(empty));
         STpop(empty);

    }
    //通过再一个循环把它重新插入到原来的栈里,顺序恢复

    return data;

}

int myQueuePeek(MyQueue* obj) {
    if(!STempty(&(obj->s1))){
       return obj->s1.a[0];
    }
    else{
        return  obj->s2.a[0];
    }
}
//直接返回栈的首元素即队首元素
bool myQueueEmpty(MyQueue* obj) {
    return STempty(&(obj->s1))&&STempty(&(obj->s2));
}

void myQueueFree(MyQueue* obj) {
    STdestroy(&(obj->s1));
    STdestroy(&(obj->s2));
    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);
*/

 测试:

int main() {
    MyQueue* m = myQueueCreate();
    myQueuePush(m, 1);
    myQueuePush(m, 2);
    myQueuePush(m, 3);
    int ret = myQueuePop(m);
    printf("%d ", ret);
    int n=myQueuePeek(m);
    printf("%d ", n);


    return 0;
}

三·设计循环队列:
 

 

源:oj链接:. - 力扣(LeetCode)​​​​​​

1·思路: 

设计循环队列,首先把它设计成一个数组的形式来循环利用,这里会涉及到判空与判满如何进行,

那么我们有两种方法解决,一个是进出队列用size记录,一个是额外多开辟一个空间,,我们选择用后者。比如设置长度为k,那么就要开辟k+1个空间。而多出来的空间我们不放数据用tail指向这个空的空间。(下面的head与tail实则是下标,把它假想为指针)

 ①MyCircularQueue:创建一个结构体存放队列要开辟的长度k,头尾指针以及int类型的指针a。

②myCircularQueueFront:找头,可以直接对a[head]去访问。

③myCircularQueueRear:访问尾指针前一个数据的话由于可能会存在tail为0,那么上一个就是-1,明显是不可能的,故需要转化,可以把它tail-1直接变成k,也可以tail-1后+(k+1)%(k+1).

④myCircularQueueEnQueue:插入数据先判是否full,没有的话,就放入tail++,而可能存在为k+1.那么就把它变为0,或者直接(++tail)%(k+1)。

⑤ myCircularQueueDeQueue:这里我们画图可以发现删除数据只需要head++,而tail不用变化,但是head++,当过界时候把它变为0。

⑥myCircularQueueIsEmpty:头尾指针指向同一个处,即head==tail。

⑦myCircularQueueIsFull:画图可以知道每每当填满数据的时候tail+1==head(不包括越界改变的情况),故我们还是可以在tail到k+1,把它变为0,看是否与head相同,也可以(tail+1)%(k+1)看是否==head。

2·画图理解:

3·代码解答:


typedef struct {
    int head;
    int tail;
    int k;//要开辟的队列长度
     int *a;

} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    if(k<0){
        return NULL;
    }
    MyCircularQueue*q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int *m=(int*)malloc(sizeof(int)*(k+1));
    q->head=q->tail=0;
    q->a=m;
    q->k = k;//将结构体里的k初始化为队列长度k
    return q;


}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);//这里由于提前调用未定义的函数故需要在前面声明

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)){
        return false;
    }
    else{
        // obj->a[obj->tail]=value;
        // obj->tail++;
        //  if(obj->tail==obj->k+1){
        // obj->tail=0;//这里有一个情况当tail+1到达数组超过数组最大额度就变为0
         obj->a[obj->tail]=value;
         obj->tail++;
         obj->tail%=obj->k+1;//这里取模可以简化上面的判断
    

   

  }
  return true;
}


bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->head++;
    // obj->a[obj->tail++];
    // if(obj->tail==obj->k+1){
    //     obj->tail=0;
    // }
     if(obj->head==obj->k+1){
        obj->head=0;
    }
    return true;
    //这里我们要删出队列的第一个元素,那么只需要head++(这里也要考虑越界变0),然后tail不变即可




}

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

int myCircularQueueRear(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
//     if(obj->tail==0){
//      return obj->a[obj->k];
//     }
//   else{
//     return obj->a[obj->tail-1];
//   }
  //这里是返回tail的上一个数据,故可能会出现tail为零那么tail-1=-1;实际为k
  //简化:
  
    return obj->a[(obj->tail-1+(obj->k+1))%(obj->k+1)];
  
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
     if(obj->head==obj->tail){
        return true;
    }
    else{
        return false; 
    }
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    // if(obj->tail==obj->k&&obj->head==0){
    //     return true;
    // }
    // if(obj->tail+1==obj->head){
    //     return true;
    // }
    
    //     return false;
    /*这里判断是否满,我们画图可以得到在多开辟一个空间的时候,每当tail+1=head就满了,考虑到可能tail
    +1为-1,故进行了讨论判断*/

    //简化:
    return (obj->tail+1)%(obj->k+1)==obj->head;
    //%(k+1)可以将越界的下标变成-1
}

void myCircularQueueFree(MyCircularQueue* obj) {
   free(obj->a);
   obj->a=NULL;
   free(obj);
   obj=NULL;//先释放掉开辟的数组空间内存,再把结构体的空间释放,指针置空
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

测试:

int main() {
    MyCircularQueue* m = myCircularQueueCreate(3);
    myCircularQueueEnQueue(m, 1);
    myCircularQueueEnQueue(m, 2);
    myCircularQueueEnQueue(m, 3);
    myCircularQueueEnQueue(m, 4);
    printf("%d ", myCircularQueueRear(m));
    myCircularQueueIsFull(m);
    myCircularQueueDeQueue(m);
    myCircularQueueEnQueue(m, 4);
    printf("%d ", myCircularQueueRear(m));
    myCircularQueueFree(m);



    return 0;
}

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

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

相关文章

MySQL5.7压缩包安装图文教程

一、下载 https://dev.mysql.com/downloads/mysql/ 选择5.7版本 二、解压 下载完成后解压&#xff0c;解压后如下&#xff08;zip是免安装的&#xff0c;解压后配置成功即可使用&#xff09; 注意&#xff1a;只有5.6以前的版本才有在线安装&#xff08;install msi&#xf…

网页如何集成各社区征文活动

Helllo , 我是小恒 由于我需要腾讯云社区&#xff0c;稀土掘金以及CSDN的征文活动RSS&#xff0c;找了一下没发现&#xff0c;所以使用GET 请求接口对网页定时进行拉取清洗&#xff0c;甚至无意间做了一个简单的json格式API 最终网址:hub.liheng.work API:http://hub.liheng.wo…

李廉洋:5.13黄金原油美盘行情分析,必看策略。

黄金消息面分析&#xff1a;机构最新调查中的一些受访者表示&#xff0c;美国最大的科技股不仅是对创新行业的押注&#xff0c;而且可能是对冲通胀的工具。46%的受访者表示&#xff0c;数十年来一直是避险之选的黄金仍被视为抵御价格上涨风险的最佳保障。但近三分之一的人表示&…

前端开发者必备:Nginx入门实战宝典,从部署到优化一网打尽

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 引言 &#x1f44b;一、Nginx简介 &#x1f4da;二、常见的Web服务器架构 &#x1f300;&#x1f4cc; 架构概述&#x1f4cc; Nginx的深入探讨 三、正向代理与反向代理 &#x1f52e;&#x1f4cc; 正向代理工作原理&#…

深度解读《深度探索C++对象模型》之虚继承的实现分析和效率评测(一)

目录 前言 具有虚基类的对象的构造过程 通过子类的对象存取虚基类成员的实现分析 接下来我将持续更新“深度解读《深度探索C对象模型》”系列&#xff0c;敬请期待&#xff0c;欢迎左下角点击关注&#xff01;也可以关注公众号&#xff1a;iShare爱分享&#xff0c;或文章末…

docker端口映射成功,docker端口不生效的问题解决,外界无法访问docker映射端口

docker端口映射不生效的问题解决 问题 使用docker run -p 88848:8848后&#xff0c;显示容器启动正常&#xff0c;并且使用docker logs –f xxx能够看到容器可以正常启用&#xff0c;docker ps 可以看到容器启动成功&#xff0c;并且端口已经映射,但是在浏览器访问相关地址&am…

字符串函数(一):strcpy(拷贝),strcat(追加),strcmp(比较),及strncpy,strncat,strncmp

字符串函数 一.strcpy&#xff08;字符串拷贝&#xff09;1.函数使用2.模拟实现 二.strcat&#xff08;字符串追加&#xff09;1.函数使用2.模拟实现 三.strcmp&#xff08;字符串比较&#xff09;1.函数使用2.模拟实现 四.strncpy1.函数使用2.模拟实现 五.strncat1.函数使用2.…

调剂”小清华“、不保护一志愿?——兰州大学25计算机考研考情分析

兰州大学&#xff08;Lanzhou University&#xff09;&#xff0c;简称“兰大”&#xff0c;是中华人民共和国教育部直属 全国重点大学&#xff0c;中央直管副部级建制&#xff0c;位列国家首批“双一流(A 类)”、“211 工 程”、“985 工程”大学行列&#xff0c;入选国家“珠…

电机及FOC算法介绍

一.电机概述 1.电机的简介 电机是一种可以在电能和机械能的之间相互转换的设备&#xff0c;其中发电机是将机械能转换为电能&#xff0c;电动机是将电能转换为机械能。发电机的主要用于产生电能&#xff0c;用途单一&#xff0c;但是电动机主要用于产生机械能&#xff0c;用途…

外卖 点金推广实战课程,2024外卖 点金推广全流程(7节课+资料)

课程内容&#xff1a; 外卖点金推广实操课程 资料 01 1-了解外卖.mp4 02 第一节:点金推广的说明.mp4 03 第二节:如何降低点金推广的成本,mp4 04 第三节:如何计算点金推广的流速,mp4 05 第四节:如何提升点金的精准度,mp4 06 第五节:点金推广实操,mp4 07 点金推广高级教程…

几种IO模型

部分图来自网络和黑马程序员 IO IO分为两个阶段&#xff1a;数据准备&#xff08;数据读取到内核缓冲区&#xff09;数据拷贝&#xff08;从内核缓冲区拷贝到用户空间&#xff09; 例如&#xff0c;在下图中两个主机的通信中&#xff0c;程序A/B从TCP接收缓冲区读取数据时&am…

Vue3实战笔记(13)—pinia安装笔记

文章目录 前言安装和配置pinia总结 前言 Pinia 是 Vue 的专属状态管理库&#xff0c;它允许你跨组件或页面共享状态。 Pinia是一个轻量级的状态管理库&#xff0c;它专注于提供一个简单的API来管理应用程序的状态。相比之下&#xff0c;Vuex是一个更完整的状态管理库&#xf…

视频模糊变清晰,这13个工具总有一个能帮到你,收藏好

1、Topaz Video Enhance AI 这是一款非常专业的视频分辨率放大软件&#xff0c;使用来自多个帧的信息来实现视频升级、去噪、去隔行扫描和恢复的结果。 Topaz Video Enhance AI可以将视频放大和增强8K分辨率的镜头&#xff0c;并提供真实的细节和动作一致性。它采用AI技术实现…

【STM32HAL库】DAC输出0-3.3v

一、简要介绍一下DAC DAC也有分辨率&#xff0c;转换时间&#xff0c;精度等 分辨率常见为8或12位的 转换时间F1&#xff0c;F4,F7都是3us左右&#xff0c;而H7系列是1.7us 1.DAC框图 2.数据格式&#xff08;对齐方式&#xff09; 3.触发源 4.可以发送DMA请求 注意&#xff…

OSS证书自动续签,一分钟轻松搞定,解决阿里云SSL免费证书每3个月失效问题

文章目录 一、&#x1f525;httpsok-v1.11.0支持OSS证书自动部署介绍支持特点 二、废话不多说上教程&#xff1a;1、场景2、实战Stage 1&#xff1a;ssh登录阿里云 ECSStage 2&#xff1a;进入nginx &#xff08;docker&#xff09;容器Stage 3&#xff1a;执行如下指令Stage 3…

vivado Virtex UltraScale 配置存储器器件

Virtex UltraScale 配置存储器器件 下表所示闪存器件支持通过 Vivado 软件对 Virtex UltraScale ™ 器件执行擦除、空白检查、编程和验证等配置操作。 本附录中的表格所列赛灵思系列非易失性存储器将不断保持更新 &#xff0c; 并支持通过 Vivado 软件对其中所列非易失…

Flink HA模式下JobManager切换时发送告警

资源&版本信息 Flink版本1.14.6 运行平台&#xff1a;K8s HA使用ZK&#xff08;使用K8s的ETC应该是一个道理&#xff09; 详解Flink HA原理 Flink启动时会创建HighAvailabilityServices提供HA和相关基础服务&#xff0c;其中包括leaderRetrievalService和LeaderElecti…

MP4视频转gif怎么做?看看这篇就会了

喜欢刷短视频的小伙伴经常会看到各种好玩有趣的片段&#xff0c;想要通过自己将这段视频制作成gif动态图片的还不想下载软件的时候要怎么办呢&#xff1f;这个很简单&#xff0c;不需要下载什么软件用专业的Gif动画制作网站&#xff0c;支持超清的画质导出&#xff0c;能够完成…

ssm123基于java web的网上书城系统的设计与实现+vue

基于java web的网上书城系统的设计与实现vue 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;商品交易当然也不能排除在外&#xff0c;随着商品交易管理的不断成熟&#xff0c;它彻底改变了…

Git详解之六:Git工具

现在&#xff0c;你已经学习了管理或者维护 Git 仓库&#xff0c;实现代码控制所需的大多数日常命令和工作流程。你已经完成了跟踪和提交文件的基本任务&#xff0c;并且发挥了暂存区和轻量级的特性分支及合并的威力。 接下来你将领略到一些 Git 可以实现的非常强大的功能&…