重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

C语言数据结构——栈和队列-创新互联

目录

成都创新互联专注于勐海网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供勐海营销型网站建设,勐海网站制作、勐海网页设计、勐海网站官网定制、成都微信小程序服务,打造勐海网络公司原创品牌,更为您提供勐海网站排名全网营销落地服务。

前言

一、栈

1.1 栈的概念和结构

1.2 栈的实现

1.2.1 栈的创建及其初始化

1.2.2 入栈/出栈

1.2.3 获取栈顶元素

1.2.4 检查栈是否为空

1.2.5 销毁栈

二、队列

2.1 队列的概念及结构

2.2 队列的实现

2.2.1 队列结构的创建及初始化

2.2.2 插入删除数据

2.2.3 读取头尾数据

2.2.4 判断是否为空

2.2.5 判断存储数据的数量

2.2.6 销毁队列

总结



前言

本篇文章主要带领大家深入了解栈和队列以及相关实现。


一、栈 1.1 栈的概念和结构

栈:栈是一种特殊的线性表,其只允许在一端进行插入和删除的操作,而进行插入删除操作的一端叫栈顶,另一端叫栈底。所以栈中的数据也遵从后进先出原则。

压栈:从栈顶压入数据的操作叫做压栈,也称为进栈或者出栈

出栈:从栈顶删除数据的操作叫做出栈

1.2 栈的实现

栈的实现一般使用数组或者是链表,相对而言,使用数组的优势更大,因为数组尾插尾删的效率高,相当契合栈的要求,而链表尾删需要遍历链表效率相比数组就低了许多。

接下来我们就用数组实现动态栈

1.2.1 栈的创建及其初始化

栈的创建:栈的结构体成员有三个,分别代表数组,栈顶,栈容

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

栈的初始化:我们先开辟4个空间的数组,然后给栈顶,容量赋值

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	STDataType* ptr = (STDataType*)malloc(4 * sizeof(STDataType));
	if (ptr == NULL)//检查开辟是否成功
	{
		perror("malloc");
		exit(-1);
	}
	ps->_a = ptr;
	ps->_top = 0;
	ps->_capacity = 4;
}
1.2.2 入栈/出栈

入栈:入栈需要先检查容量,如果容量满了,就用realloc进行扩容,然后在插入数据即可

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		STDataType* ptr =realloc(ps->_a,ps->_capacity*2*sizeof(STDataType));
		if (ptr == NULL)//检查开辟是否成功
		{
			perror("malloc");
			exit(-1);
		}
		ps->_a = ptr;
		ps->_capacity = ps->_capacity * 2;
	}
	ps->_a[ps->_top] = data;
	ps->_top++;
}

出栈:出栈就很简单了,只需检查栈里是否有数据,无数据则无法删除,然栈顶--即可。

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(StackEmpty(ps));
	ps->_top--;
}
1.2.3 获取栈顶元素

这个需要注意的是,top指向的是栈顶元素的下一个位置,所以想要获取栈顶元素,需要的下标是top-1

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(StackEmpty(ps));
	
	return ps->_a[ps->_top - 1];
}
1.2.4 检查栈是否为空

只需返回top即可,如果top为0则为空

// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->_top;
	
}
1.2.5 销毁栈

释放数组即可

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}
二、队列 2.1 队列的概念及结构

队列:只允许在一端进行插入,在另一端进行删除的特殊线性表,插入的一端叫队尾,删除的一端叫队头,遵从先进先出原则。

2.2 队列的实现

队列一般可以用数组或者链表实现,使用链表的结构更优一些,因为队列需要用到尾插头删,链表的头删和尾插都比数组要优秀。

下面就用链表实现队列

2.2.1 队列结构的创建及初始化

结构的创建:首先是创建链表的节点空间,然后在创建两个指针分别指向链表头和尾,再创建一个size记录队列的有效数据

typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

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

初始化:头尾指针置空,size置为0

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
2.2.2 插入删除数据

插入数据:先给要插入的数据开辟一个新节点,然后只需要考虑一些第一次插入的特殊情况,其他按照链表的尾插即可

//插入数据
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newcode = (QNode*)malloc(sizeof(QNode));
	if (newcode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	
	if (pq->head == NULL)
	{
		newcode->data = x;
		newcode->next = NULL;
		pq->head = pq->tail = newcode;
		pq->size++;
	}
	else
	{
		newcode->data = x;
		newcode->next = NULL;
		pq->tail->next = newcode;
		pq->tail = pq->tail->next;
		pq->size++;
	}
}

删除数据:需要检查是否为空,为空则无法删除,和链表头删类似

//删除数据
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(QueueEmpty(pq));
	QNode* cur = pq->head->next;
	free(pq->head);
	pq->head = cur;
	pq->size--;

}
2.2.3 读取头尾数据

读取头数据:直接读取head指向的数据即可

//读取头个数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(QueueEmpty(pq));
	return pq->head->data;
}

读取尾数据:读取tail指向的数据即可

//读取最后一个数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(QueueEmpty(pq));
	return pq->tail->data;
}
2.2.4 判断是否为空

head和tail为空则为空

//判断是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head && pq->tail;
}
2.2.5 判断存储数据的数量

返回size即可

//判断数据的数量
int QueueSize(Queue* pq)
{
	assert(pq);
	assert(QueueEmpty(pq));
	return pq->size;
}
2.2.6 销毁队列

一个空间一个空间释放即可

//释放空间
void QueueDestroy(Queue* pq)
{
	assert(pq);
	while (pq->head)//一个节点一个节点释放
	{
		QNode* cur = pq->head->next;
		free(pq->head);
		pq->head = cur;
	}
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

总结

以上就是今天要讲的内容,希望铁子们可以有所收货。

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网页题目:C语言数据结构——栈和队列-创新互联
文章地址:http://cqcxhl.cn/article/dchpdh.html

其他资讯

在线咨询
服务热线
服务热线:028-86922220
TOP