数据结构学习——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;
}

输出结果：

 四、总结

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