欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈的顺序存储及实现(二)

程序员文章站 2022-06-05 13:33:53
...

栈的介绍


栈(stack)是限定仅在表尾进行插入和删除操作的线性表
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又被称为后进先出(LastIn First Out)的线性表,简称LIOF结构。
首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已


代码实现


栈一般的实现都是用顺序存储结构进行实现的,上次我们在栈的顺序存储结构及实现(一)采用的数组进行实现,但是数组有个瓶颈就是固定了栈的长度这次我们才采用动态获取内存空间,当压栈时如果栈满进行动态的扩充容量,进行栈的实现


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 5
#define STACK_INCREMENT 5
typedef int Status;
typedef int EleType;

typedef struct SeqStack
{
	EleType* top;//栈顶指针
	EleType* base;//栈底指针
	int stackSize;//栈容量
}SeqStack;
//初始化栈
Status InitStack(SeqStack* stack)
{
	//开辟空间
	stack->base = stack->top = (EleType*)malloc(STACK_INIT_SIZE*sizeof(EleType));
	if (!stack->base)
	{
		exit(0);
	}
	return OK;
}
/*
清空栈
*/
Status ClearStack(SeqStack* stack) {
	if (NULL == stack) {
		return ERROR;
	}
	//清空栈 实质上是忽略栈中数据,可以再次使用内存单元
	stack->top = stack->base;
	return OK;
}
/*
销毁栈
*/
Status DestroyStack(SeqStack* stack)
{
	if (NULL == stack) {
		return ERROR;
	}
	//销毁栈 是释放栈在内存中占用的空间资源
	if (!stack->base)
	{
		free(stack->base);
	}
	stack->top = stack->base = NULL;
	stack->stackSize = 0;
	return OK;
}
//获取栈长度(栈中元素个数)
int LengthStack(SeqStack stack)
{
	return stack.top - stack.base;
}
//压栈
Status push(SeqStack* stack,EleType e)
{
	if (stack == NULL)
	{
		return ERROR;
	}
	//压栈之前检测容量是否足够
	if (stack->top - stack->base == stack->stackSize)
	{
		//超出容量 进行扩容,使用realloc函数,会拷贝原内存内容
		stack->base = (SeqStack*)realloc(stack->base, stack->stackSize+STACK_INCREMENT);
		if (!stack->base)
		{
			exit(0);
		}
		stack->top = stack->base + stack->stackSize;
		stack->stackSize += STACK_INCREMENT;
	}
	*stack->top = e;
	stack->top++;
	return OK;
}
//弹栈
Status pop(SeqStack* stack, EleType *e)
{
	if (stack == NULL || e == NULL)
	{
		return ERROR;
	}
	//空栈
	if (stack->top == stack->base)
	{
		return ERROR;
	}
	*stack->top--;
	*e = *stack->top;
	return OK;
}
/*
判断栈是否为空
*/
int IsEmptyStack(SeqStack* stack) {
	if (NULL == stack) {
		return ERROR;
	}
	if (stack->top == stack->base) {
		return TRUE;
	}
	return FALSE;
}
/*
获取栈顶元素
*/
Status GetTop(SeqStack* stack, EleType *e) {
	if (NULL == stack) {
		return ERROR;
	}
	*e = *(stack->top - 1);
	return OK;
}
/*
从栈顶向下展示元素值
*/
Status ShowStack(SeqStack* stack) {
	if (NULL == stack || stack->top == stack->base) {
		return ERROR;
	}
	EleType *top = stack->top;
	while (top != stack->base)
	{
		top--;
		printf("%d\n", *top);
	}
	return OK;
}
int main(int argc, char *argv[])
{
	SeqStack stack;//创建顺序栈
	InitStack(&stack);//初始化
	printf("压入元素5,4,3,2,1\n");
	push(&stack, 5);
	push(&stack, 4);
	push(&stack, 3);
	push(&stack, 2);
	push(&stack, 1);
	puts("栈元素展示:");
	ShowStack(&stack);
	puts("弹出2个元素后");
	puts("栈元素展示:");
	EleType e1, e2,e3;
	pop(&stack, &e1);
	pop(&stack, &e2);
	ShowStack(&stack);
	printf("弹出元素为:%d,%d\n", e1, e2);
	//测试是否动态扩充容量
	push(&stack,8);
	push(&stack,9);
	push(&stack,10);
	printf("压入元素8,9,10\n");
	puts("栈元素展示:");
	ShowStack(&stack);
	GetTop(&stack, &e3);
	printf("栈顶元素为:%d\n", e3);
	DestroyStack(&stack);
	return 0;
}



运行结果


栈的顺序存储及实现(二)