数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）

目录

用队列实现栈

题目描述 

题目示例 

核心思路 

解题过程

定义结构体

创建栈结构体函数

入栈函数

出栈函数 

取栈顶数据函数 

判断栈是否为空函数

销毁栈函数

完整题解（C语言）

用栈实现队列 

题目描述 

题目示例

核心思路 

完整题解

用队列实现栈

题目来源：力扣

题目描述 

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

实现 MyStack 类：

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

题目示例 

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

核心思路 

1.入数据时，往不为空的队列入，保持另一个队列为空。

2.出数据时，依次出队头的数据，转移到另一个队列保存。直到剩下最后一个数据，用来出数据，则实现了栈的先进后出。

用C语言来解决这道题之前，应该先把队列的结构完成了。 

解题过程

定义结构体

用队列实现栈，先定义一下这个栈的结构体类型。 题目中定义的是匿名结构体，这个栈的结构体包括了两个队列的结构体。（属于嵌套定义） 

typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;

创建栈结构体函数

这里的创建栈结构体的函数，是指调用这个函数之后，创建一个我们栈的结构体，再将这个结构体的地址返回。 但是它在函数内部，出了这个函数就会被销毁，要解决这个问题有两种方式：一是使用全局变量，二是申请空间。为了避免全局变量带来的一些问题，我们就用申请空间的方式来实现。 要注意的一点是：对这个结构体进行初始化时，要深入到它内部的两个队列结构体中，分别对两个队列进行初始化。 最终返回我们栈结构体的地址。

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

入栈函数

按照之前的核心思路，将数据入到为空的队列中去，如果两个都为空则入到任意一个队列。

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

出栈函数 

实现出栈函数，需要先将有数据的一方队列转移到空的另一方队列，保留最后一个数据。那么就要先判断哪一个队列为空，使用假设法：先假设q1为空，q2不为空，且创建两个变量记录下来，类似emptyQ和nonemptyQ；然后调用函数确认q1是否为空，为空则不变，不为空则交换q1和q2。 确认哪一方的队列为空之后，就可以对nonemptyQ(不为空的队列)进行数据转移了。

int myStackPop(MyStack* obj) 
{
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }

    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ)); 
        QueuePop(nonemptyQ);       
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);

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

销毁栈函数

销毁栈不能只free掉栈结构体的空间，栈结构里面还有两个队列结构，而队列里面有指针指向链式结构。只free掉栈结构体时，会发生内存泄漏，即队列里面指向链式结构的指针没得到释放。所以我们应该由内到外，先把两个队列free掉，最后再free掉栈。

void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

完整题解（C语言）

typedef int QDataType;

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

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;

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

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

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

int QueueSize(Queue* pq)
{
	assert(pq);

	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}
typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;


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

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

int myStackPop(MyStack* obj) 
{
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }

    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ)); 
        QueuePop(nonemptyQ);       
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);

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

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

用栈实现队列 

题目来源：力扣

题目描述 

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

实现 MyQueue 类：

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

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

题目示例

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

核心思路 

与上一道题本质上是没有区别的，所以就只写一下核心思路

要用两个栈来实现队列： 入数据时，入到其中的一个栈中。（设此栈为PushStack） 出数据时，将有数据的栈转移到另一个栈，这样就把数据倒过来了，这时直接出这个栈的数据就实现了先进先出了（设此栈为PopStack）

完整题解（C语言）

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; //或者ps->top = -1;
	ps->capacity = 0;
}


void StackPrint(ST* ps)
{
	assert(ps);

	for (int i = 0; i < ps->top; i++)
	{
		printf("%d\t", ps->a[i]);
	}
	printf("\n");
}
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//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* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

STDataType StackTop(ST* ps)//取出栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)//计算栈中有多少个元素
{
	assert(ps);
	return ps->top;
}

typedef struct
{
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate()
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);

    return q;
}

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

int myQueuePop(MyQueue* obj)
{
    //如果popST中没有数据，将pushST的数据传递过去
    //popST中的数据就可以符合先进先出的顺序了
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }        
    }
    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}

int myQueuePeek(MyQueue* obj)
{
    //如果popST中没有数据，将pushST的数据传递过去
    //popST中的数据就符合先进先出的顺序
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);

}

void myQueueFree(MyQueue* obj)
{
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    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);
*/

end

学习自：比特徐靖杭——数据结构与算法课程

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

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

相关文章

计算机网络管理 ARP 地址解析协议 ARP的基础原理 Wireshark ARP 报文分析 ARP的通信过程

计算机网络管理 ARP 地址解析协议 ARP的基础原理 Wireshark ARP 报文分析 ARP的通信过程

