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

 一、栈的介绍

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

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

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

2.1 栈的创建以及初始化

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

typedef int MyInt;
#define STACK_SIZE 20

typedef 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 fulln");
        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 emptyn");
        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 emptyn");
        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 emptyn");
        return;
    }
    printf("栈中的元素为:n");
    for( int i = s->bottom; i <= s->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("被删除的元素:%dn",delete);

    ClearStack(&stack);
    PrintStack(&stack);

    return 0 ;
}

2.7 结果输出以及代码

        输出结果:

        全部代码:

 

#include<stdio.h>

typedef int MyInt;
#define STACK_SIZE 20

typedef 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 fulln");
        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 emptyn");
        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 emptyn");
        return;
    }
    printf("栈中的元素为:n");
    for( int i = s->bottom; i <= s->top; i++){
        printf("%d  ",s->data[i]);
    }
    printf("n");
}

void ClearStack(Stack* s){
    if(s->top == -1){
        printf("this Stack is emptyn");
        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("被删除的元素:%dn",delete);

    ClearStack(&stack);
    PrintStack(&stack);

    return 0 ;
}

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

3.1 栈的创建以及初始化

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

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <math.h>


#define STACK_INIT_SIZE 10
#define STACK_SIZE_ADD 10

typedef 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("删除的元素是:  %dn",pop_stack(&myStack));
    Print_stack(myStack);
    
    clear_stack(&myStack);
    Print_stack(myStack);

    destroy_stack(&myStack);
    destroy_stack(&myStack);
    return 0;
}

3.8 全部代码:

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <math.h>


#define STACK_INIT_SIZE 10
#define STACK_SIZE_ADD 10

typedef 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 < s.top){
        printf("%d  ",*p);
        p++;
    }
    printf("n");
}

void clear_stack(stack *s){
    ElemType *p = s->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("删除的元素是:  %dn",pop_stack(&myStack));
    Print_stack(myStack);
    
    clear_stack(&myStack);
    Print_stack(myStack);

    destroy_stack(&myStack);
    destroy_stack(&myStack);
    return 0;
}

输出结果:

 四、总结

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