C语言之数据结构之栈和队列的运用

目录

    • 1. 用队列实现栈
      • 1.1 思路讲解
      • 1.2 代码实现
    • 2. 用栈实现队列
      • 1.1 思路讲解
      • 1.2 代码实现
    • 总结

在这里插入图片描述
•͈ᴗ•͈ 个人主页：御翮
•͈ᴗ•͈ 个人专栏：C语言数据结构
•͈ᴗ•͈ 欢迎大家关注和订阅!!!

在这里插入图片描述

1. 用队列实现栈

题目描述：

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

实现 MyStack 类：

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

注意：

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

示例：

输入：
[“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 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

1.1 思路讲解

首先队列的特性是先入先出，而栈的特性是先入后出

题目说用两个队列实现一个栈

所以当栈为空时我们有两个空队列q1和q2

我们入数据时先默认入q2，假设这里依次入1、2、3

在这里插入图片描述

如果这个时候我们要出栈呢，如果按队列先入先出，我们会拿到1而不是最后入的3

此时我们可以先把1和2依次放入q1中，此时q2中就只剩3，就可以先取出3了

在这里插入图片描述

如果我们接着要放数据，就放入非空的队列q1，这样留一个队列q2为空，就还可以继续这样的出栈操作

在这里插入图片描述

当我们要继续出栈时，就把前n-1个数据放入空的队列中，再把最后一个数据取出，这样如此颠倒反复，就完成了先入后出的操作

在这里插入图片描述

1.2 代码实现

队列代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>typedef int QDatatype;typedef struct QNode
{struct QNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;void Init_Queue(Queue* ptr)
{assert(ptr);ptr->head = ptr->tail = NULL;
}
void Destroy_Queue(Queue* ptr)
{assert(ptr);QNode* cur = ptr->head;while (ptr->head != NULL){cur = ptr->head;ptr->head = ptr->head->next;free(cur);}ptr->tail = NULL;
}QNode* Buy_Node()
{QNode* tmp = (QNode*)malloc(sizeof(QNode));return tmp;
}void Print_Queue(Queue* ptr)
{assert(ptr);QNode* cur = ptr->head;while (cur != NULL){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}void Push_Queue(Queue* ptr, QDatatype val)
{assert(ptr);QNode* newnode = Buy_Node();if (newnode == NULL){perror("Push_Queue\n");exit(1);}newnode->data = val;newnode->next = NULL;if (ptr->head == NULL){ptr->head = ptr->tail = newnode;}else{ptr->tail->next = newnode;ptr->tail = newnode;}
}int Queue_Size(Queue* ptr)
{assert(ptr);int count = 0;QNode* cur = ptr->head;while (cur != NULL){cur = cur->next;count++;}return count;
}void Pop_Queue(Queue* ptr)
{assert(ptr);if (ptr->head == NULL){printf("队列中没有元素\n");return;}if (Queue_Size(ptr) == 1){free(ptr->tail);//如果删完了但是没有将tail置为NULL，则case 5 会发生错误，显示队尾元素随机值。ptr->tail = NULL;ptr->head = NULL;return;}QNode* pop = ptr->head;ptr->head = ptr->head->next;free(pop);
}QDatatype Queue_Front(Queue* ptr)
{assert(ptr);return ptr->head->data;
}QDatatype Queue_Back(Queue* ptr)
{assert(ptr);return ptr->tail->data;
}int Check_Empty(Queue* ptr)
{assert(ptr);if (Queue_Size(ptr))return 0;elsereturn 1;
}//以上是自己创建的队列，因为c语言没有队列

队列实现栈代码：

typedef struct 
{Queue q1;Queue q2;
} MyStack;// 创建栈
MyStack* myStackCreate() 
{MyStack* tmp = (MyStack*)malloc(sizeof(MyStack));if (tmp == NULL) // 开辟空间可能失败，失败则终止程序{printf("Fail: myStackCreate\n");exit(1);}Init_Queue(&tmp->q1); // 我们的栈由两个队列组成，所以初始化要调用队列的初始化Init_Queue(&tmp->q2);return tmp;
}// 数据入栈
void myStackPush(MyStack* obj, int x) 
{if (Check_Empty(&obj->q1)) // 哪个队列有元素就往哪放，两个都没有就默认放q2，保证只有一个队列有数据{Push_Queue(&obj->q2, x);}elsePush_Queue(&obj->q1, x);
}// 数据出栈
int myStackPop(MyStack* obj) 
{//题目保证每次调用pop时栈都不为空，不用考虑为空时的popif (Check_Empty(&obj->q1)) // 哪个队列有数据就将n-1个数据放到另一个队列，剩下的最后一个元素就是栈顶元素，直接出栈{int sum = Queue_Size(&obj->q2); // 获取队列元素个数nfor (int i = 0; i < sum - 1; i++) // 将前n-1个数据放到另一个空队列{Push_Queue(&obj->q1, Queue_Front(&obj->q2));Pop_Queue(&obj->q2);}QDatatype tmp = Queue_Front(&obj->q2); // 保存最后一个元素的值，再pop，因为要返回出栈元素的值Pop_Queue(&obj->q2);return tmp;}else{int sum = Queue_Size(&obj->q1);for (int j = 0; j < sum - 1; j++){Push_Queue(&obj->q2, Queue_Front(&obj->q1));Pop_Queue(&obj->q1);}QDatatype tmp = Queue_Front(&obj->q1);Pop_Queue(&obj->q1);return tmp;}
}// 获取栈顶元素
int myStackTop(MyStack* obj) 
{//题目保证每次调用top时栈都不为空，不用考虑为空时的topif (Check_Empty(&obj->q1)) // 因为我们前面入栈时保证了只有一个队列有数据，所以队尾元素就是栈顶元素{return Queue_Back(&obj->q2);}elsereturn Queue_Back(&obj->q1);
}// 判断栈是否为空
bool myStackEmpty(MyStack* obj) 
{if (Check_Empty(&obj->q1) && Check_Empty(&obj->q2)) // 栈由两个队列组成，两个队列都为空栈就为空{return true;}elsereturn false;
}// 销毁栈
void myStackFree(MyStack* obj) 
{Destroy_Queue(&obj->q1); // 消耗栈要销毁里面的两个队列Destroy_Queue(&obj->q2);free(obj);
}

2. 用栈实现队列

题目描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

1.1 思路讲解

首先栈的特性是先入后出，而队列的特性是先入先出

题目说用两个栈实现一个队列

所以当队列为空时我们有两个空栈

我们给这两个栈分别命名为push和pop

我们入数据只往push里放

在这里插入图片描述

出数据的话，如果pop为空，我们就把push栈里面的数据全放进pop栈里，再出栈，就取到了队头的元素

在这里插入图片描述

如果pop不为空，就直接出栈就好了

在这里插入图片描述

后序有数据也是直接放在push，push只进行入栈，pop只进行出栈，不像用队列实现栈一样要来回颠倒。

1.2 代码实现

栈代码：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <errno.h>typedef int STDataType;typedef struct Stack
{STDataType* stack;int size;int capacity;
}Stack;void Init_Stack(Stack* ptr)
{assert(ptr);STDataType* tmp = (STDataType*)malloc(3 * sizeof(STDataType));if (tmp == NULL){perror("Init_Stack\n");exit(1);}ptr->stack = tmp;ptr->capacity = 3;ptr->size = 0;
}void Destroy_Stack(Stack* ptr)
{assert(ptr);free(ptr->stack);ptr->stack = NULL;
}void Check_Capacity(Stack* ptr)
{assert(ptr);if (ptr->size == ptr->capacity){STDataType* tmp = (STDataType*)realloc(ptr->stack, 2 * ptr->capacity * sizeof(STDataType));if (tmp == NULL){perror("Check_Capacity\n");exit(1);}ptr->stack = tmp;ptr->capacity *= 2;}
}void Print_Stack(Stack* ptr)
{assert(ptr);for (int i = 0; i < ptr->size; i++){printf("%d ", ptr->stack[i]);}printf("\n");
}void Push_Stack(Stack* ptr, STDataType val)
{assert(ptr);Check_Capacity(ptr);ptr->stack[ptr->size] = val;ptr->size++;
}void Pop_Stack(Stack* ptr)
{assert(ptr);ptr->size--;
}STDataType Top_Stack(Stack* ptr)
{assert(ptr);return ptr->stack[ptr->size - 1];
}int Size_Stack(Stack* ptr)
{assert(ptr);return ptr->size;
}int Empty_Stack(Stack* ptr)
{assert(ptr);if (ptr->size == 0)return 1;elsereturn 0;
}typedef struct 
{Stack push;Stack pop;
} MyQueue;

栈实现队列代码：

// 创建队列
MyQueue* myQueueCreate() 
{MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));if (queue == NULL) // 开辟空间有可能失败，失败则终止程序{perror("myQueueCreate");exit(1);}Init_Stack(&queue->push); // 初始化队列要初始化里面的栈Init_Stack(&queue->pop);return queue;
}// 数据入队列
void myQueuePush(MyQueue* obj, int x) 
{Push_Stack(&obj->push, x); // 数据只入push栈
}// 数据出队列
int myQueuePop(MyQueue* obj) 
{if (Empty_Stack(&obj->pop)) // 如果pop栈为空，就要从push栈里面把数据拿过来{int sum = Size_Stack(&obj->push); // 获取push中的元素个数nfor (int i = 0; i < sum; i++){Push_Stack(&obj->pop, Top_Stack(&obj->push));Pop_Stack(&obj->push);}}int ret = Top_Stack(&obj->pop); // 先储存队头元素再出队列，因为题目要返回队头元素Pop_Stack(&obj->pop);return ret;
}// 获取队头元素
int myQueuePeek(MyQueue* obj) 
{if (Empty_Stack(&obj->pop)) // 如果pop栈为空，那就把push栈里面的元素拿过来{int sum = Size_Stack(&obj->push);for (int i = 0; i < sum; i++){Push_Stack(&obj->pop, Top_Stack(&obj->push));Pop_Stack(&obj->push);}}return Top_Stack(&obj->pop); // 队头元素就是pop栈中的栈顶元素，因为pop栈内的元素是push栈内的元素顺序颠倒过来
}// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) 
{if (Empty_Stack(&obj->push) && Empty_Stack(&obj->pop)) // 两个栈都为空，队列就为空{return true;}elsereturn false;
}// 销毁队列
void myQueueFree(MyQueue* obj) 
{Destroy_Stack(&obj->push);  // 销毁队列要销毁里面的两个栈Destroy_Stack(&obj->pop);free(obj);					// 不要忘记释放这个空间
}

总结

两个队列实现栈需要来回颠倒。
两个栈实现队列要确定一个push和一个pop。

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

练习题（2024/5/3）

练习题（2024/5/3）

1对称二叉树 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xff1a;false提示&#xff1a; 树中…
阅读更多...
鸿蒙通用组件Image简介

鸿蒙通用组件Image简介

鸿蒙通用组件Image简介 图片----Image图片支持三种引用方式设置图片宽高设置图片缩放模式设置图片占位图设置图片重复样式设置图片插值效果 图片----Image Image主要用于在应用中展示图片 Image($r(app.media.app_icon)).width(150) // 设置宽.height(150) // 设置高.objectF…
阅读更多...
一文看懂卷积神经网络CNN（1）—前馈神经网络

一文看懂卷积神经网络CNN（1）—前馈神经网络

目录 参考资料 一、神经网络 1、人脑神经网络 2、人工神经网络 3、神经网络的发展历史 二、前馈神经网络 1、神经元 &#xff08;1&#xff09;Sigmoid型函数 ① Logistic函数 ②Tanh函数 ③两个函数形状对比 &#xff08;2&#xff09;ReLU函数 ① 带泄露的ReLU函…
阅读更多...
leetcode刷题(3): 动态规划

leetcode刷题(3): 动态规划

文章目录 42. 接雨水解题思路c 实现 64. 最小路径和解题思路c 实现 62 不同路径解题思路c 实现 42. 接雨水 题目&#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例: 解题思路 使用动态…
阅读更多...
大功率双向直流电源的输出电压和电流

大功率双向直流电源的输出电压和电流

双向直流电源&#xff08;Bidirectional DC Power Supply&#xff09;是一种具有双向输出电能的直流电源。与传统的直流电源相比&#xff0c;双向直流电源在输出电能的同时&#xff0c;还具备一定的电流输入能力&#xff0c;从而使其应用范围更加广泛。大功率双向直流电源作为电…
阅读更多...
言语 目录

言语 目录

List item List item List item
阅读更多...
【业务场景】京东实际场景，频繁GC引起的CPU飙高问题的解决

【业务场景】京东实际场景，频繁GC引起的CPU飙高问题的解决

目录 1.业务介绍 2.判断任务类型 3.CPU飙高的原因 1.业务介绍 本文的业务场景是京东零售线公开的一篇文章&#xff0c;文章内容详细介绍了京东零售线如何将广告相关的定时任务从半小时优化到秒级的&#xff0c;原文链接&#xff1a; 半小时到秒级&#xff0c;京东零售定时…
阅读更多...
USP技术提升大语言模型的零样本学习能力

USP技术提升大语言模型的零样本学习能力

大语言模型&#xff08;LLMs&#xff09;在零样本和少样本学习能力上取得了显著进展&#xff0c;这通常通过上下文学习&#xff08;in-context learning, ICL&#xff09;和提示&#xff08;prompting&#xff09;来实现。然而&#xff0c;零样本性能通常较弱&#xff0c;因为缺…
阅读更多...
数据库（MySQL）—— 事务

数据库（MySQL）—— 事务

数据库&#xff08;MySQL&#xff09;—— 事务 什么是事务事务操作未控制事务测试异常情况 控制事务一查看/设置事务提交方式&#xff1a;提交事务回滚事务 控制事务二开启事务提交事务回滚事务 并发事务问题脏读&#xff08;Dirty Read&#xff09;不可重复读&#xff08;Non…
阅读更多...
【热门话题】如何构建具有高度扩展性的系统

【热门话题】如何构建具有高度扩展性的系统

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 如何构建具有高度扩展性的系统引言一、理解扩展性1.1 扩展性的定义1.2 扩展性的…
阅读更多...
嵌入式单片机中必会的50个电路分享

嵌入式单片机中必会的50个电路分享

单片机 电源 声音模块 收音机 485
阅读更多...
微软如何打造数字零售力航母系列科普08 - Yobe 如何联手微软Azure，安全使用客户数据，预测客户购买行为？

微软如何打造数字零售力航母系列科普08 - Yobe 如何联手微软Azure，安全使用客户数据，预测客户购买行为？

Yobe 如何联手Azure&#xff0c;安全使用客户数据&#xff0c;预测客户购买行为&#xff1f; 在当今数据驱动的世界中&#xff0c;了解客户行为并有能力通过数据和分析预测客户意图是企业保持竞争力所应具备的首要优势。Yobi由Max Snow、Bill Wise和Tom Griffiths于2019年创立&…
阅读更多...
vivado Aurora 8B/10B IP核（12）- Setp By Step搭建FPGA工程

vivado Aurora 8B/10B IP核（12）- Setp By Step搭建FPGA工程

Step1:任意创建一个新的空的工程&#xff08;创建工程的具体工程如果还不清楚的看我们教程第一季部分&#xff09;&#xff0c; 并且进入IP CORE列表 右击Customize ip Step2:配置 IP CORE-Core options Step3:配置 IP CORE-GT Selections Step4:配置 IP CORE-Shared Logic 为 …
阅读更多...
力扣刷题1

力扣刷题1

第一次刷Leetcode&#xff01;这个系列会已知更新下去的&#xff01; 由于作者太废&#xff0c;所以只能先更&#xff1a;【新】动计划---编程入门 题目简单 &#xff0c;不愧是第一题&#xff01;这题考察的是函数的返回值。 ACcode : class Solution { public:int sum(int n…
阅读更多...
机器学习笔记-20

机器学习笔记-20

处理大数据集的算法 1. 随机梯度下降 我们之前一直在学的梯度下降算法也叫Batch梯度下降算法&#xff0c;前面的笔记有提过一嘴。以线性回归为例子&#xff0c;随机梯度下降也适用于其他使用Batch梯度下降算法求参数的学习算法&#xff0c;随机梯度下降是对Batch梯度下降算法的…
阅读更多...
生成树协议（STP,MSTP,RSTP）详解

生成树协议（STP,MSTP,RSTP）详解

目录 STP生成树协议 二层环路出现的原因&#xff1a; 二层环路引发的危害&#xff1a; stp生成树防环的基本思路&#xff1a; 802.1D生成树协议&#xff1a; 配置BPDU的报文结构&#xff1a; 配置BPDU中某些字段的解析&#xff1a; TCN BPDU报文格式&#xff1a; stp中…
阅读更多...
LabVIEW鸡蛋品质智能分级系统

LabVIEW鸡蛋品质智能分级系统

LabVIEW鸡蛋品质智能分级系统 随着现代农业技术的飞速发展&#xff0c;精确、高效的农产品质量控制已成为行业的重要需求。其中&#xff0c;鸡蛋作为日常膳食中不可或缺的重要组成部分&#xff0c;其品质直接关系到消费者的健康与满意度。本文设计并实现了一套基于LabVIEW的鸡…
阅读更多...
3.3Java全栈开发前端+后端（全栈工程师进阶之路）-前端框架VUE3框架-企业级应用-Vue组合式API

3.3Java全栈开发前端+后端（全栈工程师进阶之路）-前端框架VUE3框架-企业级应用-Vue组合式API

为什么要使用Composition API 一个Options API实例 在前面的课程中&#xff0c;我们都是采用 Options API&#xff08;基于选项的 API &#xff09; 来写一个组件的。下面是一个实例&#xff1a; <template> Count is: {{ count }}, doubleCount is: {{ doubleCount…
阅读更多...
二、Linux系统安装

二、Linux系统安装

章节目标 Linux发展史掌握虚拟机软件安装新建虚拟机以及CentOS系统安装了解VMware备份的两种方式、能说出快照与克隆的区别 一、Linux发展史 1. Linux 起源 Linus(林纳斯托瓦兹)&#xff1a;Linux 的开发作者&#xff0c;被称为Linux 之父&#xff0c;Linux 诞生时是芬兰赫…
阅读更多...
PR2019软件下载教程

PR2019软件下载教程

打开下载网址&#xff1a;rjctx.com 选择Premiere&#xff1a; 选择PR2019&#xff0c;并点击&#xff1a; 拉到最后&#xff0c;选择百度网盘下载&#xff1a; 下载到本地。 二&#xff0c;软件安装 解压缩后&#xff0c;双击set_up 选择位置后&#xff0c;进行安装&…
阅读更多...
最新文章

Copyright @ 2022~2023