首页 > 资讯 > 后端开发 > 其他教程 >C语言浅谈栈与队列的定义与操作

701

分享到

C语言浅谈栈与队列的定义与操作

2024-04-02 19:04:59 701人浏览薄情痞子

摘要

目录栈的定义栈的实现前置初始化栈栈的销毁栈的插入出栈的操作取栈顶元素栈的大小队列的定义队列的基本操作队列的初始化队列的销毁队列的插入队列的删除队列的判空取出队头元素取出队尾元素队列的

栈的定义

栈同样是一种线性表，它的特性是插入元素必须从后面插入，删除元素也是从后面删除，进行数据删除和插入的一端称为栈顶，另一端是栈底。
压栈—就是插入元素
出栈—就是删除元素
它可以用数组实现也可以用链表实现

在这里插入图片描述

但是用数组实现更好，因为链表的插入和删除要进行遍历，而数组可以进行随机访问，从而时间复杂度更低。

栈的实现

前置

栈的元素需要表明容量，还有栈顶


typedef int SDType;
typedef struct Srack
{
	SDType* a;
	int top;
	int capacity;

}ST;

初始化栈

把元素置为空，栈顶在下标为0的位置


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

栈的销毁

不再赘述


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

栈的插入

先判空，如果容量满了，进行增容，把栈顶元素进行赋值，再把栈顶指针加一


void StackPush(ST* ps, SDType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity);
		if (tmp == NULL)
		{
			printf("Realloc fail!\n");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

出栈的操作

栈顶指针减一即可


void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;

}

取栈顶元素

先进行判空，不空的话直接取出栈顶指针指向的元素


SDType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps -> a[ps->top - 1];
}

栈的大小


int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

判断栈是否为空


bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

队列的定义

队列只允许在一段进行插入操作，一段进行删除操作，在队尾进行插入，在队头进行删除

在这里插入图片描述

队列的基本操作

队列的初始化

我们在进行基本操作的时候要用到头指针和尾指针


void QueueInit(Queue* pq)
{
	assert(pq != NULL);
	pq->head = NULL;
	pq->tail = NULL;


}

队列的销毁

将临时指针cur被赋值为head，保存下一个，遍历进行删除，最后把头指针和尾指针进行free


void QueueDestroy(Queue* pq)
{
	assert(pq != NULL);
	Queuenode* cur = pq->head;
	QueueNode* next = cur->next;
	while (cur)
	{
		free(cur);
		cur = next;
		next = next->next;
	}
	pq->head = pq->tail = NULL;
}

队列的插入

队列只能从队尾查，如果开始的时候队头和队尾重合，那就直接进行插入，
如果不，那就找到尾，在尾后边进行插入


void QueuePush(Queue* pq,QDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->data = x;
	newNode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

队列的删除

很简单，删除队尾头元素，先保存下一个，再把队头复制给新的


void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* NewHead = pq->head->next;
	free(pq->head);
	pq->head = NewHead;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

队列的判空

是否队头指向空


bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

取出队头元素


QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

取出队尾元素

先判空


QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;

}

队列的大小

直接遍历就行


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

点个赞把

到此这篇关于C语言 浅谈栈与队列的定义与操作的文章就介绍到这了,更多相关C语言栈与队列内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言浅谈栈与队列的定义与操作

本文链接: https://www.lsjlt.com/news/156368.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C语言浅谈栈与队列的定义与操作

目录栈的定义栈的实现前置初始化栈栈的销毁栈的插入出栈的操作取栈顶元素栈的大小队列的定义队列的基本操作队列的初始化队列的销毁队列的插入队列的删除队列的判空取出队头元素取出队尾元素队列的...

99+

2022-11-12
C语言栈与队列如何定义

今天小编给大家分享一下C语言栈与队列如何定义的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。栈栈的定义栈是一种线性表，但限定这...

99+

2023-06-30
Go语言实现栈与队列基本操作学家

目录一、前言二、实现栈与队列基本操作2.1 栈基本操作2.2 队列基本操作三、用栈实现队列3.1 理论3.2 算法题3.3 思路3.4 代码部分四、用队列实现栈4.1 理论4.2 算...

99+

2022-11-16

Go语言栈队列操作 Go语言栈 Go语言队列
C语言数据结构之队列的定义与实现

目录一、队列的性质二、队列的结构三、代码实现头文件功能函数一、队列的性质上次我们学习栈，了解到栈储存释放数据的方式是：先进后出而队列与其相反，队列是：先进先出，后进后出。二、队...

99+

2022-11-13
C语言数据结构之队列怎么定义与实现

今天小编给大家分享一下C语言数据结构之队列怎么定义与实现的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。一、队列的性质上次我们...

99+

2023-07-02
C语言数据结构之栈与队列的相互实现

目录一、用对列实现栈代码实现二、用栈实现队列代码实现一、用对列实现栈题干要求：细节分析：队列是先进先出；要实现的栈是先进后出。解题思路：假设：先用一个队列储存数据 N 个，...

99+

2022-11-13
C语言编程数据结构栈与队列的全面讲解示例教程

目录一、栈的表示和实现1栈的概念和结构2栈的初始化3压栈(栈顶插入一个数据)4出栈(栈顶删除一个数据)5取栈顶元素6取栈顶元素7判断栈是否为空二、队列的表示和实现1队列的概念及结构2...

99+

2022-11-12