栈和队列的动态实现(C语言实现)

这篇具有很好参考价值的文章主要介绍了栈和队列的动态实现(C语言实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

栈和队列的动态实现(C语言实现),数据结构与算法,c语言,开发语言,数据结构,算法,链表

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍑栈

🍍栈的含义

栈是一种特殊类型的线性表,它的特点是仅允许在其一端进行插入(压入)和删除(弹出)操作。这一端被称为栈顶,而相对的另一端则被称为栈底。栈通常遵循“后进先出”(LIFO)的原则,意味着新加入的元素总是位于栈顶,而要访问或移除的元素必须从前部移除。

🍍栈的结构

栈和队列的动态实现(C语言实现),数据结构与算法,c语言,开发语言,数据结构,算法,链表

栈的结构就是如图片中的形容的类似,满足先进后出

🍍栈的实现

🍌栈的补充条件

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

typedef int STDatetype;//方便后续数据不只是int,也可以方便的换其他类型

typedef struct Stack//利用结构体来定义栈
{
	STDatetype* a;
	int top; 
	int capacity;
}ST;


int main()
{
	ST st;
	STInia(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	printf("\n");

	STDestroy(&st);

	return 0;
}

🍌初始化栈

void STInia(ST* ps)
{
	assert(ps);
	ps->top = ps->capacity = 0;
	ps->a = NULL;
}

🍌入栈

void STPush(ST* ps, STDatetype x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = 2;
		}
		else
		{
			newcapacity = newcapacity * 2;
		}

		STDatetype* tem = (STDatetype*)realloc(ps->a, sizeof(STDatetype) * newcapacity);
		if (tem == NULL)
		{
			perror("realloc  fail");
			exit(-1);
		}

		ps->a = tem;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}

(1)之所以在这里不用malloc创建空间,是因为后面还要用realloc进行扩容,所以就直接用realloc进行空间的创建。
(2)在ps->top和ps->capacity相等时进行扩容,在这里进行了判断,有两种情况。第一种是ps->capacity等于0,那就得先创建空间。第二种是ps->capacity不为0,就直接扩容为原来2倍的空间

🍌出栈

void STPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//判断数据是否为空

	(ps->top)--;

}

🍌获取栈顶元素

STDatetype STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);//判断是否为空

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

🍌获取栈中有效元素的个数

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

在栈中数据个数其实就是ps->top

🍌检查栈是否为空

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

如果为空就返回1,不为空就返回0

🍌销毁栈

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

🍍栈的整体代码的实现

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

typedef int STDatetype;

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

void STInia(ST* ps)
{
	assert(ps);
	ps->top = ps->capacity = 0;
	ps->a = NULL;
}

void STDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDatetype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = 2;
		}
		else
		{
			newcapacity = ps->capacity * 2;
		}

		STDatetype* tem = (STDatetype*)realloc(ps->a, sizeof(STDatetype) * newcapacity);
		if (tem == NULL)
		{
			perror("realloc  fail");
			exit(-1);
		}

		ps->a = tem;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	(ps->top)++;
}


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

	(ps->top)--;

}

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool STEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

STDatetype STTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);

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


int main()
{
	ST st;
	STInia(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st))
	{
		printf("%d ", STTop(&st));
		STPop(&st);
	}

	printf("\n");

	STDestroy(&st);

	return 0;
}

🍑队列

🍍队列的含义

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

🍍队列的结构

栈和队列的动态实现(C语言实现),数据结构与算法,c语言,开发语言,数据结构,算法,链表

队列和栈有点类似,只不过栈是先进后出,而队列是先进先出

🍍队列的实现

🍌队列的补充条件


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

typedef int QDatetype;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatetype date;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;
///
int main()
{
	Que qq;
	QueueInia(&qq);
	QueuePush(&qq, 1);
	QueuePush(&qq, 2);
	QueuePush(&qq, 3);
	QueuePush(&qq, 4);
	while (!QueueEmpty(&qq))
	{
		printf("%d ", QueueFront(&qq));
		QueuePop(&qq);
	}
	printf("\n");
	return 0;
}

在这个队列中,我是采用了单链表(单向不循环)的结构来实现队列,所以再这里要注意头可能是空指针的问题,在前面我介绍单链表的时候是利用二级指针解决这个问题,而在这里是采用了新的方法,也就是结构体指针,把头和尾重新用一个结构体来定义

🍌初始化队列

void QueueInia(Que* ps)
{
	assert(ps);
	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

🍌队尾入队列

void QueuePush(Que* ps, QDatetype x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc  fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->date = x;

	if (ps->tail == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
	(ps->size)++;
}

🍌队头出队列

void QueuePop(Que* ps)
{
	assert(ps);
	assert(ps->size > 0);

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* cur = ps->head->next;
		free(ps->head);
		ps->head = cur;
	}
	(ps->size)--;
}

🍌获取队列头部元素

QDatetype QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->date;
}

🍌获取队列队尾元素

QDatetype QueueBake(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->tail->date;
}

🍌获取队列中有效元素个数

int QueueSize(Que* ps)
{
	assert(ps);

	return ps->size;
}

🍌检测队列是否为空

bool QueueEmpty(Que* ps)
{
	assert(ps);
	return ps->head == NULL;
}

