C语言中的循环队列与栈、队列之间的转换实现

引言

在数据结构的学习中，栈（Stack）和队列（Queue）是两个非常重要的概念。它们分别遵循着后进先出（LIFO）和先进先出（FIFO）的原则。在某些情况下，我们可能需要通过栈来模拟队列，或者通过队列来模拟栈的行为。本文将详细介绍这两种数据结构，并提供相应的C语言实现代码和图解。

一、栈（Stack）

栈是一种后进先出（LIFO）的数据结构，只允许在一端进行操作，这一端被称为栈顶（top）。栈的基本操作包括入栈（push）和出栈（pop）。

C语言实现栈：

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	//top指向栈顶数据的下一个位置
	ps->_top = 0;
	//top指向栈顶数据
	//ps->_top = -1;
	ps->_capacity = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * (sizeof(STDataType)));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	assert(ps);
	return ps->_top == 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

栈的图解：

（可以想象一个竖直的容器，新元素从顶部加入，也是从顶部取出。）

二、队列（Queue）

队列是一种先进先出（FIFO）的数据结构，只允许在两端进行操作，一端为队头（front），另一端为队尾（rear）。队列的基本操作包括入队（enqueue）和出队（dequeue）。C语言实现队列：

#include <stdio.h>  
#include <stdlib.h>  
#define MAX_SIZE 100  
  
typedef struct 
{  
    int data[MAX_SIZE];  
    int front, rear;  
} Queue;  
  
void initQueue(Queue *q) 
{  
    q->front = q->rear = -1;  
}  
  
int isFull(Queue *q) 
{  
    return (q->rear + 1) % MAX_SIZE == q->front;  
}  
  
int isEmpty(Queue *q) 
{  
    return q->front == -1;  
}  
  
void enqueue(Queue *q, int value) 
{  
    if (!isFull(q)) 
    {  
        q->data[++q->rear] = value;  
    } 
    else 
    {  
        printf("Queue is full!\n");  
    }  
}  
  
int dequeue(Queue *q) 
{  
    if (!isEmpty(q)) 
    {  
        int value = q->data[q->front++];  
        if (q->front > q->rear) q->front = q->rear = -1; // 处理队列为空的情况  
        return value;  
    } else 
    {  
        printf("Queue is empty!\n");  
        return -1;  
    }  
}  
  
// ... 其他队列操作函数 ...

队列的图解：

（可以想象一个水平的容器，新元素从尾部加入，从头部取出。）

三、循环队列

循环队列是对普通队列的一种改进，通过取模运算实现队首和队尾的循环，从而更高效地利用存储空间。相当于队列头尾相接,同时容量固定.

（代码与上面的队列实现类似，主要区别在于isFull和isEmpty的判断，以及front和rear的更新方式。）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef struct
{
    int* a;
    int head; //指向头
    int tail; //指向尾下一个
    int k; //容量
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (obj == NULL)
    {
        return;
    }
    
    //多开一个解决假溢出问题
    obj->a = (int*)malloc(sizeof(int)*(k + 1));
    obj->head = 0;
    obj->tail = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return (obj->tail + 1) % (obj->k + 1) == obj->head;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if (myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->tail] = value;
    obj->tail++;
    obj->tail %= (obj->k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    ++obj->head;
    obj->head %= (obj->k + 1);
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[obj->head];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if (myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    else
    {
        return obj->a[(obj->tail + obj->k) % (obj->k + 1)];
    }
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->a);
    free(obj);
}
四、栈实现队列

虽然栈是后进先出的数据结构，但我们可以通过两个栈（一个作为输入栈，一个作为输出栈）来模拟队列的先进先出特性。

代码实现：

（主要涉及两个栈的push和pop操作，以及如何在适当的时候交换两个栈的角色。）

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	//top指向栈顶数据的下一个位置
	ps->_top = 0;
	//top指向栈顶数据
	//ps->_top = -1;
	ps->_capacity = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * (sizeof(STDataType)));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->_a = tmp;
		ps->_capacity = newcapacity;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	assert(ps);
	return ps->_top == 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

