刷题训练营之栈与队列

文章目录

  • 前言
  • 一、用队列实现栈
    • 1.题目介绍
    • 2.思路
    • 3.代码
  • 二、用栈实现队列
    • 1.题目介绍
    • 2.思路
    • 3.代码

在这里插入图片描述

前言

本题是在栈与队列的基础上，为巩固两者而出的题，所以基本是在实现了栈与队列的基础上做的，如果没有栈与队列的基础，请看我之前的文章，数据结构之栈与队列详解

一、用队列实现栈

1.题目介绍

题目在225. 用队列实现栈
在这里插入图片描述

2.思路

1️⃣将不为空的队列的数据导入为空的队列中至数据只剩余一个在这里插入图片描述
2️⃣队列出掉4，对于栈来说，就是4出栈在这里插入图片描述
3️⃣
在这里插入图片描述
4️⃣当其中一个队列为空时，将不为空的队列的数据导入为空的队列中至数据只剩余一个
在这里插入图片描述
5️⃣重复上述操作
在这里插入图片描述

3.代码

typedef char 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* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;

}

void QueuePush(Queue* pq, QDatatype x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->Data = x;
    newnode->next=NULL;
    if (pq->size == 0)
    {
        pq->head =pq->tail= newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;

}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->size);
    if (pq->head->next==NULL)
    {
        free(pq->head);
        pq->head =pq->tail= NULL;
    }
    else
    {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

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

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

QDatatype QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->Data;
}

QDatatype QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->Data;
}

//此位置之上属于队列的实现代码，此下为题目所需完成的

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

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        while(QueueSize(&obj->q1)>1)
        {
            QDatatype front=QueueFront(&obj->q1);
            QueuePop(&obj->q1);
            QueuePush(&obj->q2,front);
        }
        QDatatype front=QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        return front;
    }
    else
    {
        while(QueueSize(&obj->q2)>1)
        {
            QDatatype front=QueueFront(&obj->q2);
            QueuePop(&obj->q2);
            QueuePush(&obj->q1,front);
        }
        QDatatype front=QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        return front;
    }
   
}

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后，发现我们不需要在来回倒腾了，当我们在想出后面的时，我们一直只需要出另外一个

那么如果我们在出一个后需要入数据呢，我们入到什么地方去呢，比如想下面这种情况，当我们出掉1和2后，我们在队列后面入1和2，那么我们在栈里面怎么入呢，因为3,和4的那个栈需要出掉其他数据，不能入，所以我们只能操作左边的栈
在这里插入图片描述
在这里插入图片描述
然后如果我们的右边的栈出完后，我们就重复上述操作
在这里插入图片描述

那么我们可以总结
1️⃣我们将一个栈只当作出数据的的，将一个栈只当入数据的(对于上图来说左边是入的，右边是出的）
2️⃣当出的栈为空时，我们就将入的栈的数据入到出的栈里面
3️⃣当出的栈不为空时，我们出数据就只向出栈出数据

3.代码

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//初始化时如果top是0，即top指向栈顶上的后一位
	ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}
void StackPush(ST* ps, STDataType x)
{
		assert(ps);
		if (ps->top == ps->capacity)
		{
			int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;
			STDataType* temp = (STDataType * )realloc(ps->a, sizeof(STDataType)*newcapacity);
			if (temp == NULL)
			{
				printf("realloc fail\n");
				exit(-1);
			}
			ps->a = temp;
			ps->capacity = newcapacity;
		}
		ps->a[ps->top] = x;
		ps->top++;

}
void StackPop(ST* ps) 
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

void StackPrint(ST* ps)
{
	while (ps->top)
	{
		printf("%d", StackTop(ps));
		StackPop(ps);
	}
}
typedef struct {
    ST st1;//入的栈
    ST st2;//出的栈
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* Queue=(MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&Queue->st1);
    StackInit(&Queue->st2);
    return Queue;
}

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

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->st2))
    {
        while(!StackEmpty(&obj->st1))
        {
            StackPush(&obj->st2,StackTop(&obj->st1));
            StackPop(&obj->st1);
        }
    }
  
    return StackTop(&obj->st2);
}

int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    StackPop(&obj->st2);
    return front;
    
}