⬜⬜⬜ ---&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; (*^▽^*)欢迎光临 &#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea;---⬜⬜⬜ ✏️write in front✏️ &#x1f4dd;个人主页&#xff1a;陈丹宇jmu &#x1f381;欢迎各位→…
阅读更多...
GPT4和ChatGPT的区别，太让人震撼

GPT4和ChatGPT的区别，太让人震撼

文 | Serendipity知乎 前言 GPT4上午朋友圈已经刷屏啦&#xff0c;不过我还在忙&#xff0c;刚刚才登上 GPT-4 &#xff0c;现在来体验一下~ 附 GPT-4 能力测试站&#xff08;无需魔法&#xff0c;仅供国内研究测试&#xff09;&#xff1a; https://gpt4test.com 附 Cha…
阅读更多...
解决代码重复的优化方案

解决代码重复的优化方案

上周公司组织培训Spring 基于注解的数据校验方案&#xff0c;可以节省很大工作量&#xff0c;其实&#xff0c;除了数据校验&#xff0c;还有很多其他方案&#xff0c;可以大幅提高代码的整洁性。如&#xff1a;设计模式、OOP 思想、反射、泛型等等&#xff0c;框架往往需要以同…
阅读更多...
强化学习下的多教师知识蒸馏模型（学习笔记

强化学习下的多教师知识蒸馏模型（学习笔记

对知识蒸馏的方法提出了一个新的方向 采用多个不同的教师模型同时训练一个学生模型 一个很明显的好处 就是 多个教师model可以减少单个教师模型它的bias 但是当我们有多个老师的时候&#xff0c; 学生模型是否能够根据自己的能力选择和结合教师模型的特点 来选择性的向老师…
阅读更多...
Maven依赖管理

Maven依赖管理

文章目录一、mvn依赖的特性1. 依赖的范围2. 依赖的传递3. 依赖的排除二、mvn中的继承和聚合1. 聚合2. 继承3. Demo1、首先创建一个父工程并且修改它的打包方式为 pom2、创建子模块工程3、依赖管理三、企业级知识扩展1. 属性2. 版本管理3. 资源配置4. 多环境开发配置Maven工程约…
阅读更多...
SWAT模型（高阶）

SWAT模型（高阶）

SWAT模型高阶十七项案例分析实践应用 导师&#xff1a;刘老师【副教授】&#xff1a;来自国内双一流高校&#xff0c;长期从事数字流域建模、流域水土过程模拟、遥感及GIS技术应用等领域工作&#xff0c;发表多篇SCI论文暨完成多项科研项目&#xff0c;具有资深的技术底蕴和专…
阅读更多...
Python 01 初识python

Python 01 初识python

目录 一、编程是怎么来到我们这个世界的&#xff1f; 二、Python的由来&#xff1f; 三、什么是python&#xff1f; 3.1面向对象和面向过程 3.1.1面向对象 3.1.2 面向过程 3.2解释性 3.2.1 编译性 3.2.2 解释性 3.3交互式 四、Python3和Python2 五、python和其他…
阅读更多...
基于LiFePO4和硅/还原氧化石墨烯纳米复合材料的锂离子电池

基于LiFePO4和硅/还原氧化石墨烯纳米复合材料的锂离子电池

A lithium-ion battery based on LiFePO4 and silicon/reduced graphene oxide nanocomposite highlights&#xff1a; 硅纳米颗粒(nSi)和还原氧化石墨烯(RGO)作为阳极&#xff1b;微波辐射&#xff0c;对混合物进行热处理&#xff0c;合成nSi/RGO复合物&#xff1b;通过不同充…
阅读更多...
Jsoup使用教程以及使用案例

Jsoup使用教程以及使用案例

文章目录1&#xff1a;什么是Jsoup1&#xff1a;Jsoup概述2&#xff1a;Jsoup能做什么2&#xff1a;Jsoup相关概念3&#xff1a;获取文档1&#xff1a;导入jsoup的jar包2&#xff1a;从URL中加载文档对象&#xff08;常用&#xff09;3&#xff1a;从本地文件中加载文档对象4&a…
阅读更多...
2023 海外工具站 3 月复盘

2023 海外工具站 3 月复盘

3 月的碎碎念&#xff0c;大致总结了商业人生、付费软件、创业方向选择、创业感性还是理性、如何解决复杂问题及如何成长这几个方面的内容。 商业人生 商业人生需要试错能力和快速信息收集与验证校准&#xff1b; 商业逻辑需要试错能力&#xff0c;收集各种渠道信息后整理决…
阅读更多...
手把手教你一步一步暴力破解密码，学不会来找我

手把手教你一步一步暴力破解密码，学不会来找我

目录 一、什么是暴力破解&#xff1f; 二、暴力破解弱口令实验 三、如何防御暴力破解攻击&#xff1f; 一、什么是暴力破解&#xff1f; 暴力破解也可称为穷举法、枚举法&#xff0c;是一种针对于密码的破译方法&#xff0c;将密码进行逐个推算直到找出真正的密码为止。设置长而…
阅读更多...
[学习笔记] 3. C++ / CPP提高

