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.rhkb.cn/news/319460.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

恶补《操作系统》5_2——王道学习笔记

恶补《操作系统》5_2——王道学习笔记

5.2_1 I-O核心子系统 1、用户层软件 假脱机系统 2、设备独立性软件&#xff08;设备无关性软件&#xff09; IO调度、设备保护、设备分配与回收、缓冲区管理 3、设备驱动程序&#xff08;比如打印机驱动&#xff09; 4、中断处理程序 5、硬件 5.2_2 假脱机技术&#xff…
阅读更多...
小程序引入 Vant Weapp 极简教程

小程序引入 Vant Weapp 极简教程

一切以 Vant Weapp 官方文档 为准 Vant Weapp 官方文档 - 快速入手 1. 安装nodejs 前往官网下载安装即可 nodejs官网 安装好后 在命令行&#xff08;winr&#xff0c;输入cmd&#xff09;输入 node -v若显示版本信息&#xff0c;即为安装成功 2. 在 小程序根目录 命令行/终端…
阅读更多...
www.fastssh.com SSH over WebSockets with CDNs

www.fastssh.com SSH over WebSockets with CDNs

https://www.fastssh.com/page/create-ssh-cdn-websocket/server/这其实不是标准的websocket报文(服务器响应报文无Sec-Websocket-Accept字段)&#xff0c;所以无法使用github.com/gorilla/websocket包&#xff1a;GET / HTTP/1.1 Host: hostname:8080 User-Agent: Go-http-cli…
阅读更多...
jvm重要参数可视化和线上问题排查

jvm重要参数可视化和线上问题排查

jvm重要参数可视化和线上问题排查 目标jvm参数分类(了解)运行时数据区相关的&#xff08;jdk1.8&#xff09;处理 OOM 相关的垃圾回收器相关的GC 日志记录相关的意义,默认值,调优原则&#xff08;重要&#xff0c; 待拆分&#xff09; 排查 OOM 流程 和 常见原因参考文章 目标 …
阅读更多...
【除了协程还有哪些方式可以实现异步编程】

【除了协程还有哪些方式可以实现异步编程】

在Unity中&#xff0c;除了使用协程实现异步编程外&#xff0c;还有以下几种方法&#xff1a; 异步加载资源&#xff1a; 使用UnityWebRequest类进行异步加载资源&#xff0c;这在加载网络资源或动态加载资源时非常有用。 using UnityEngine; using UnityEngine.Networking;…
阅读更多...
基于OpenCv的图像特征点检测

基于OpenCv的图像特征点检测

⚠申明&#xff1a; 未经许可&#xff0c;禁止以任何形式转载&#xff0c;若要引用&#xff0c;请标注链接地址。 全文共计3077字&#xff0c;阅读大概需要3分钟 &#x1f308;更多学习内容&#xff0c; 欢迎&#x1f44f;关注&#x1f440;【文末】我的个人微信公众号&#xf…
阅读更多...
C语言/数据结构——（用双链表实现数据的增删查改）

C语言/数据结构——（用双链表实现数据的增删查改）

一.前言 嗨嗨嗨&#xff0c;大家好久不见&#xff01;前面我们已经通过数组实现数据的增删查改、单链表实现数据的增删查改&#xff0c;现在让我们尝试一下使用双链表实现数据的增删查改吧&#xff01; 二.正文 如同往常一样&#xff0c;对于稍微大点的项目来说&#xff0c;…
阅读更多...
【工程记录】Python爬虫入门记录（Requests BeautifulSoup）

【工程记录】Python爬虫入门记录（Requests BeautifulSoup）

目录 写在前面1. 环境配置2. 获取网页数据3. 解析网页数据4. 提取所需数据4.1 简单提取4.2 多级索引提取 5. 常见问题 写在前面 仅作个人学习与记录用。主要整理使用Requests和BeautifulSoup库的简单爬虫方法。在进行数据爬取时&#xff0c;请确保遵守相关法律法规和网站的服务…
阅读更多...
FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

点击查看详情!点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情 1、描述 这是一款桌面科研实验测温热成像多功能热像记录仪&#xff0c;小巧轻便…
阅读更多...
SFOS1：开发环境搭建

SFOS1：开发环境搭建

