c语言实现栈(顺序栈,链栈)-Toy模板网

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

c语言实现栈(顺序栈,链栈)

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解用c语言实现:“数据结构之"栈”,分别从"顺序栈"和"链栈"的接口讲解.
金句分享:
✨不是每一场雨后都有彩虹,但是晴天总是会到来!✨

前言

栈

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

c语言实现栈(顺序栈,链栈)

"栈"的常见接口实现

InitST:初始化栈
STPush:入栈
STPop:出栈
STEmpty:判空(判断是否为空栈)
PrintSTTop:打印栈顶元素
STTop:返回栈顶元素(返回值类型:stacktype)

一、顺序栈

"顺序栈"的类型定义

如果友友们学过顺序表,这种类型可以随便拿捏.😄😄

代码:

typedef struct stack
{
	stacktype* data;//一个指向连续内存空间的指针
	int top;//记录栈顶元素的下标
	int capacaity;
}ST;

c语言实现栈(顺序栈,链栈)

1.1 初始化栈

top指针:
由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.

capacaity :
同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.

void InitST(ST* ps)
{
	assert(ps);
	ps->top = -1;//此时栈中无数据
	ps->capacaity = 4;//设置初始最大容量
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

此处初始化后:
c语言实现栈(顺序栈,链栈)

1.2 入栈(压栈,向"栈"中插入数据)

学到这里(顺序表和链表),对于"栈"的压栈操作很简单.

由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.
top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.
将新元素插入.此时刚好top为新的栈顶的下标.

图解:
c语言实现栈(顺序栈,链栈)

代码:

void STPush(ST* ps, stacktype x)//压栈
{
	assert(ps);
	if (ps->top+1 == ps->capacaity)//检查"栈"满
	{
		ps->capacaity *= 2;//扩容
		stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if(tmp == NULL)
		{
			printf("增容失败\n");
		}
		ps->data = tmp;
	}
	//将"栈顶指针"指向待插入位置
	ps->top++;
	//将元素压栈
	ps->data[ps->top] = x;
	
}

1.3 “出栈”,删除"栈"中的数据

步骤:

删除数据时,需要判断"栈"是否为空.
将top向前(下)移动一位,即表示有效数据位减1.

代码:

void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

1.4 判空(判断"栈"是否为空)

当栈为空时,top为初始状态-1.

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{
	assert(ps);
	if (ps->top == -1)
	{
		return true;
	}
	return false;
}

1.5 打印"栈顶"元素

void PrintSTTop(ST* ps)
{
	assert(ps);
	printf("%d", ps->data[ps->top]);
}

1.6 返回"栈顶"元素

stacktype STTop(ST* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data[ps->top];
}

1.7 "栈"的销毁

栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.

void STDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}

二、链栈

"链栈"的类型定义

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;

其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.

同时为了提高效率:

链表	分析
尾插，尾删	效率低，因为需要找尾巴
头插，头插	效率高,只需要改变头指针的指向

综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.

2.1 初始化"链栈"

对于链表实现的栈,如果不带头结点:
我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)

//创建一个栈顶指针,并完成初始化
SLStackNode* SLStack = NULL;

如果是带头结点的单链表:
我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.

//stack.c
SLStackNode* InitStack()
{
	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
	if (newnode == NULL)
	{
		perror("newnode malloc fail");
	}
	return newnode;
}

//test.c
SLStackNode* SLStack = InitStack();

2.2 入栈(压栈,向"栈"中插入数据)

步骤:(与单链表的头插类似)

创建一个新节点.
将新节点的next指针指向原"栈"的顶点
更新栈顶指针(将栈顶指针指向新节点)

图解:
c语言实现栈(顺序栈,链栈)

代码:

//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
	assert(pps);
	//获取新的结点
	SLStackNode* newnode = BuyNode(x);
	newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点
	*pps = newnode;//更新栈顶
}

2.3 “出栈”,删除"栈"中的数据

步骤:(与链表的头删操作类似)

判空,防止空链栈的删除操作
记录原栈顶元素的地址.
更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).
释放原栈顶空间

图解:
c语言实现栈(顺序栈,链栈)

void STPop(SLStackNode** pps)//出栈
{
	assert(pps);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pps);//防止空链栈的删除操作
	SLStackNode* head = *pps;//记录栈顶元素的地址
	*pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点
	free(head);//释放原栈顶空间
}

2.4 判空(判断"栈"是否为空)

链栈(不带头版本的)的初始状态是栈顶指针指向NULL.

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
	if (ps == NULL)
	{
		return true;
	}
	else
		return false;
}

2.5 打印"栈顶"元素

栈顶元素即,栈顶指针指向的结点的数据域.

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
	assert(ps);
	printf("%d ", ps->data);
}

2.6 返回"栈顶"元素

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data;
}

2.7 返回"链栈"的长度(有效数据的个数)

遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).

代码:

int LengthStack(SLStackNode* ps)
{
	int count = 0;
	if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素
	{
		return 0;
	}
	SLStackNode* tail = ps;//代替头指针遍历
	while (ps)
	{
		count++;//如果该结点不为空,则有效数据个数+1
		ps = ps->next;
	}
	return count;//返回有效数据的个数
}

2.8 "链栈"的销毁

与"链表"销毁类似.

void STDestory(SLStackNode* ps)//栈的销毁
{
	SLStackNode* del = ps;
	SLStackNode* next = ps;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;

	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

总结:

虽然链表和顺序表可以实现"栈",并且效率上,二者差距不大.

但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.

寄存器:

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).

数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.

🌰栗子:
c语言实现栈(顺序栈,链栈)

