1. Toy模板网首页
  2. > Toy博客

栈和队列的动态实现（C语言实现）

9月前 作者：悦心无谓 分类：Toy博客 阅读(25) 违法举报

这篇具有很好参考价值的文章主要介绍了栈和队列的动态实现（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语言数据结构——线性表之栈和队列

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

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

    2023年04月11日
    浏览(113)
  • 数据结构|栈和队列以及实现

    数据结构|栈和队列以及实现

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

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

    【数据结构】实现栈和队列

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

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

    【数据结构】栈和队列的模拟实现

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

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

    数据结构（Java实现）-栈和队列

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

    2024年02月10日
    浏览(43)
  • c++实现数据结构栈和队列

    c++实现数据结构栈和队列

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

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

    数据结构——Java实现栈和队列

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

    2024年01月20日
    浏览(43)
  • 数据结构基础5：栈和队列的实现。

    数据结构基础5：栈和队列的实现。

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

    2024年02月13日
    浏览(39)

  • 【数据结构】栈和队列的模拟实现（两个方式实现）

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

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

    【数据结构和算法】---栈和队列的互相实现

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

    2024年02月03日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包