//leetcode

typedef struct 
{
	Stack pushst;
	Stack popst;
} MyQueue;


MyQueue* myQueueCreate() 
{
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); 
	if (obj == NULL)
	{
		return;
	}
	StackInit(&(obj->popst));
	StackInit(&(obj->pushst));
	return obj;
}

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

int myQueuePeek(MyQueue* obj) 
{
	if (StackEmpty(&(obj->popst)))
	{
		//倒数据
		while (!StackEmpty(&(obj->pushst)))
		{
			int top = StackTop(&(obj->pushst));
			StackPush(&(obj->popst), top);
			StackPop(&(obj->pushst));
		}
	}
	return StackTop(&(obj->popst));
}

int myQueuePop(MyQueue* obj) 
{
	int front = myQueuePeek(obj);
	StackPop(&(obj->popst));
	return front;
}

bool myQueueEmpty(MyQueue* obj) 
{
	return StackEmpty(&(obj->popst)) && StackEmpty(&(obj->pushst));
}

void myQueueFree(MyQueue* obj) 
{
	StackDestroy(&(obj->popst));
	StackDestroy(&(obj->pushst));
	free(obj);
}
五、队列实现栈

队列是先进先出的数据结构，但通过两个队列（或者一个队列和一个辅助栈）也可以模拟栈的后进先出特性。

代码实现：

typedef char QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

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

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);

		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

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

	newnode->next = NULL;
	newnode->val = x;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

// 队头删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	/*QNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;

	if (pq->phead == NULL)
		pq->ptail = NULL;*/

		// 一个节点
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else // 多个节点
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	pq->size--;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}


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

	return pq->size;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}
typedef struct
{
	Queue q1;
	Queue q2;
} MyStack;
//leetcode
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* empty = &(obj->q1);
	Queue* nonempty = &(obj->q2);
	if (!QueueEmpty(&(obj->q1)))
	{
		nonempty = &(obj->q1);
		empty = &(obj->q2);
	}
	//不为空前size-1导走,删除最后一个就是栈顶数据
	while (QueueSize(nonempty) > 1)
	{
		QueuePush(empty, QueueFront(nonempty));
		QueuePop(nonempty);
	}
	int top = QueueFront(nonempty);
	QueuePop(nonempty);
	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);
}

分享到这里,欢迎翻阅我的文章.

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

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

相关文章

用友NC printBill 任意文件读取/删除漏洞复现(XVE-2024-10609)

用友NC printBill 任意文件读取/删除漏洞复现(XVE-2024-10609)

0x01 产品简介 用友NC是一款企业级ERP软件。作为一种信息化管理工具，用友NC提供了一系列业务管理模块，包括财务会计、采购管理、销售管理、物料管理、生产计划和人力资源管理等，帮助企业实现数字化转型和高效管理。 0x02 漏洞概述 用友NC printBill 接口处存在任意文件读…
阅读更多...
PDF编辑阅读器PDF Expert for Mac v3.10.1中文激活版

PDF编辑阅读器PDF Expert for Mac v3.10.1中文激活版

PDF Expert for Mac是一款易于使用的 PDF 编辑器和注释器&#xff0c;专为 Mac 设备设计。它允许用户轻松查看、编辑、签名、注释和共享 PDF。该软件使用户能够向他们的 PDF 添加文本、图像、链接和形状&#xff0c;突出显示和标记文本&#xff0c;填写表格以及签署数字文档。它…
阅读更多...
02-结构型设计模式(共7种)

02-结构型设计模式(共7种)

1. Adapter(适配器模式) 适配器模式是一种结构型设计模式&#xff0c;它允许将一个类的接口转换成客户端所期望的另一个接口。这种模式通常用于解决接口不兼容的情况&#xff0c;使得原本由于接口不匹配而无法工作的类可以一起工作。 在 C 中&#xff0c;适配器模式可以通过类适…
阅读更多...
数学建模——线性回归模型