bool myQueueEmpty(MyQueue* obj) {
    return (StackEmpty(&obj->st1)&&StackEmpty(&obj->st2));
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->st2);
    StackDestroy(&obj->st1);
    free(obj);
}

/**
 * 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);
*/

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

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

相关文章

Nginx的漏洞浮现

Nginx的漏洞浮现

本文参考https://vulhub.org/#/environments/nginx/nginx_parsing_vulnerability/环境搭建均是采用docker拉取环境请移步到参考。一、Nginx的配置错误案列1. CRLF注入漏洞配置错误文件error1.confrootubuntu-virtual-machine:/vulhub/vulhub-master/nginx/insecure-configurati…
阅读更多...
数据结构中的堆

数据结构中的堆

一、树的重要知识点 节点的度：一个节点含有的子树的个数称为该节点的度（有几个孩子）叶节点或终端节点:度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点（0个孩子）非终端节点或分支节点…
阅读更多...
css实现炫酷充电动画

css实现炫酷充电动画

先绘制一个电池&#xff0c;电池头部和电池的身体 这里其实就是两个div&#xff0c;使用z-index改变层级&#xff0c;电池的身体盖住头部&#xff0c;圆角使用border-radius完成 html部分,完整的css部分在最后 <div class"chargerBox"><div class"ch…
阅读更多...
.NET Core 实现Excel的导入导出

.NET Core 实现Excel的导入导出

.NET Core 使用NPOI实现Excel的导入导出前言NPOI简介一、安装相对应的程序包1.1、在 “管理NuGet程序包” 中的浏览搜索&#xff1a;“NPOI”二、新建Excel帮助类三、调用3.1、增加一个“keywords”模型类&#xff0c;用作导出3.2、添加一个控制器3.3、编写导入导出的控制器代码…
阅读更多...
一本通 3.2.1 队列的基本应用

一本通 3.2.1 队列的基本应用

1332&#xff1a;【例2-1】周末舞会 【题目描述】 假设在周末舞会上&#xff0c;男士们和女士们进入舞厅时&#xff0c;各自排成一队。跳舞开始时&#xff0c;依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同&#xff0c;则较长…
阅读更多...
【数据结构】树和二叉树的介绍

【数据结构】树和二叉树的介绍

文章目录前言一、树1.1 树的概念1.2 树的相关概念1.3 树的表示1.4 树的用途二、二叉树2.1 二叉树的概念2.2 两种特殊的二叉树2.3 二叉树的性质2.4 二叉树的存储方式总结前言 树是一种让程序员们既爱又恨的数据结构。它就像是一棵大树&#xff0c;让你可以轻松地摘取其中的果实…
阅读更多...
【10】核心易中期刊推荐——模式识别与机器学习

【10】核心易中期刊推荐——模式识别与机器学习

🚀🚀🚀NEW！！！核心易中期刊推荐栏目来啦 ~ 📚🍀 核心期刊在国内的应用范围非常广，核心期刊发表论文是国内很多作者晋升的硬性要求，并且在国内属于顶尖论文发表，具有很高的学术价值。在中文核心目录体系中，权威代表有CSSCI、CSCD和北大核心。其中，中文期刊的数…
阅读更多...
【C++进阶】C++11(中)左值引用和右值引用

【C++进阶】C++11(中)左值引用和右值引用

文章目录左值引用左值引用的概念左值引用的使用右值引用右值引用的概念右值引用的使用左右值相互引用左值引用对右值进行引用右值引用对左值进行引用右值引用使用场景和意义左值引用的优势左值引用的短板右值引用的优势完美转发模板万能引用完美转发实际运用场景左值引用 左值…
阅读更多...
vue3+ts 开发效率提升

vue3+ts 开发效率提升

1、vite pnpm项目初始化 pnpm&#xff1a; 比npm或yarn快10倍 pnpm与其他包管理器&#xff08;如npm和Yarn&#xff09;的不同之处在于它使用一种称为“硬链接”的独特安装方法。当你使用PNPM安装一个包时&#xff0c;它并不会将包的文件复制到每个项目的node_modules目录中&a…
阅读更多...
图形视图界面 图形效果

图形视图界面 图形效果

Qt的标准图形效果类&#xff1a; QGraphicsBlurEffect提供模糊效果QGraphicsColorizeEffect提供染色效果QGraphicsDropShadowEffect提供阴影效果QGraphicsOpacityEffect提供透明效果 QGraphicsBlurEffect&#xff08;模糊效果&#xff09; 模糊效果会模糊源。此效果对于减少细…
阅读更多...
VS Code工作区用法