🍌 销毁队列

void QueueDestroy(Que* ps)
{
	assert(ps);

	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	ps->head = ps->tail = NULL;
	ps->size = 0;
}

🍍队列的整体代码的实现

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

typedef int QDatetype;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDatetype date;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

void QueueInia(Que* ps)
{
	assert(ps);
	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

bool QueueEmpty(Que* ps)
{
	assert(ps);
	return ps->head == NULL;
}


void QueuePush(Que* ps, QDatetype x)
{
	assert(ps);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc  fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->date = x;

	if (ps->tail == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}
	(ps->size)++;
}

void QueuePop(Que* ps)
{
	assert(ps);
	assert(ps->size > 0);

	if (ps->head->next == NULL)
	{
		free(ps->head);
		ps->head = ps->tail = NULL;
	}
	else
	{
		QNode* cur = ps->head->next;
		free(ps->head);
		ps->head = cur;
	}
	(ps->size)--;
}

QDatetype QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->date;
}

QDatetype QueueBake(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->tail->date;
}

int QueueSize(Que* ps)
{
	assert(ps);

	return ps->size;
}

void QueueDestroy(Que* ps)
{
	assert(ps);

	QNode* cur = ps->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	ps->head = ps->tail = NULL;
	ps->size = 0;
}


int main()
{
	Que qq;
	QueueInia(&qq);
	QueuePush(&qq, 1);
	QueuePush(&qq, 2);
	QueuePush(&qq, 3);
	QueuePush(&qq, 4);
	while (!QueueEmpty(&qq))
	{
		printf("%d ", QueueFront(&qq));
		QueuePop(&qq);
	}
	printf("\n");
	return 0;
}

队列和栈我就不详细介绍了,如果有需要可以看我写的这篇博客:单链表

本期的内容就结束了,文章有错误的地方欢迎大家指正!!!

栈和队列的动态实现(C语言实现),数据结构与算法,c语言,开发语言,数据结构,算法,链表文章来源地址https://www.toymoban.com/news/detail-833916.html

到了这里,关于栈和队列的动态实现(C语言实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言数据结构——线性表之栈和队列

    为什么会定义栈和队列这两种数据结构呢? 原因在于: 之所以会定义栈和队列这样的数据结构 是因为他们有两大特性 : 第一: 他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。 比如: 栈用于解决迷宫问题,就

    2023年04月11日
    浏览(110)
  • 【数据结构】实现栈和队列

    (1)栈的概念 栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底 。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶。 出

    2024年02月11日
    浏览(42)
  • 数据结构|栈和队列以及实现

    栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和数据删除的一端称为栈顶,另一端称为栈顶。 栈中的数据元素遵循后进先出的原则,简称LIFO(Last In First Out)。 压栈:栈的插入操作叫做进栈/压栈/入栈, 入数据在栈顶 。 出栈:栈

    2024年02月09日
    浏览(43)
  • 【数据结构】栈和队列的模拟实现

    前言:前面我们学习了单链表并且模拟了它的实现,今天我们来进一步学习,来学习栈和队列吧!一起加油各位,后面的路只会越来越难走需要我们一步一个脚印! 💖 博主CSDN主页:卫卫卫的个人主页 💞 👉 专栏分类:数据结构 👈 💯代码仓库:卫卫周大胖的学习日记💫 💪关

    2024年02月05日
    浏览(44)
  • 数据结构(Java实现)-栈和队列

    栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 先进后出 栈的使用 栈的模拟实现 上述的主要代码 改变元素的序列 将递归转化为循环 比如:逆序打印链表 结果如下 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表

    2024年02月10日
    浏览(40)
  • 数据结构基础5:栈和队列的实现。

    1.基本概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:栈

    2024年02月13日
    浏览(39)
  • 数据结构——Java实现栈和队列

    (1)栈是一种线性数据结构 (2)规定只能从栈顶添加元素,从栈顶取出元素 (3)是一种先进后出的数据结构(Last First Out)LIFO Java中可以直接调用方法来实现栈 如何自己写代码来实现栈呢? 先定义一个接口,方便后边进行调用 接下来来实现栈的方法,调用接口,完善方法

    2024年01月20日
    浏览(41)
  • c++实现数据结构栈和队列

    1、栈 头文件 源文件 主函数 2、循环队列 头文件 源文件 主函数 3、思维导图

    2024年02月08日
    浏览(38)
  • 【数据结构】栈和队列的模拟实现(两个方式实现)

    💓作者简介: 加油,旭杏,目前大二,正在学习 C++ , 数据结构 等👀 💓作者主页:加油,旭杏的主页👀 ⏩本文收录在:再识C进阶的专栏👀 🚚代码仓库:旭日东升 1👀 🌹欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖        这一篇博客将学习栈和队列的相关知识, 栈

    2024年02月05日
    浏览(44)
  • 【数据结构和算法】---栈和队列的互相实现

    具体题目可以参考 LeetCode 232. 用栈实现队列 首先要想到的是,队列是一种 先进先出 的结构,而栈是一种 先进后出 的结构。依此 我们可以定义两个栈结构来模拟先进先出 ,既然要定义两个栈,那么为了方便调用,我们可以将这两个栈结构定义在一个结构体中,如下: 实现

    2024年02月03日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包