数学建模——线性回归模型

目录 1.线性回归模型的具体步骤和要点&#xff1a; 1.收集数据&#xff1a; 2.探索性数据分析&#xff1a; 3.选择模型&#xff1a; 4.拟合模型&#xff1a; 5.评估模型&#xff1a; 1.R平方&#xff08;R-squared&#xff09;&#xff1a; 2.调整R平方&#xff08;Ad…
阅读更多...
Windows11系统配置WSL2网络使它支持LAN访问

Windows11系统配置WSL2网络使它支持LAN访问

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、WSL2安装二、使用步骤1.NAT2.镜像 三、写在最后总结 前言 WSL2的出现感觉真的是一个惊喜&#xff0c;又想玩Linux&#xff0c;又怕日用搞不了的最佳替代方…
阅读更多...
TreeMap详解：Java 有序 Map 原理与实现

TreeMap详解：Java 有序 Map 原理与实现

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…
阅读更多...
[初学者必看]JavaScript 简单实际案例练习，锻炼代码逻辑思维

[初学者必看]JavaScript 简单实际案例练习，锻炼代码逻辑思维

文章目录 创意小项目合集&#xff1a;从简易图片轮播到购物车1. 图片轮播器2. 动态列表3. 模态框&#xff08;Modal&#xff09;4. 简单的表单验证5. 简易待办事项列表&#xff08;Todo List&#xff09;6. 简易图片画廊7. 简易时钟8. 简易搜索框高亮9. 简易颜色选择器10. 简易…
阅读更多...
【知识碎片】2024_05_14

【知识碎片】2024_05_14

本篇记录了两道关于位运算的选择题&#xff0c;和一道有点思维的代码题。 C语言碎片知识 求函数返回值&#xff0c;传入 -1 &#xff0c;则在64位机器上函数返回&#xff08; &#xff09; int func(int x) {int count 0;while (x){count;x x&(x - 1);//与运算} return c…
阅读更多...
java项目之实验室管理系统(springboot+vue+mysql)

java项目之实验室管理系统(springboot+vue+mysql)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的实验室管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 实验室管理系统的主要使用…
阅读更多...
OpenAI 推出革命性新模型 GPT-4o：全能AI的新纪元

OpenAI 推出革命性新模型 GPT-4o：全能AI的新纪元

GPT-4o 模型的推出预示着人工智能领域的又一次飞跃&#xff0c;它将如何改变我们的世界&#xff1f; 在人工智能的快速发展浪潮中&#xff0c;OpenAI 再次站在了技术革新的前沿。2024年5月14日&#xff0c;OpenAI 宣布了其最新旗舰模型 GPT-4o&#xff0c;这不仅是一个简单的版…
阅读更多...
2024CCPC全国邀请赛（郑州）暨河南省赛

2024CCPC全国邀请赛（郑州）暨河南省赛

2024CCPC全国邀请赛&#xff08;郑州站&#xff09;暨河南省赛 一铜一银&#xff0c;虽不是线下第一次参赛但是第一次拿xcpc奖牌&#xff0c;还有个国赛奖真是不戳。感谢学长&#xff0c;感谢队友&#xff01; 虽然遗憾没有冲到省赛金&#xff0c;不过还有icpc商丘&#xff08…
阅读更多...
HTTP基础概念和HTTP缓存技术

HTTP基础概念和HTTP缓存技术

什么是HTTP HTTP是超文本传输协议&#xff0c;主要分为三个部分&#xff1a;超文本、传输、协议。 超文本是指&#xff1a;文字、图片、视频的混合体。传输是指&#xff1a;点与点之间的信息通信。协议是指&#xff1a;通信时的行为规范或约定 HTTP常见字段 字段名 解释 例…
阅读更多...
Android存储文件路径的区别

Android存储文件路径的区别

