栈和队列相关题 ， 用队列实现栈， 用栈实现队列 ，设计循环队列 C/C++双版本

文章目录

  • 1.用队列实现栈
  • 2.用栈实现队列
  • 3. 设计循环队列

1.用队列实现栈

225. 用队列实现栈

在这里插入图片描述

思路：

使用两个队列，始终保持一个队列为空。

  • 当我们需要进行压栈操作时，将数据压入不为空的队列中（若两个都为空，则随便压入一个队列）。
  • 当需要进行出栈操作时，将不为空的队列中的数据导入空队列，仅留下一个数据，这时将这个数据返回并且删除即可。
  • 判断栈是否为空，即判断两个队列是否同时为空。

在这里插入图片描述
C 代码：

typedef int QDataType;//队列中存储的元素类型typedef struct QListNode
{struct QListNode* next;//指针域QDataType data;//数据域
}QListNode;typedef struct Queue
{QListNode* head;//队头QListNode* tail;//队尾
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{assert(pq);//起始时队列为空pq->head = NULL;pq->tail = NULL;
}//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);QListNode* cur = pq->head;//接收队头//遍历链表，逐个释放结点while (cur){QListNode* next = cur->next;free(cur);cur = next;}pq->head = NULL;//队头置空pq->tail = NULL;//队尾置空
}//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));//申请新结点if (newnode == NULL){printf("malloc fail\n");exit(-1);}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));//检测队列是否为空if (pq->head->next == NULL)//队列中只有一个结点{free(pq->head);pq->head = NULL;pq->tail = NULL;}else//队列中有多个结点{QListNode* next = pq->head->next;free(pq->head);pq->head = next;//改变队头指针指向}
}//获取队列头部元素
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);QListNode* cur = pq->head;//接收队头int count = 0;//记录结点个数while (cur)//遍历队列{count++;cur = cur->next;}return count;//返回队列中的结点数
}/*---以上代码是队列的基本功能实现，以下代码是题解主体部分---*/typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* pEmpty = &obj->q1;//记录空队列Queue* pNoEmpty = &obj->q2;//记录非空队列if (!QueueEmpty(&obj->q1)){pEmpty = &obj->q2;pNoEmpty = &obj->q1;}//将非空队列中的数据放入空队列中，只留下一个数据while(QueueSize(pNoEmpty) > 1){QueuePush(pEmpty,QueueFront(pNoEmpty));QueuePop(pNoEmpty);}int front = QueueFront(pNoEmpty);//获取目标数据QueuePop(pNoEmpty);//删除目标数据return front;
}int myStackTop(MyStack* obj) {//获取非空队列的队尾数据if (!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {//两个队列均为空，则MyStack为空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);//释放第一个队列QueueDestroy(&obj->q2);//释放第二个队列free(obj);//释放MyStack
}

C++ 代码：

class MyStack {
public:queue<int> q1;queue<int> q2;MyStack() {}void push(int x) {if (!q1.empty()){q1.push(x);}else{q2.push(x);}}int pop() {queue<int>* qempty = &q1;queue<int>* qnoempty = &q2;if (!q1.empty()){qempty = &q2;qnoempty = &q1;}while (qnoempty->size() > 1){qempty->push(qnoempty->front());qnoempty->pop();}int top = qnoempty->front();qnoempty->pop();return top;}int top() {if (!q1.empty()){return q1.back();}else{return q2.back();}}bool empty() {return q1.empty() && q2.empty();}
};

2.用栈实现队列

232. 用栈实现队列

在这里插入图片描述

思路：

使用两个栈，第一个栈只用于数据的输入，第二个栈只用于数据的输出。
当需要输出数据，但第二个栈为空时，先将第一个栈中的数据一个一个导入到第二个栈，然后第二个栈再输出数据即可。

在这里插入图片描述
C代码：