一、简介 最近在学习sailfish os的应用开发&#xff0c;主要内容是QmlPython。所以&#xff0c;在开发之前需要对开发环境&#xff08;virtualBox官方SDKcmake编译器python&#xff09;进行搭建。值得注意的是&#xff0c;我的开发环境是ubuntu22.04。如果是windows可能大同小异…
阅读更多...
带文字海报流程自动化

带文字海报流程自动化

上一篇文章&#xff1a; 带文字海报流程自动化 - 知乎 项目代码整理在&#xff1a; https://github.com/liangwq/Chatglm_lora_multi-gpu​github.com/liangwq/Chatglm_lora_multi-gpu 根据用户的输入生成图片prompt模块代码封装&#xff1a; from openai import OpenAI im…
阅读更多...
获取淘宝商品销量数据接口

获取淘宝商品销量数据接口

淘宝爬虫商品销量数据采集通常涉及以下几个步骤&#xff1a; 1、确定采集目标&#xff1a;需要明确要采集的商品类别、筛选条件&#xff08;如天猫、价格区间&#xff09;、销量和金额等数据。例如&#xff0c;如果您想了解“小鱼零食”的销量和金额&#xff0c;您需要设定好价…
阅读更多...
【云原生系列】云计算概念与架构设计介绍

【云原生系列】云计算概念与架构设计介绍

1 什么是云计算 云计算是一种基于互联网的计算模式&#xff0c;在这个模式下&#xff0c;各种计算资源&#xff08;例如计算机、存储设备、网络设备、应用程序等&#xff09;可以通过互联网实现共享和交付。云计算架构设计的主要目标是实现高效、可扩展、可靠、安全和经济的计算…
阅读更多...
C++多态特性详解

C++多态特性详解

目录 概念&#xff1a; 定义及实现&#xff1a; 虚函数重写的两个例外&#xff1a; 1.协变&#xff1a; 2.析构函数的重写&#xff1a; final关键字&#xff1a; override关键字&#xff1a; 多态是如何实现的&#xff08;底层&#xff09;&#xff1a; 面试题&#xff1…
阅读更多...
idea No versioned directories to update were found

idea No versioned directories to update were found

idea如何配置svn以及svn安装时需要注意什么 下载地址&#xff1a;https://112-28-188-82.pd1.123pan.cn:30443/download-cdn.123pan.cn/batch-download/123-820/3ec9445a/1626635-0/3ec9445a25ba365a23fc433ce0c16f34?v5&t1714358478&s171435847804276f7d9249382ba512…
阅读更多...
代码随想录算法训练营DAY40\DAY41|C++动态规划Part.3|343.整数拆分、96.不同的二叉搜索树

代码随想录算法训练营DAY40\DAY41|C++动态规划Part.3|343.整数拆分、96.不同的二叉搜索树

DAY40休息日&#xff0c;本篇为DAY41的内容 文章目录 343.整数拆分思路dp含义递推公式&#xff08;难点&#xff09;初始化遍历顺序打印 CPP代码数学方法归纳证明法 96.不同的二叉搜索树思路dp含义递推公式初始化遍历顺序打印 CPP代码题目总结 343.整数拆分 力扣题目链接 文章…
阅读更多...
小蓝本--因式分解（习题1）讲解

小蓝本--因式分解（习题1）讲解

这几天要备战期中&#xff0c;下一期可能要等暑假了...... 小升初的压力真是紧扣于头啊&#xff0c;为了分到一个好班&#xff0c;拼了&#xff01; 对了&#xff0c;下一期可能在寒假更&#xff0c;见谅&#xff01; 1分解因式&#xff1a; 公因式&#xff1a; 答案&#xff…
阅读更多...
vue3--element-plus-抽屉文件上传和富文本编辑器

vue3--element-plus-抽屉文件上传和富文本编辑器

一、封装组件 article/components/ArticleEdit.vue <script setup> import { ref } from vue const visibleDrawer ref(false)const open (row) > {visibleDrawer.value trueconsole.log(row) }defineExpose({open }) </script><template><!-- 抽…
阅读更多...
iptables---防火墙

iptables---防火墙

防火墙介绍 防火墙的作用可以理解为是一堵墙&#xff0c;是一个门&#xff0c;用于保护服务器安全的。 防火墙可以保护服务器的安全&#xff0c;还可以定义各种流量匹配的规则。 防火墙的作用 防火墙具有对服务器很好的保护作用&#xff0c;入侵者必须穿透防火墙的安全防护…
阅读更多...
排序算法--快速排序

排序算法--快速排序

前提&#xff1a; 快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发