[学习笔记] 3. C++ / CPP提高

本阶段主要针对C泛型编程和STL技术做详细讲解&#xff0c;探讨C更深层的使用。 [学习笔记] 3. C / CPP提高1. 模板1.1 模板的概念1.2 函数模板1.2.1 函数模板语法1.2.2 函数模板注意事项1.2. 3函数模板案例1.2.4 普通函数与函数模板的区别1.2.5 普通函数与函数模板的调用规则1.…
阅读更多...
HTML标签

HTML标签

目录 1.注释标签 2.标题标签:h1-h6 3.段落标签 4.换行标签 5.转义字符 6.格式化标签 7.图片标签:img 8.超链接便签:a 9.表格标签 10.列表标签 11.表单标签 12.无语义标签:div&span 1.注释标签 <!-- 我是注释 --> ctrl/快捷键可以快速进行注释/取消注释 …
阅读更多...
PVE虚拟机安装爱快/iKuai软路由(爱快软路由虚拟机系统安装教程)

PVE虚拟机安装爱快/iKuai软路由(爱快软路由虚拟机系统安装教程)

上篇提到PVE后&#xff0c;装LINUX CENTOS8&#xff0c;现在装个爱快软路由. 一、软硬件要求 1、安装好PVE虚拟环境的X86系统&#xff0c;32位爱快系统需要512MB以上内存&#xff0c;64位爱快系统需要4GB以上。 2、双网口主板&#xff0c;如果是单网口要配置openwrt/LEDE为单…
阅读更多...
【C语言编程练习】手撕扫雷

【C语言编程练习】手撕扫雷

【C语言编程练习】手撕扫雷一、目标二、具体实现步骤1、棋盘的设计思路2、选定模式3、创建及初始化棋盘4、布置雷到棋盘5、打印棋盘6、排查雷7、递归版统计雷数8、判断是否胜出的函数三、完整代码逻辑展示1、Minesweeping.h2、Minesweeping.c3、test.c一、目标 之所以打算将扫…
阅读更多...
板内盘中孔设计狂飙，细密间距线路中招

板内盘中孔设计狂飙，细密间距线路中招

一博高速先生成员&#xff1a;王辉东大风起兮云飞扬&#xff0c;投板兮人心舒畅。赵理工打了哈欠&#xff0c;伸了个懒腰&#xff0c;看了看窗外&#xff0c;对林如烟说道&#xff1a;“春天虽美&#xff0c;但是容易让人沉醉。如烟&#xff0c;快女神节了&#xff0c;要不今晚…
阅读更多...
AHP层次分析法分析流程

AHP层次分析法分析流程

AHP层次分析法分析流程&#xff1a; 一、案例背景 当前有一项研究&#xff0c;想要构建公司绩效评价指标体系&#xff0c;将一级指标分为4个&#xff0c;分别是&#xff1a;服务质量、管理水平、运行成本、安全生产&#xff0c;现在想要确定4个指标的权重。 AHP层次分析法是一…
阅读更多...
【MySQL】 SQL 执行顺序 OR 递增id用完了怎么办呢？哪个问题难回答

【MySQL】 SQL 执行顺序 OR 递增id用完了怎么办呢？哪个问题难回答

这里写目录标题写在前面基础概念SQL 执行顺序FROMONJOINWHEREGROUP BYHAVINGSELECTDISTINCTORDER BYMysql 自增 ID用完了1.有主键的情况解决方案2.没有主键解决方案&#xff1a;总结写在前面 三月已经结束了&#xff0c;不知道这个月你有没有被邀请面试&#xff0c;如果有面试…
阅读更多...
【C++笔试强训】第二天

【C++笔试强训】第二天

选择题 解析&#xff1a;考查printf&#xff0c;%后面-表示输出左对齐&#xff0c;输出左对齐30个字符格式为%-30f&#xff0c;.后面表示精度。%e字符以指数形势输出&#xff0c;可以认为是double类型&#xff08;也就是小数点后保留6位&#xff09;的指数。为%f字符表示输出格…
阅读更多...
JVM问题(二) -- 内存泄漏

JVM问题(二) -- 内存泄漏

1. 什么是内存泄漏&#xff1a; 2. 内存泄漏的理解&#xff1a; 严格来说&#xff0c;只有对象不会再被程序用到了&#xff0c;但是GC又不能回收他们的情况&#xff0c;才叫内存泄漏。 但是实际情况很多时候一些不太好的实践&#xff08;或疏忽&#xff09;会导致对象的生命周…
阅读更多...
最新文章

Copyright @ 2022~2023