史上最强数据结构----轻松拿捏栈的两种模拟实现

x33g5p2x  于2022-03-29 转载在 其他  
字(3.2k)|赞(0)|评价(0)|浏览(350)

1. 栈的概念及结构

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

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

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

注意:数据结构中的栈和我们C语言中的栈有什么关系吗?

前者是一种数据结构,用来存储数据。后者是操作系统中内存划分的一个区域,叫做栈,用来函数调用时,建立栈帧。

问:当入栈顺序是1 2 3 4的时候,出栈顺序一定是4 3 2 1吗?

答:不一定是,因为有可能是1入栈之后接着就出栈了,2、3、4也同样如此,此时的出栈顺序是1 2 3 4。实际上是有很多种出栈方式,后进先出是相对的。

2. 栈的实现

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

栈的代码实现:

2.1 数组栈的实现

第一种:数组栈的实现(推荐)

Stack.h文件代码:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的位置
	int capacity;//容量
}ST;
void StackInit(ST*ps);
void StackDestory(ST* ps);
void StackPush(ST* ps,STDataType x);
void StackPop(ST* ps);
bool StackEmpty(ST* ps);
int SizeStack(ST* ps);
STDataType StackTop(ST* ps);

Stack.c文件代码:

#include"Stack.h"
void StackInit(ST* ps)//栈的初始化
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void StackDestory(ST*ps)//栈的销毁
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity =ps->top =  0;
}
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//满了进行扩容
	{
		int newCapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
		STDataType*new = (STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);
		if (new == NULL)
		{
			printf("fail malloc\n");
			exit(-1);
		}
		ps->a = new;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top++] = x;
}
void StackPop(ST* ps)//出栈
{
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
	assert(ps);
	return ps->top == 0;
}
STDataType StackTop(ST* ps)//取栈顶元素
{
	assert(ps);
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}
int SizeStack(ST* ps)//求栈的元素数量
{
	assert(ps);
	return ps->top;
}

2.2 链表栈的实现

第二种:链表栈的实现

链表栈的实现在此处是运用了单链表(有哨兵位)作为载体,入栈的位置采取的是单链表的头部,即哨兵位的后面的位置,出栈出的也是哨兵位后面的节点。

Stack.h文件代码:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct StackNode
{
	STDataType val;
	struct StackNode* next;
}StackNode;
StackNode* StackInit();
void StackDestory(StackNode* ps);
void StackPush(StackNode* ps,STDataType x);
void StackPop(StackNode* ps);
bool StackEmpty(StackNode* ps);
int SizeStack(StackNode* ps);
STDataType StackTop(StackNode* ps);
StackNode* BuyStackNode(STDataType x);

Stack.c文件代码:

#include"Stack.h"
StackNode* BuyStackNode(STDataType x)//开辟一个栈(链表的)节点
{
	StackNode* newnode = (StackNode*)malloc(sizeof(StackNode));
	if (newnode == NULL)
	{
		printf("fail malloc\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	return newnode;
}
StackNode* StackInit()//栈的初始化
{
	StackNode* head = BuyStackNode(-1);
	return head;
}
void StackDestory(StackNode* ps)//栈的销毁
{
	assert(ps);
	StackNode* cur = ps;
	while (cur)
	{
		StackNode* next = cur->next;
		free(cur);
		cur = next;
	}
}
void StackPush(StackNode* ps, STDataType x)//入栈
{
	assert(ps);
	StackNode* newnode = BuyStackNode(x);
	StackNode* next = ps->next;
	ps->next = newnode;
	newnode->next = next;
}
void StackPop(StackNode* ps)//出栈
{
	assert(ps);
	assert(ps->next);
	StackNode* pop = ps->next;
	ps->next = pop->next;
	free(pop);
}
bool StackEmpty(StackNode* ps)//判断栈是否为空
{
	assert(ps);
	return ps->next == NULL;
}
int SizeStack(StackNode* ps)//求栈中有的节点的数目
{
	assert(ps);
	int size = 0;
	StackNode* cur = ps->next;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
STDataType StackTop(StackNode* ps)//求栈顶的节点存储的元素
{
	assert(ps);
	assert(ps->next);
	return ps->next->val;
}

相关文章