数据结构学习——C语言对栈的基本操作

一、栈的介绍

栈(Stack)是一种常用的数据结构，遵循先进后出(LIFO)的原则，对表尾进行操作，常用于临时存储和撤销等操作，其基本操作包括栈的创建、入栈(也叫压栈Push)、出栈(又称弹栈)、栈的遍历、栈的清空(clear)、栈的销毁(destroy)等。

二、数组方式——栈的基本操作

栈的创建有两种方式，一种是通过数组的方式，另一种是通过指针的方式，两种方式的原理都遵循栈的基本原理。

2.1 栈的创建以及初始化

宏定义栈的最大大小，创建结构体，这里都用的int类型，初始化栈，将栈顶和栈底指针均置为 -1 表示此时为一个空栈。

typedef int MyInt;#define STACK_SIZE 20typedef struct{MyInt data[STACK_SIZE];MyInt top;MyInt bottom;}Stack;void StackInit(Stack *s){s->top = -1;s->bottom = -1;}

2.2 入栈函数(压栈操作)

需要注意的是，插入第一个元素之前，栈顶和栈底的指向均为 -1 ，在插入第一个值时，需要将栈顶和栈底均置为0，因为这里栈底和栈顶为 -1 的时候表示还没有插入任何的元素。

void PushStack(Stack* s,int data){if(s->top == STACK_SIZE - 1){//栈满printf("this Stack is full\n");return;}if(s->top == -1){//空栈，第一次插入元素，初始化栈底s->bottom = 0;}//栈顶指针向上移动，指向栈底s->top++;//当前节点插入元素s->data[s->top] = data;}

2.3 出栈函数(弹栈操作）

出栈遵循先进后出的原理，因此这里每次调用出栈函数只删除最后一个元素，还需要改变栈顶的指向，使栈顶的指向向下移动一个，指向上一个进栈的元素，并且定义int类型的变量将出栈的元素记录下来。

MyInt PopStack(Stack* s){if(s->top == -1){//空栈，没有元素可供删除printf("Stack is empty\n");return -1;}//定义变量pop_data表示要出栈的元素MyInt pop_data = s->data[s->top];//栈顶指针下移s->top--;if(s->top == -1)//栈为空时,重置栈底指针s->bottom = -1;//传回出栈元素return pop_data;}

2.4 清栈函数(只清空数据）

清栈函数只清除元素的数据，并不改变栈顶和栈底的指向，原来有多少个元素在进行清栈操作后依然有多少个元素，元素个数不会发生改变，但内容均为 0 ，销毁一个栈即栈为空，需要移动栈顶指针，只需在清栈同时移动栈顶指针即可。

void ClearStack(Stack* s){if(s->top == -1){printf("this Stack is empty\n");return;}for(int i = s->top; i >= s->bottom; i--){s->data[i] = 0;//若需销毁栈操作时，需要移动top指针//s->top--;}//只清空数据不改变栈顶和栈底}

2.5 栈的遍历

栈的遍历这里也遵循了先进后出的原理，遍历的时候从最前面的元素往后遍历，不改变栈顶指向，这里定义变量 i 进行循环操作，并且判断当栈顶 top 为 -1 的时候表示该栈中已经没有元素了，是一个空栈。

void PrintStack(Stack* s){if(s->top == -1){//空栈printf("Stack is empty\n");return;}printf("栈中的元素为:\n");for( int i = s->bottom; i top; i++){printf("%d",s->data[i]);}printf("\n");}

2.6 主函数测试

int main(){Stack stack;StackInit(&stack);PushStack(&stack,1);PushStack(&stack,2);PushStack(&stack,3);PrintStack(&stack); int delete = PopStack(&stack);PrintStack(&stack);printf("被删除的元素:%d\n",delete);ClearStack(&stack);PrintStack(&stack);return 0 ;}

2.7 结果输出以及代码

输出结果：

全部代码：

#includetypedef int MyInt;#define STACK_SIZE 20typedef struct{MyInt data[STACK_SIZE];MyInt top;MyInt bottom;}Stack;void StackInit(Stack *s){s->top = -1;s->bottom = -1;}void PushStack(Stack* s,int data){if(s->top == STACK_SIZE - 1){//栈满printf("this Stack is full\n");return;}if(s->top == -1){//空栈，第一次插入元素，初始化栈底s->bottom = 0;}//栈顶指针向上移动，指向栈底s->top++;//当前节点插入元素s->data[s->top] = data;}MyInt PopStack(Stack* s){if(s->top == -1){//空栈，没有元素可供删除printf("Stack is empty\n");return -1;}//定义变量pop_data表示要出栈的元素MyInt pop_data = s->data[s->top];//栈顶指针下移s->top--;if(s->top == -1)//栈为空时,重置栈底指针s->bottom = -1;//传回出栈元素return pop_data;}void PrintStack(Stack* s){if(s->top == -1){//空栈printf("Stack is empty\n");return;}printf("栈中的元素为:\n");for( int i = s->bottom; i top; i++){printf("%d",s->data[i]);}printf("\n");}void ClearStack(Stack* s){if(s->top == -1){printf("this Stack is empty\n");return;}for(int i = s->top; i >= s->bottom; i--){s->data[i] = 0;}//只清空数据不改变栈顶和栈底}int main(){Stack stack;StackInit(&stack);PushStack(&stack,1);PushStack(&stack,2);PushStack(&stack,3);PrintStack(&stack); int delete = PopStack(&stack);PrintStack(&stack);printf("被删除的元素:%d\n",delete);ClearStack(&stack);PrintStack(&stack);return 0 ;}

三、指针方式——栈的基本操作

3.1 栈的创建以及初始化

首先定义结构体，其成员包括栈顶指针和栈底指针，最大长度。宏定义栈的初始大小和增量大小，当该栈满了的时候，重新为其分配内存大小，一次分配 STACK_SIZE_ADD个长度，初始化栈的栈顶和栈底相同，并且初始大小为 STACK_INIT_SIZE。

#include #include #include #include #define STACK_INIT_SIZE 10#define STACK_SIZE_ADD 10typedef char ElemType;typedef struct{ElemType *top;//栈顶指针ElemType *base; //栈底指针int MaxSize;//最大长度}stack;void init_stack(stack *s){//分配初始内存大小s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));//判断内存是否分配成功if( !s->base ){printf("内存分配失败\n");return;}//初始化栈顶和栈底指向相同s->top = s->base;//初始化栈的最大大小s->MaxSize = STACK_INIT_SIZE;}

3.2 入栈函数

调用入栈函数先判断该栈是否超过了最大长度，若超过则重新分配内存大小，并且给栈底赋值后栈顶指针指向下一个元素，此代码中栈顶指针top除初始化外始终指向最后一个元素的下一个空元素。

void push_stack(stack *s,ElemType value){//判断栈是否超过了最大长度if(s->top - s->base >= s->MaxSize){//relloc 重新分配内存，有两个参数，分别是指向地址的指针和内存大小s->base = (ElemType *)realloc(s->base,(s->MaxSize + STACK_SIZE_ADD) * sizeof(ElemType));if(!s->base){printf("内存分配失败\n");return;}}*(s->top) = value;//top指针向上移动，指向下一个元素,此时还没有内容s->top++;}

3.3 出栈函数

出栈函数相对入栈简单很多，需要注意的是当该栈为空的时候已经不能进行出栈操作，因此要先判断该栈是否为空，直接将栈顶指针指向先前进栈的元素即可。

ElemType pop_stack(stack *s){//判断是否为空栈if(s->top == s->base){printf("该栈为空!\n");return -1;}return *--(s->top); }

3.4 清栈函数

这里的清栈将栈中全部的元素均进行置零，不改变栈顶指针的指向，因此需要重新定义指针用于遍历清零。

void clear_stack(stack *s){ElemType *p = s->base;if(s->top == s->base){printf("该栈为空!\n");return;}for( ; p != s->top; p++){*p = 0;}}

3.5 栈的遍历

void Print_stack(stack s){//判断是否为空栈if(s.top == s.base){printf("该栈为空!\n");return;}ElemType *p = s.base;printf("栈中的元素为:\n");while(p < s.top){printf("%d",*p);p++;}printf("\n");}

3.6 销毁一个栈

销毁一个栈只需要将结构体指针置为空，并且将分配的内存释放即可，注意需避免对空栈进行销毁。

void destroy_stack(stack *s){if(s->base != NULL){free(s->base);s->top = NULL;s->base = NULL;s->MaxSize = 0;printf("该栈销毁成功\n");return;}printf("该栈为空,无法进一步销毁\n");}

3.7 主函数

int main(){stack myStack;init_stack(&myStack);push_stack(&myStack,1);push_stack(&myStack,2);push_stack(&myStack,3);Print_stack(myStack); printf("删除的元素是:%d\n",pop_stack(&myStack));Print_stack(myStack);clear_stack(&myStack);Print_stack(myStack);destroy_stack(&myStack);destroy_stack(&myStack);return 0;}

3.8 全部代码：

#include #include #include #include #define STACK_INIT_SIZE 10#define STACK_SIZE_ADD 10typedef char ElemType;typedef struct{ElemType *top;//栈顶指针ElemType *base; //栈底指针int MaxSize;//最大长度}stack;void init_stack(stack *s){//分配初始内存大小s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));//判断内存是否分配成功if( !s->base ){printf("内存分配失败\n");return;}//初始化栈顶和栈底指向相同s->top = s->base;//初始化栈的最大大小s->MaxSize = STACK_INIT_SIZE;}void push_stack(stack *s,ElemType value){//判断栈是否超过了最大长度if(s->top - s->base >= s->MaxSize){//relloc 重新分配内存，有两个参数，分别是指向地址的指针和内存大小s->base = (ElemType *)realloc(s->base,(s->MaxSize + STACK_SIZE_ADD) * sizeof(ElemType));if(!s->base){printf("内存分配失败\n");return;}}*(s->top) = value;//top指针向上移动，指向下一个元素,此时还没有内容s->top++;}ElemType pop_stack(stack *s){//判断是否为空栈if(s->top == s->base){printf("该栈为空!\n");return -1;}return *--(s->top); }void Print_stack(stack s){//判断是否为空栈if(s.top == s.base){printf("该栈为空!\n");return;}ElemType *p = s.base;printf("栈中的元素为:\n");while(p base;if(s->top == s->base){printf("该栈为空!\n");return;}for( ; p != s->top; p++){*p = 0;}}void destroy_stack(stack *s){if(s->base != NULL){free(s->base);s->top = NULL;s->base = NULL;s->MaxSize = 0;printf("该栈销毁成功\n");return;}printf("该栈为空,无法进一步销毁\n");}int main(){stack myStack;init_stack(&myStack);push_stack(&myStack,1);push_stack(&myStack,2);push_stack(&myStack,3);Print_stack(myStack); printf("删除的元素是:%d\n",pop_stack(&myStack));Print_stack(myStack);clear_stack(&myStack);Print_stack(myStack);destroy_stack(&myStack);destroy_stack(&myStack);return 0;}

输出结果：

四、总结

对栈的各种操作时需要注意内存使用的问题，注意判断栈顶指针的指向，栈底指针的指向，栈的内存分配，遵循先进后出的原则，在使用后需要对栈进行内存释放。