一、Android存储简介 Android系统分为内部存储和外部存储 从Android6.0开始不断在更新存储权限 外部存储路径的开头&#xff1a;storage/emulated/0 内部存储文件路径的开头&#xff1a;/data/user/0/应用的包名&#xff08;packageName&#xff09; 在设备上对应的目录为/data…
阅读更多...
Leetcode2105. 给植物浇水 II

Leetcode2105. 给植物浇水 II

Every day a Leetcode 题目来源&#xff1a;2105. 给植物浇水 II 解法1&#xff1a;双指针 设 Alice 当前下标为 i&#xff0c;初始化为 0&#xff0c;水量为 a&#xff0c;初始化为 capacityA&#xff1b;Bob 当前下标为 j&#xff0c;初始化为 n-1&#xff0c;水量为 b&am…
阅读更多...
flutter开发实战-compute将工作交由isolate处理

flutter开发实战-compute将工作交由isolate处理

flutter开发实战-compute将工作交由isolate处理 最近查看flutter文档时候&#xff0c;看到了compute可以将工作交由isolate处理。通过 Flutter 提供的 compute() 方法将解析和转换的工作移交到一个后台 isolate 中。这个 compute() 函数可以在后台 isolate 中运行复杂的函数并…
阅读更多...
string功能介绍（普及版）

string功能介绍（普及版）

目录 1。初始化&#xff08;好几种方式&#xff09;&#xff0c;npos和string的使用说明 2。string的拷贝&#xff0c;隐式类型转换&#xff0c;[]&#xff0c;size&#xff0c;iterator&#xff0c;begin&#xff0c;end&#xff0c;reverse&#xff0c;reverse_iterator&am…
阅读更多...
回归预测 | Matlab实现DBO-ESN蜣螂算法优化回声状态网络多输入单输出回归预测

回归预测 | Matlab实现DBO-ESN蜣螂算法优化回声状态网络多输入单输出回归预测

回归预测 | Matlab实现DBO-ESN蜣螂算法优化回声状态网络多输入单输出回归预测 目录 回归预测 | Matlab实现DBO-ESN蜣螂算法优化回声状态网络多输入单输出回归预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现DBO-ESN蜣螂算法优化回声状态网络多输入单输出…
阅读更多...
图像融合-下游任务（目标检测、实例分割、深度估计、局部区域细节放大）

图像融合-下游任务（目标检测、实例分割、深度估计、局部区域细节放大）

下游任务： 采用目标检测、实例分割和深度估计的下游任务来验证图像融合结果质量。 文章目录 下游任务：1.目标检测2.实例分割3.深度估计局部细节放大工具Update1.目标检测 YOLOv8：https://github.com/ultralytics/ultralytics 步骤内容第一步下载项目到本地第二步安装READ…
阅读更多...
20232810 2023-2024-2 《网络攻防实践》实验九

20232810 2023-2024-2 《网络攻防实践》实验九

一、实践内容 1.1 反汇编 1.1.1 编程原理 编程的原理是一套指导软件开发和维护的概念、原则和实践&#xff0c;包括抽象以简化复杂系统、模块化以分解程序、封装以隐藏内部状态、继承以共享特性、多态以允许不同响应、算法和数据结构以组织计算和存储、控制结构以控制流程、…
阅读更多...
Spring Cloud系列—Spring Cloud Gateway服务网关的部署与使用指南

Spring Cloud系列—Spring Cloud Gateway服务网关的部署与使用指南

Gateway网关 文章目录 Gateway网关1. 网关基本简介1.1 什么是网关1.2 为什么需要网关&#xff1f; 2. 快速搭建gateway网关2.1 创建新模块2.2 引入依赖2.3 编写启动类2.4 配置路由规则2.5 测试 3. 路由过滤4. 过滤器4.1 简介4.2 网关过滤器4.2.2 种类 4.3 自定义过滤器4.3.1 自…
阅读更多...
最新文章

Copyright @ 2022~2023