综上,还是稍微建议使用顺序栈有一点点优势.

希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦！
最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。
c语言实现栈(顺序栈,链栈) 文章来源地址https://www.toymoban.com/news/detail-446931.html

总代码

"顺序栈"总代码

声明区(stack.h)

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef  int stacktype;
typedef struct stack
{
	stacktype* data;
	int top;
	int capacaity;
}ST;
void InitST(ST* ps);
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
void PrintSTTop(ST* ps);//打印栈顶元素

bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁

接口实现区( stack.c)

#include "stack.h"
//初始化栈
void InitST(ST* ps)
{
	assert(ps);
	ps->top = -1;
	ps->capacaity = 4;
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

//压栈
void STPush(ST* ps, stacktype x)
{
	assert(ps);
	if (ps->top+1 == ps->capacaity)
	{
		ps->capacaity *= 2;
		stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if(tmp == NULL)
		{
			printf("增容失败\n");
		}
		ps->data = tmp;
	}
	ps->top++;
	ps->data[ps->top] = x;
	
}

//出栈
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

//打印栈顶元素
void PrintSTTop(ST* ps)
{
	assert(ps);
	printf("%d", ps->data[ps->top]);
}

//判断是否为空栈,是空返回真
bool STEmpty(ST* ps)
{
	assert(ps);
	if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1;
	{
		return true;
	}
	return false;
}

//返回栈顶元素
stacktype STTop(ST* ps)
{
	assert(ps);
	return ps->data[ps->top];//反追栈顶元素
}

//栈的销毁
void STDestory(ST* ps)
{
	assert(ps);
	free(ps->data);//释放栈空间
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}

测试区(test.c)

#include "stack.h"
void test1()
{
	ST st1;
	InitST(&st1);
	STPush(&st1, 1);//压栈
	STPush(&st1, 2);//压栈
	STPush(&st1, 3);//压栈
	STPush(&st1, 4);//压栈
	int a=STTop(&st1);
	printf("栈顶元素为%d\n", a);
	while (!STEmpty(&st1))
	{
		PrintSTTop(&st1);//打印栈顶元素
		STPop(&st1);
	}

	STDestory(&st1);
	
}
int main()
{
	test1();
	return 0;
}

"链栈"总代码:

声明区(SLStack.h)

#pragma once

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

typedef int stacktype;
// 链栈的类型
typedef struct SLStackNode
{
    stacktype data;
    struct SLStackNode* next;
}SLStackNode;


//SLStackNode* InitStack();

void STPush(SLStackNode** pps, stacktype x);//压栈
void STPop(SLStackNode** pps);//出栈
void PrintSTTop(SLStackNode* ps);//打印栈顶元素

bool STEmpty(SLStackNode* ps);//判断是否为空栈
stacktype STTop(SLStackNode* ps);//返回栈顶元素

int LengthStack(SLStackNode* ps);//返回栈的长度

void STDestory(SLStackNode* ps);//栈的销毁

接口实现区(SLStack.c)

#include "SLStack.h"

//SLStackNode* InitStack()
//{
//	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
//	if (newnode == NULL)
//	{
//		perror("newnode malloc fail");
//	}
//	return newnode;
//}

SLStackNode* BuyNode(stacktype x)//创建新结点
{
	SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode));
	assert(newnode);//防止申请结点失败
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}


//入栈
void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插
{
	assert(pps);
	//获取新的结点
	SLStackNode* newnode = BuyNode(x);
	newnode->next = *pps;
	*pps = newnode;
}

void STPop(SLStackNode** pps)//出栈
{
	assert(pps);//二级指针不可能为空,如果为空就一定是传错了
	assert(*pps);//防止空链栈的删除操作
	SLStackNode* head = *pps;//记录栈顶元素的地址
	*pps = (*pps)->next;//将栈顶向下移动一位
	free(head);//释放栈顶空间
}

void PrintSTTop(SLStackNode* ps)//打印栈顶元素
{
	assert(ps);
	printf("%d ", ps->data);
}

bool STEmpty(SLStackNode* ps)//判断是否为空栈
{
	if (ps == NULL)
	{
		return true;
	}
	else
		return false;
}

stacktype STTop(SLStackNode* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data;
}

int LengthStack(SLStackNode* ps)
{
	int count = 0;
	if (ps == NULL)
	{
		return 0;
	}
	SLStackNode* tail = ps;
	while (ps)
	{
		count++;
		ps = ps->next;
	}
	return count;
}

void STDestory(SLStackNode* ps)//栈的销毁
{
	SLStackNode* del = ps;
	SLStackNode* next = ps;//用于记录下一个结点
	while (next)
	{
		next = next->next;
		free(del);
		del = next;

	}
	//保持习惯置空
	next == NULL;
	del = NULL;
}

测试区(test.c)

#include "SLStack.h"

void test1()
{
	SLStackNode* SLStack = NULL;
	//SLStackNode* SLStack = InitStack();

	STPush(&SLStack, 1);//压栈
	STPush(&SLStack, 2);//压栈
	STPush(&SLStack, 3);//压栈
	STPush(&SLStack, 4);//压栈
	STPush(&SLStack, 5);//压栈
	STPush(&SLStack, -1);//压栈
	STPush(&SLStack, -2);//压栈
	int a = STTop(SLStack);
	printf("栈顶元素为%d\n", a);

	int length = LengthStack(SLStack);
	printf("链表的长度为:%d\n", length);

	while (!STEmpty(SLStack))
	{
		PrintSTTop(SLStack);//打印栈顶元素
		STPop(&SLStack);
	}
	
	STDestory(SLStack);

}
int main()
{
	test1();
	return 0;
}