C语言超详细讲解栈与队列实现实例

2024-09-29 08:06:26

1.思考-1

为什么栈用数组来模拟比用链表来模拟更优一些？

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，时间复杂度为O(n)。

2.栈基本操作的实现

2.1 初始化栈

void StackInit(stack*ps)
{
	assert(ps);
	ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4);
	ps->_top = 0;
	ps->_capacity = 4;
}

2.2 入栈

void StackPush(stack*ps, StackDate x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		stack*tmp = (StackDate*)realloc(ps, sizeof(StackDate)*(ps->_capacity) * 2);
		if (NULL == tmp)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps = tmp;
		ps->_capacity *= 2;
	}
	ps->_a[ps->_top] = x;
	ps->_top++;
}

2.3 出栈

void StackPop(stack*ps)
{
	assert(ps);
	assert(!StackIsEmpty(ps));
	--ps->_top;
}

注意： 出栈并不是真正意义上的删除数据，而是将_top向后挪动了一个位置。

2.4 获取栈顶数据

StackDate StackTop(stack*ps)
{
	assert(ps);
	assert(!StackIsEmpty(ps));
	return ps->_a[ps->_top - 1];
}

2.5 获取栈中有效元素个数

int StackSize(stack*ps)
{
	assert(ps);
	return ps->_top;
}

2.6 判断栈是否为空

bool StackIsEmpty(stack*ps)
{
	assert(ps);
	return ps->_top == 0;
}

2.7 销毁栈

void StackDestory(stack*ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

3.测试

3.1测试

void test()
{
	//插入数据
	stack  st;
	StackInit(&st);
	StackPush(&st,1);
	StackPush(&st,2);
	StackPush(&st,3);
	StackPush(&st,4);
	while (!StackIsEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");

	//获取栈顶数据
	StackPush(&st, 1);
	StackPush(&st, 2);
	printf("%d ", StackTop(&st));
	printf("\n");

	//栈中有效数据个数
	printf("%d ", StackSize(&st));

	//销毁栈
	StackDestory(&st);
}

3.2测试结果

4.思考-2

为什么队列用链表模拟比数组模拟更加合适？

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价小。

5.队列的基本操作实现

5.1 初始化队列

void QueueInit(Queue*pq)
{
	assert(pq);
	pq->_head = pq->_tail = NULL;
}

5.2 队尾入队列

void QueuePush(Queue*pq, QueueDate x)
{
	assert(pq);
	QueueNode*newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newnode)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	if (NULL == pq->_tail)
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		pq->_tail->next = newnode;
		pq->_tail = newnode;
	}
}

5.3 队头出队列

void QueuePop(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	if (NULL == pq->_head->next)
	{
		free(pq->_head);
		pq->_head = pq->_tail = NULL;

	}
	else
	{
		QueueNode*next = pq->_head->next;
		free(pq->_head);
		pq->_head = next;
	}
}

代码分析：

5.4 队列中有效元素的个数

int QueueSize(Queue*pq)
{
	assert(pq);
	int count = 0;
	QueueNode*cur = pq->_head;
	while (cur)
	{
		++count;
		cur = cur->next;
	}
	return count;
}

5.5 判断队列是否为空

bool QueueIsEmpty(Queue*pq)
{
	assert(pq);
	return pq->_head == NULL;
}

5.6 获取队头数据

QueueDate QueueFront(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	return pq->_head->val;
}

5.7 获取队尾的数据

QueueDate QueueBack(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	return pq->_tail->val;
}

5.8 销毁队列

void QueueDestory(Queue*pq)
{
	assert(pq);
	while (pq->_head)
	{
		if (pq->_head == pq->_tail)
		{
			free(pq->_head);
			pq->_head = pq->_tail = NULL;
		}
		else
		{
			QueueNode*next = pq->_head->next;
			free(pq->_head);
			pq->_head = next;
		}
	}
}

注意： 和队头出队列一样分析。

6.测试

6.1测试