typedef int STDataType;//栈中存储的元素类型typedef struct Stack
{STDataType* a;//栈int top;//栈顶int capacity;//容量，方便增容
}Stack;//初始化栈
void StackInit(Stack* pst)
{assert(pst);pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);//初始化栈可存储4个元素pst->top = 0;//初始时栈中无元素，栈顶为0pst->capacity = 4;//容量为4
}//销毁栈
void StackDestroy(Stack* pst)
{assert(pst);free(pst->a);//释放栈pst->a = NULL;//及时置空pst->top = 0;//栈顶置0pst->capacity = 0;//容量置0
}//入栈
void StackPush(Stack* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity)//栈已满，需扩容{STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType)*pst->capacity * 2);if (tmp == NULL){printf("realloc fail\n");exit(-1);}pst->a = tmp;pst->capacity *= 2;//栈容量扩大为原来的两倍}pst->a[pst->top] = x;//栈顶位置存放元素xpst->top++;//栈顶上移
}//检测栈是否为空
bool StackEmpty(Stack* pst)
{assert(pst);return pst->top == 0;
}//出栈
void StackPop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));//检测栈是否为空pst->top--;//栈顶下移
}//获取栈顶元素
STDataType StackTop(Stack* pst)
{assert(pst);assert(!StackEmpty(pst));//检测栈是否为空return pst->a[pst->top - 1];//返回栈顶元素
}//获取栈中有效元素个数
int StackSize(Stack* pst)
{assert(pst);return pst->top;//top的值便是栈中有效元素的个数
}/*---以上代码是栈的基本功能实现，以下代码是题解主体部分---*/typedef struct {Stack pushST;//插入数据时用的栈Stack popST;//删除数据时用的栈
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//申请一个队列类型StackInit(&obj->pushST);//初始化pushSTStackInit(&obj->popST);//初始化popSTreturn obj;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST, x);//插入数据，向pushST插入
}int myQueuePeek(MyQueue* obj) {if(StackEmpty(&obj->popST))//popST为空时，需先将pushST中数据导入popST{while(!StackEmpty(&obj->pushST))//将pushST数据全部导入popST{StackPush(&obj->popST, StackTop(&obj->pushST));StackPop(&obj->pushST);}}return StackTop(&obj->popST);//返回popST栈顶的元素
}int myQueuePop(MyQueue* obj) {int top = myQueuePeek(obj);StackPop(&obj->popST);//删除数据，删除popST中栈顶的元素return top;
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);//两个栈均为空，则“队列”为空
}void myQueueFree(MyQueue* obj) {//先释放两个栈，再释放队列的结构体类型StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);
}

C++ 代码：

class MyQueue {
public:stack<int> pushST;stack<int> popST;MyQueue() {}void push(int x) {pushST.push(x);}int pop() {int top = this->peek();popST.pop();return top;}int peek() {if(popST.empty()){while(!pushST.empty()){popST.push(pushST.top());pushST.pop();}}return popST.top();}bool empty() {return pushST.empty() && popST.empty();}
};

3. 设计循环队列

622. 设计循环队列

在这里插入图片描述

思路：

在环形队列中，队列为空时，队头队尾指向同一个位置。当队列不为空时，队头指向插入的第一个数据，队尾指向最后一个数据的下一个位置。当tail+1等于front时，说明环形队列已满。
 
注意：
 环形队列的队尾不能像常规队列中队尾一样指向最后一个数据，如果这样的话，我们将不能区别环形队列的状态是空还是满，因为此时队头和队尾都指向同一个位置。这就意味着，我们必须留出一个空间，这个空间不能存放数据，这样我们才能很好的区别环形队列的状态是空还是满

在这里插入图片描述
我们如果用一个数组来实现这个环形队列的话，上面这三种状态就对应于以下三种状态：

在这里插入图片描述

可以看出，此时这个数组和环形完全扯不上关系，这其实很简单，我们只需注意判断两个地方：

  1. 当指针指向整个数组的后方的时候，让该指针重新指向数组的第一个元素。
  2. 当指针指向整个数组的前方的时候，让该指针直接指向数组最后一个有效元素的后面。