VS Code工作区用法

背景VS Code可以通过"文件/打开文件夹"来打开本地项目&#xff0c;但是想要打开多个项目便需要来回切换&#xff0c;比较费劲。此时就可以使用工作区功能&#xff0c;将不同的项目放置到同一个工作区中&#xff0c;这样切换项目的时候就会非常方便。操作方法打开其中…
阅读更多...
免费搭建个人博客

免费搭建个人博客

免费搭建个人博客,并发布到公网 利用hexo搭建个人博客&#xff0c;通过gitee的pages发布到公网 1 前置准备 安装git、安装node.js&#xff08;尽量选择长期支持的版本) node.js官网&#xff1a;https://nodejs.org/en/ git官网&#xff1a;https://git-scm.com/book/zh/v2 安装…
阅读更多...
如何衡量你的Facebook广告活动的成功

如何衡量你的Facebook广告活动的成功

投入大量资金和资源在Facebook广告上并不总能带来预期的回报&#xff0c;这很可能是由于缺乏恰当的衡量广告活动成功的方法。在这篇文章中&#xff0c;我们将介绍一些关键的指标&#xff0c;帮助你更好地了解如何衡量你的Facebook广告活动的成功。1.费用每次点击&#xff08;CP…
阅读更多...
Spring和IDEA都不推荐用的@Autowired注解，为什么还有那么多人用？

Spring和IDEA都不推荐用的@Autowired注解，为什么还有那么多人用？

Autowired的默认装配 我们都知道在spring中Autowired注解&#xff0c;是用来自动装配对象的。通常&#xff0c;我们在项目中是这样用的&#xff1a; package com.sue.cache.service;import org.springframework.stereotype.Service;Service public class TestService1 {publ…
阅读更多...
你是否了解AR技术？AR技术就在我们身边

你是否了解AR技术？AR技术就在我们身边

文章目录专栏导读1、前言2、AR技术原理3、游戏领域应用4、教育领域应用5、医疗领域应用6、零售领域应用专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN Python领域新星创作者&#xff0c;专注于分享python领域知识。 ✍ 本文录入于《数据分析之道》&#xff0c;本专栏…
阅读更多...
C/C++每日一练(20230325)

C/C++每日一练(20230325)

目录 1. 搜索插入位置 &#x1f31f; 2. 结合两个字符串 &#x1f31f; 3. 同构字符串 &#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 搜索插入位置 给定一个排序数…
阅读更多...
CAN通信----电路图

CAN通信----电路图

CAN通信----基本原理 一、CAN总线网络连接 1.闭环总线网络----ISO11898 闭环总线网络高速、短距离&#xff0c;它的总线最大长度为 40m&#xff0c;通信速度最高为 1Mbps&#xff0c;总线的两端各要求有一个120 欧的电阻。 2.开环总线网络----ISO11519 开环总线网络低速、…
阅读更多...
LeetCode394.字符串解码

LeetCode394.字符串解码

LeetCode刷题记录 文章目录&#x1f4dc;题目描述&#x1f4a1;解题思路⌨C代码&#x1f4dc;题目描述 给定一个经过编码的字符串&#xff0c;返回它解码后的字符串。 编码规则为: k[encoded_string]&#xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保…
阅读更多...
1652_MIT 6.828 shell例程重定向的实现分析

1652_MIT 6.828 shell例程重定向的实现分析

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 前面完成了一个单独命令执行之后&#xff0c;想放弃这个简单shell的实现。后来想想多少还是有几分不甘心&#xff0c;还是耐着心思把这个做完吧&#xff01; 这次&…
阅读更多...
基于pytorch+Resnet101加GPT搭建AI玩王者荣耀

基于pytorch+Resnet101加GPT搭建AI玩王者荣耀

本源码模型主要用了SamLynnEvans Transformer 的源码的解码部分。以及pytorch自带的预训练模型"resnet101-5d3b4d8f.pth"本资源整理自网络&#xff0c;源地址&#xff1a;https://github.com/FengQuanLi/ResnetGPT注意运行本代码需要注意以下几点 注意&#xff01;&a…
阅读更多...
最新文章

Copyright @ 2022~2023