void test1()
{
	//插入数据
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//有效数据的个数
	printf("%d ", QueueSize(&q));
	printf("\n");

	//获取队头数据
	printf("%d",QueueFront(&q));
	printf("\n");

	//获取队尾数据
	printf("%d",QueueBack(&q));
	printf("\n");

	//出队
	QueuePop(&q);
	while (!QueueIsEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	//销毁
	QueueDestory(&q);
	printf("\n");
}

6.2 测试结果

今天数据结构栈与队列的相关知识点就分享到这里了，感谢你的浏览，如果对你有帮助的话，可以给个关注，顺便来个赞。

到此这篇关于C语言超详细讲解栈与队列实现实例的文章就介绍到这了,更多相关C语言栈与队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言用栈和队列实现的回文检测功能示例

本文实例讲述了C语言用栈和队列实现的回文功能.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h>//内存分配头文件 #include<math.h>//在math.h中已定义OVERFLOW的值为3 #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typede
C语言浅谈栈与队列的定义与操作

目录栈的定义栈的实现前置初始化栈栈的销毁栈的插入出栈的操作取栈顶元素栈的大小队列的定义队列的基本操作队列的初始化队列的销毁队列的插入队列的删除队列的判空取出队头元素取出队尾元素队列的大小栈的定义栈同样是一种线性表,它的特性是插入元素必须从后面插入,删除元素也是从后面删除,进行数据删除和插入的一端称为栈顶,另一端是栈底. 压栈-就是插入元素出栈-就是删除元素它可以用数组实现也可以用链表实现但是用数组实现更好,因为链表的插入和删除要进行遍历,而数组可以
C语言编程数据结构的栈和队列

目录栈数组实现标题全部代码 Stack_array.c Stack_array.h 初始化数组栈满栈后扩容是否为空栈压栈和退栈链表实现 stack_chain.h stack_chain.c 整个压栈流程整个弹栈流程出栈情况队列队列的实现 queue_chain.h queue_chain.c 一个结构体类型用于维护这个队列概念流程图入队列的实现出队列的实现是否空队栈栈是一种以后进先出为顺序对对象进行添加或删除的数据结构对栈进行形象记忆就像是桌子上的一堆书或一
深入浅析C语言中堆栈和队列

1.堆和栈 (1)数据结构的堆和栈堆栈是两种数据结构. 栈(栈像装数据的桶或箱子):是一种具有后进先出性质的数据结构,也就是说后存放的先取,先存放的后取.这就如同要取出放在箱子里面底下的东西(放入的比较早的物体),首先要移开压在它上面的物体(放入的比较晚的物体). 堆(堆像一棵倒过来的树):是一种经过排序的树形数据结构,每个结点都有一个值.通常所说的堆的数据结构,是指二叉堆.堆的特点是根结点的值最小(或最大),且根结点的两个子树也是一个堆.由于堆的这个特性,常用来实现优先队列,堆的存取是随意,
C语言中栈和队列实现表达式求值的实例

C语言中栈和队列实现表达式求值的实例实现代码: #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define STACK_SIZE 20 #define STACK_INCREMENT 10 #define QUEUE_SIZE 20 typedef int Status; typedef char StackElemtype; typedef struct Stack{ StackElemty
C语言数据结构进阶之栈和队列的实现

目录栈的实现: 一.栈的概念和性质二.栈的实现思路三.栈的相关变量内存布局图四.栈的初始化和销毁五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空队列的实现: 一.队列的概念和性质二.队列的实现思路三.队列相关变量的内存布局图四.队列的初始化和销毁五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空总结栈的实现: 一.栈的概念和性质栈(stack)又名
C语言编程数据结构栈与队列的全面讲解示例教程

目录一.栈的表示和实现 1栈的概念和结构 2栈的初始化 3压栈(栈顶插入一个数据) 4出栈(栈顶删除一个数据) 5取栈顶元素 6取栈顶元素 7判断栈是否为空二.队列的表示和实现 1队列的概念及结构 2队列的实现 3队列初始化 4入队(队尾插入一个数据) 5出队(队头删除一个数据) 6取队头数据 7取队尾数据 8计算队列中数据个数 9判断队列是否为空 10销毁队列总结一.栈的表示和实现 1栈的概念和结构栈:一种特殊的线性表(逻辑上数据是连着放的),其只允许在固定的一端进行插入和删除操作.
C语言表、栈和队列详解及实例代码

C语言表.栈和队列详解表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指
C语言超详细讲解栈与队列实现实例

目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用
C语言超详细讲解栈的实现及代码

目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码 Stack.h 文件 Stack.c 文件 Test.c 文件前言栈的概念栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入
C语言超详细讲解队列的实现及代码

目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化队列销毁入队列出队列队列判空获取队列元素个数获取队列头部元素获取队列尾部元素总代码 Queue.h 文件 Queue.c 文件 Test.c 文件前言队列的概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为队头队列和前文所学的栈
C语言超详细讲解函数栈帧的创建和销毁

目录 1.本节目标 2.相关寄存器 3.相关汇编指令 4.什么是函数栈帧 5.什么是调用堆栈 6.函数栈帧的创建和销毁 (1).main函数栈帧的创建与初始化 (2).main函数的核心代码 (3).Add函数的调用过程 (4).Add函数栈帧的销毁 (5).调用完成 7.对开篇问题的解答 1.本节目标 C语言绝命七连问,你能回答出几个? 局部变量是如何创建的?为什么局部变量不初始化其内容是随机的?有些时候屏幕上输出的"烫烫烫"是怎么来的?函数调用时参数时如何传递的?传参的顺序是怎样的
C语言超详细讲解算法的时间复杂度和空间复杂度

目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit
C语言超详细解析函数栈帧

目录一.前面二.预备知识三.栈帧创建与销毁四.总结一.前面本章将以汇编视角看函数栈帧的内存是如何使用与回收的,为了降低汇编语言的理解成本,以图示的方式讲解每一步汇编指令所带来的效果,来逐步展示函数栈帧的形成与销毁的整个过程. 展示环境:win10 && vs2019 二.预备知识这些预备知识理解与否对本篇文章并无很大关系,之所以预备这些知识是为了让读者能够更加相信函数栈帧的形成与销毁过程就是如此. 栈区:内存四区之一,内存为了使用和管理,被划分为四部分,其中栈区就是内存被划分
C语言超详细讲解指针的概念与使用

目录一.指针与一维数组 1. 指针与数组基础 2. 指针与数组 3. 一个思考二.指针与字符串三.指针和二维数组 1. 指针数组与数组指针 2. 指针数组 3. 数组指针一.指针与一维数组 1. 指针与数组基础先说明几点干货: 1. 数组是变量的集合,并且数组中的多个变量在内存空间上是连续存储的. 2. 数组名是数组的入口地址,同时也是首元素的地址,数组名是一个地址常量,不能更改. 3. 数组的指针是指数组在内存中的起始地址,数组元素的地址是指数组元素在内存中的其实地址. 对于第一点数
C语言示例代码讲解栈与队列

目录栈栈的定义顺序栈顺序栈的定义顺序栈的初始化顺序栈的入栈顺序栈的出栈取顺序栈的栈顶元素链栈队列队列的定义队列的顺序表达与实现队列顺序存储结构假溢出循环队列循环队列的初始化循环队列的入队循环队列的出队链队列链栈的初始化链栈的入队链栈的出队上文详细的讲解了顺序表与链表的实现,相信大家在顺序表与链表的指基础上,很容易就能学会站和队列,废话不多说,我们马上开始! 栈栈的定义栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作假设栈 [s =
C语言超详细讲解线性表

目录 1. 顺序表 1.1 管理结点 1.2 顺序表的插入 1.3 顺序表的删除 1.4 顺序表的扩容 2. 链表 2.1 定义 2.2 头部插入 2.3 尾部插入 2.4 任意位置插入 2.5 任意位置删除 2.6 虚头结点 1. 顺序表顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构.此种存储方式使得顺序表的物理结构与逻辑结构都是连续的. 与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用ulimit -s查看系统限制的大小,单位为KB),因此顺序表往往使用
C语言超详细讲解链接器

目录 1 什么是链接器 2 声明与定义 3 命名冲突 3.1 命名冲突 3.2 static修饰符 4 形参.实参.返回值 5 检查外部类型 6 头文件 1 什么是链接器典型的链接器把由编译器或汇编器生成的若干个目标模块,整合成一个被称为载入模块或可执行文件的实体–该实体能够被操作系统直接执行. 链接器通常把目标模块看成是由一组外部对象组成的.每个外部对象代表着机器内存中的某个部分,并通过一个外部名称来识别.因此,==程序中的每个函数和每个外部变量,如果没有被声明为static,就都是一个外部