在这里插入图片描述
C 代码：

typedef struct {int* a;//数组模拟环形队列int k;//队列可存储的有效数据总数int front;//队头int tail;//队尾的后一个位置
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请一个环形队列obj->a = (int*)malloc(sizeof(int)*(k+1));//开辟队列空间//初始时，队头和队尾均为0obj->front = 0;obj->tail = 0;obj->k = k;//设置队列可存储的有效数据个数return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->tail;//当front和tail指向同一位置时，队列为空
}bool myCircularQueueIsFull(MyCircularQueue* obj) {int tailnext = obj->tail+1;if(tailnext == obj->k+1)//当指针指到队列末尾时，指针返回队列开头，使队列循环tailnext = 0;return tailnext == obj->front;//当指针指到队列末尾时，指针返回队列开头，使队列循环
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))//队列已满，不能再插入数据return false;obj->a[obj->tail] = value;//插入数据obj->tail++;if(obj->tail == obj->k+1)//使队列循环obj->tail = 0;return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//当队列为空时，无法再删除数据return false;obj->front++;if(obj->front == obj->k+1)obj->front = 0;return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据可返回{return -1;}else{return obj->a[obj->front];//返回队头指向的数据}
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))//当队列为空时，无数据返回{return -1;}else//返回tail-1指向位置的数据{int tailPrev = obj->tail-1;if(tailPrev == -1)//使队列循环tailPrev = obj->k;return obj->a[tailPrev];}
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);//先释放动态开辟的数组free(obj);//再释放动态开辟的结构体
}

C++ 代码：

class MyCircularQueue {
public:vector<int> _a;//数组模拟环形队列   int _k;//队列可存储的有效数据总数int _front;//队头int _tail;//队尾的后一个位置MyCircularQueue(int k) {_k = k;_front = _tail = 0;_a = vector<int>(k+1);}bool enQueue(int value) {if(isFull()) return false;_a[_tail] = value;_tail++;_tail%=(_k+1);return true;}bool deQueue() {if(isEmpty())return false;_front++;_front%=(_k+1);return true;}int Front() {if(isEmpty())return -1;return _a[_front % (_k+1)];}int Rear() {if(isEmpty())return -1;int tailprev = _tail-1;return _a[tailprev == -1 ? _k : tailprev];}bool isEmpty() {return _front == _tail;}bool isFull() {return ((_tail+1) % (_k+1)) == _front;}
};

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

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

相关文章

关于STM32在代码中的而GPIO里面的寄存器(ODR等)不需要宏定义的问题

关于STM32在代码中的而GPIO里面的寄存器(ODR等)不需要宏定义的问题

1.GPIO为什么需要宏定义地址 在 STM32 这样的微控制器中&#xff0c;硬件寄存器的地址是固定的并且特定于每个外设&#xff08;比如 GPIOA、GPIOB 等&#xff09;。为了方便代码访问这些硬件寄存器&#xff0c;我们通常会使用宏定义来指定每个外设的基地址。这样做有几个理由&a…
阅读更多...
kimi智能助手，5大高阶玩法，95%的人还不知道

kimi智能助手，5大高阶玩法，95%的人还不知道

01 智能搜索：精准定位，一键获取最佳答案 Kimi，作为您的AI助手，拥有卓越的网络搜索能力。 我们能够迅速穿梭于信息海洋，为您筛选出五篇精选网络文章，并提供直接的网址链接。 Kimi的总结能力同样出色，特别适合那些追求效率、不愿深陷长篇文章的用户。 02 PDF速读：快速把…
阅读更多...
关于数学建模的一些介绍

关于数学建模的一些介绍

