C语言实现一个动态栈

- 日理万妓 2022-01-30 05:01 176阅读 0赞

**栈是一种特殊的数据结构,栈是具有先进后出的规则的,所以栈是不能进行遍历的,遵循栈的原则,只进行先进后出  
栈容器决定这个栈应该放入多少个元素,如果栈容器已经满了,则对栈容器进行扩容  
扩容五步走:  
1.开辟新的空间(默认是旧空间的二倍)  
2.把旧空间的数据拷贝到新的空间  
3.释放旧空间  
4.指针指向新的空间  
5.把栈容器的值改为原来的二倍**

**//头文件**

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <assert.h>
    
    
    typedef int SDataType;
    
    typedef struct Stack
    { 
    	SDataType* _array;
    	int _capacity;
    	int _size; // 表示栈中有效元素的个数 代表栈顶位置
    }Stack;
    
    //实现栈的API操作
    //初始化一个栈
    void StackInit(Stack* ps);
    //压栈
    void StackPush(Stack* ps, SDataType data);
    //出栈
    void StackPop(Stack* ps);
    //弹出栈顶元素
    SDataType StackTop(Stack* ps);
    //返回栈中有效元素个数
    int StackSize(Stack* ps);
    //判断栈是否为空
    int StackEmpty(Stack* ps);
    //销毁栈
    void StackDestroy(Stack* ps);

**//栈的实现文件**

#include "Stack.h"
    void StackInit(Stack* ps) { 
    	if (ps == NULL) { 
    		return;
    	}
    	ps->_capacity = 3;
    	ps->_size = 0;
    	ps->_array = (SDataType*)malloc(sizeof(SDataType)* ps->_capacity);
    	if (ps->_array == NULL) { 
    		assert(ps->_array);
    	}
    	for (int i = 0; i < ps->_capacity; ++i) { 
    		ps->_array[i] = 0;
    	}
    }
    //压栈
    void StackPush(Stack* ps, SDataType data) { 
    	if (ps == NULL) { 
    		return;
    	}
    	if (ps->_size == ps->_capacity) { 
    		//扩大容器
    		ps->_capacity = 2 * ps->_capacity;
    		//创建新空间
    		SDataType* newspace = (SDataType*)malloc(sizeof(SDataType)*ps->_capacity);
    		//拷贝数据
    		for (int i = 0; i < ps->_size; ++i) { 
    			newspace[i] = ps->_array[i];
    		}
    		//释放旧空间
    		free(ps->_array);
    		//指针指向新空间
    		ps->_array = newspace;
    	}
    	ps->_array[ps->_size] = data;
    	ps->_size++;
    }
    //出栈
    void StackPop(Stack* ps) { 
    	if (ps == NULL) { 
    		return;
    	}
    	if (ps->_size == 0) { 
    		printf("栈已空\n");
    		return;
    	}
    	ps->_size--;
    }
    //弹出栈顶元素
    SDataType StackTop(Stack* ps) { 
    	if (ps == NULL) { 
    		return 0;
    	}
    	if (ps->_size == 0) { 
    		printf("栈中无元素\n");
    		return 0;
    	}
    	return ps->_array[ps->_size - 1];
    }
    //返回栈中有效元素个数
    int StackSize(Stack* ps) { 
    	if (ps == NULL) { 
    		return 0;
    	}
    	return ps->_size;
    }
    //判断栈是否为空
    int StackEmpty(Stack* ps) { 
    	if (ps == NULL) { 
    		return 0;
    	}
    	if (ps->_size == 0) { 
    		return 0;
    	}
    	return 1;
    }
    //销毁栈
    void StackDestroy(Stack* ps) { 
    	if (ps == NULL) { 
    		return;
    	}
    	free(ps->_array);
    	ps->_array = NULL;
    }

**//测试文件**

#include "Stack.h"
    
    int main() { 
    	//定义一个栈
    	Stack s;
    	//对栈进行初始化
    	StackInit(&s);
    	int Empty = StackEmpty(&s);
    	if (Empty == 0) { 
    		printf("栈为空\n");
    	}
    	else { 
    		printf("栈不为空\n");
    	}
    	StackPush(&s, 1);
    	StackPush(&s, 2);
    	StackPush(&s, 3);
    	StackPush(&s, 4);
    	StackPush(&s, 5);
    	StackPush(&s, 6);
    	StackPop(&s);
    	int ret=StackTop(&s);
    	printf("%d\n", ret);
    	int size = StackSize(&s);
    	printf("%d\n", size);
    	Empty = StackEmpty(&s);
    	if (Empty == 0) { 
    		printf("栈为空\n");
    	}
    	else { 
    		printf("栈不为空\n");
    	}
    	StackDestroy(&s);
    	system("pause");
    	return 0;
    }