栈的顺序存储及实现（二）

墨蓝 2022-06-01 05:22 150阅读 0赞

# 栈的介绍 #

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

# 代码实现 #

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

#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;
    }

# 运行结果 #

![SouthEast][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/78882939
[SouthEast]: /images/20220601/ced5f3ec685f44c5aefd1f9844f30ea7.png