为了更好了解世界&#xff0c;我们可以通过数学来描述许多特定的现象&#xff0c;而数学模型就是现实世界的理想化&#xff0c;不过它永远不能完全精确地表示现实世界。 在这篇文章中&#xff0c;我将介绍一些数学建模的基本概念以及相应的基础知识&#xff0c;而关于更具体的…
阅读更多...
远翔升压恒流芯片FP7209X与FP7209M什么区别？做以下应用市场摄影补光灯、便携灯、智能家居（调光）市场、太阳能、车灯、洗墙灯、舞台灯必看！

远翔升压恒流芯片FP7209X与FP7209M什么区别？做以下应用市场摄影补光灯、便携灯、智能家居（调光）市场、太阳能、车灯、洗墙灯、舞台灯必看！

一&#xff0c;概述 FP7209是台湾远翔一款非同步升压LED驱动IC&#xff0c;封装有2种&#xff0c;分别是SOP-8L(EP), TSSOP-14L(EP)。控制外部开关NMOS。 输入低启动电压2.8V&#xff0c;可支持单节锂电池供电。工作电压5V&#xff0c;VFB反馈电压0.25V&#xff0c;反馈电压低…
阅读更多...
算法日记 18 day 二叉树

算法日记 18 day 二叉树

最后三题&#xff0c;二叉树就结束啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;修剪二叉搜索树 669. 修剪二叉搜索树 - 力扣&#xff08;LeetCode&#xff09; 给你二叉搜索树的根节点 root &#xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树…
阅读更多...
hashcat使用

hashcat使用

0.介绍 Hashcat 软件是一款非常强大的、开源的、号称世界上最快的密码破解软件&#xff0c;配合强大的字典&#xff0c;可以破译超过百分之九十的密码。Hashcat 目前支持各类公开算法高达240类&#xff0c;市面上公开的密码加密算法基本都支持&#xff0c;有 Microsoft LM 哈希…
阅读更多...
mysql 安装 windows

mysql 安装 windows

新版安装 新版本安装 如果出现initializing database无法安装 则用我当前版本传送门 如MySQL 安装时没有developer default 选项 解决方法传送门 如果上述还不行 可以选择full 汉化下载 传送门
阅读更多...
基于Redis缓存机制实现高并发接口调试

基于Redis缓存机制实现高并发接口调试

创建接口 这里使用的是阿里云提供的接口服务直接做的测试&#xff0c;接口地址 curl http://localhost:8080/initData?tokenAppWithRedis 这里主要通过参数cacheFirstfalse和true来区分是否走缓存&#xff0c;正常的业务机制可能是通过后台代码逻辑自行控制的&#xff0c;这…
阅读更多...
vue常见题型(1-10)

vue常见题型(1-10)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 2.2双向绑定的原理是什么vue框架采用的是数据双向绑定的方式&#xff0c;由三个重要部分构成2.2.1.ViewModel2.2.2 双向绑定2.2.3.1.编译Compile2.2.3.2.依赖收集 3…
阅读更多...
C语言变量与强制类型转换深度解析

C语言变量与强制类型转换深度解析

在上一篇文章中&#xff0c;小编对数据类型进行了详细的讲解与剖析&#xff0c;所以本篇文章小编要带大家理解变量和强制类型转。还是老规矩&#xff0c;来波鸡汤&#xff0c;学习一定不能着急&#xff0c;无法一下就学明白的知识我们需要给他时间&#xff0c;一定不要在一个知…
阅读更多...
JAVA+微信小程序前后端源码 微信OCR识别 识别身份证信息

JAVA+微信小程序前后端源码 微信OCR识别 识别身份证信息

官方文档:身份证识别 | 微信开放文档 实现效果 : 用的奥巴马的网络图片测试,图片 后端JAVA代码 这里用的若依的后端,前后端分离版的 package com.ruoyi.common.utils;import java.io.File; import java.io.IOException;import org.apache.http.HttpEntity; import org.apac…
阅读更多...
SL6605 输入0.8-5.5V 单颗锂电池驱动LED升压恒流限流方案

SL6605 输入0.8-5.5V 单颗锂电池驱动LED升压恒流限流方案

一、芯片特性 输入电压范围广&#xff1a;SL6605可接受0.8V至5.5V的输入电压&#xff0c;使其能够轻松应对各种锂电池电压波动。升压恒流功能&#xff1a;该芯片具有升压能力&#xff0c;可将低电压输入转换为适合LED驱动的高电压&#xff0c;并保持恒定的输出电流。限流保护&…
阅读更多...
ubuntu 安装go和vscode

ubuntu 安装go和vscode

1 安装Go 打开终端&#xff0c;执行以下命令下载Golang安装包&#xff1a; wget https://golang.org/dl/go1.xx.x.linux-amd64.tar.gz注意&#xff1a;替换命令中的“1.xx.x”为最新版本号&#xff0c;例如&#xff1a;1.23.2. 2. 解压安装包&#xff1a; sudo tar -C /usr/…
阅读更多...
[spring源码]spring启动流程

[spring源码]spring启动流程

spring启动流程 AnnotationConfigApplicationContext的构造方法 1.父类构造方法&#xff0c;构造一个DefaultListableBeanFactory 在调用AnnotationConfigApplicationContext的构造方法之前&#xff0c;会调用父类GenericApplicationContext的无参构造方法&#xff0c;会构造…
阅读更多...
Kafka自动生产消息软件(自动化测试Kafka)

Kafka自动生产消息软件(自动化测试Kafka)

点击下载《Kafka服务端(含Zookeeper)一键自启软件》 点击下载《kafka客户端生产者消费者kafka可视化工具&#xff08;可生产和消费消息&#xff09;》 点击下载《Kafka自动生产消息软件》 1. 前言 在软件开发过程中&#xff0c;Kafka常被用作消息队列来处理特定的业务功能。为…
阅读更多...
debian系统安装qt的时候 显示xcb相关文件缺失

debian系统安装qt的时候 显示xcb相关文件缺失

如果是安装之后的问题 我们可以选择使用ldd的命令查看当前依赖的so那些文件确实 ldd /home/yinsir/Qt/5.15.2/gcc_64/plugins/platforms/libqxcb.so 本人在进行打包的时候 出现则会个报错 ERROR: ldd outputLine: “libxcb-util.so.1 > not found” ERROR: for binary: “/…
阅读更多...
F28379D DAC 寄存器的值千万不要设置成4096啦！

F28379D DAC 寄存器的值千万不要设置成4096啦！

在之前的博客中&#xff0c;更新了如何 使用F28379D的片内DAC&#xff0c;提到DAC为12位的 DAC&#xff0c;因此DAC可以将参考电压分为4096份。不注意的小伙伴可能会将 对应的寄存器的值设置为4096&#xff0c;这样会导致DSP运行至_error_然后停止的哦&#xff0c;如果正在做功…
阅读更多...
中研在线教育：开启知识新征程，拓展世界新视野

中研在线教育：开启知识新征程，拓展世界新视野

在当今竞争激烈、知识驱动的时代&#xff0c;教育领域不断涌现出创新型的平台&#xff0c;而中研在线教育无疑是其中一颗璀璨的明星。作为专注于中国研究生知识的在线平台&#xff0c;中研在线教育以其丰富的业务、积极向上的企业价值观和极具感染力的口号&#xff0c;为广大学…
阅读更多...
PyQt5实战——多脚本集合包，程序入口QMainWindow（三）

PyQt5实战——多脚本集合包，程序入口QMainWindow（三）

个人博客&#xff1a;苏三有春的博客 系列往期文章&#xff1a; PyQt5实战——多脚本集合包&#xff0c;前言与环境配置&#xff08;一&#xff09; PyQt5实战——多脚本集合包&#xff0c;UI以及工程布局&#xff08;二&#xff09; PyQt程序入口&#xff08;QMainWindow&…
阅读更多...
A018基于Spring Boot的民宿租赁系统

A018基于Spring Boot的民宿租赁系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…
阅读更多...
最新文章

Copyright @ 2022~2023