数据结构栈的实现-白红宇

数据结构栈的实现

阅读量：6046 次

发布时间：2019-06-20

本文共 7470 字，大约阅读时间需要 24 分钟。

栈的概念：数据先进后出，以高地址为栈顶。存储方式分为链式存储和顺序存储

顺序存储栈的容器：

顺序栈的头文件：

#pragma once#include
     
      #include
      
       #define MAX 1024//顺序栈struct SeqStack{    void *data[MAX];    int size;};#ifdef __cplusplusextern "C"{#endif    //初始化栈    void *Init_SeqStack();    //入栈    void Push_SeqStack(void *stack, void *data);    //出栈    void Pop_SeqStack(void *stack);    //获得大小    int Size_SeqStack(void *stack);    //获得栈顶元素    void *Top_SeqStack(void *stack);    //销毁栈    void Destroy_SeqStack(void *stack);#ifdef __cplusplus}#endif

顺序栈头文件的实现：

#include"SeqStack.h"//初始化栈void *Init_SeqStack(){    struct SeqStack *stack = malloc(sizeof(struct SeqStack));    stack->size = 0;     for (int i = 0; i < MAX; i ++){        stack->data[i] = 0;    }    return stack;}//入栈void Push_SeqStack(void *stack, void *data){    if (0 == stack){        return;    }    if (0 == data){        return;    }    struct SeqStack *s = (struct SeqStack *)stack;    s->data[s->size] = data;    s->size++;}//出栈void Pop_SeqStack(void *stack){    if (0 == stack){        return;    }    struct SeqStack *s = (struct SeqStack *)stack;    s->size--;}//获得大小int Size_SeqStack(void *stack){    if (0 == stack){        return -1;    }    struct SeqStack *s = (struct SeqStack *)stack;    return s->size;}//获得栈顶元素void *Top_SeqStack(void *stack){    if (0 == stack){        return NULL;    }    struct SeqStack *s = (struct SeqStack *)stack;    return s->data[s->size - 1];}//销毁栈void Destroy_SeqStack(void *stack){    if (0 == stack){        return;    }    free(stack);}

测试文件：

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       #include
       
        #include"SeqStack.h"struct Person{    char name[64];    int age;};void test(){    //测试数据    struct Person p1 = { "aaa", 10 };    struct Person p2 = { "bbb", 20 };    struct Person p3 = { "ccc", 30 };    struct Person p4 = { "ddd", 40 };    struct Person p5 = { "eee", 50 };    //初始化栈    void *stack = Init_SeqStack();    //数据入栈    Push_SeqStack(stack, &p1);    Push_SeqStack(stack, &p2);    Push_SeqStack(stack, &p3);    Push_SeqStack(stack, &p4);    Push_SeqStack(stack, &p5);    //输出栈中所有元素    while (Size_SeqStack(stack) > 0){                //获得栈顶元素        struct Person * person = (struct Person *)Top_SeqStack(stack);        //输出栈顶元素        printf("Name:%s Age:%d\n",person->name,person->age);        //弹出栈顶元素        Pop_SeqStack(stack);    }    //销毁栈    Destroy_SeqStack(stack);}int main(){    test();    system("pause");    return EXIT_SUCCESS;}

链式栈的实现：

链式栈的头文件：

#pragma once#include
     
      struct LinkNode{    struct LinkNode *next;};//链式栈struct LStack{    struct LinkNode header;    int size;};typedef void* LinkStack;#ifdef __cplusplusextern "C"{#endif    //初始化    LinkStack Init_LinkStack();    //入栈    void Push_LinkStack(LinkStack stack, void *data);    //出栈    void Pop_LinkStack(LinkStack stack);    //获得栈顶元素    void *Top_LinkStack(LinkStack stack);    //大小    int Size_LinkStack(LinkStack stack);    //销毁栈    void Destroy_LinkStack(LinkStack stack);#ifdef __cplusplus}#endif

头文件的实现：

#include"LinkStack.h"//初始化LinkStack Init_LinkStack(){    struct LStack *stack = (struct LStack *)malloc(sizeof(struct LStack));    stack->header.next = NULL;    stack->size = 0;    return stack;}//入栈void Push_LinkStack(LinkStack stack, void *data){    if (NULL == stack){        return;    }    if (data == NULL){        return;    }    struct LStack *s = (struct LStack *)stack;    struct LinkNode *d = (struct LinkNode *)data;    d->next =  s->header.next;    s->header.next = d;    s->size++;}//出栈void Pop_LinkStack(LinkStack stack){    if (NULL == stack){        return;    }    struct LStack *s = (struct LStack *)stack;    if (s->size == 0){        return;    }    //缓存下待删除节点    struct LinkNode *pDel = s->header.next;    s->header.next = pDel->next;    s->size--;}//获得栈顶元素void *Top_LinkStack(LinkStack stack){    if (NULL == stack){        return NULL;    }    struct LStack *s = (struct LStack *)stack;    return s->header.next;}//大小int Size_LinkStack(LinkStack stack){    if (NULL == stack){        return -1;    }    struct LStack *s = (struct LStack *)stack;    return s->size;}//销毁栈void Destroy_LinkStack(LinkStack stack){    if (NULL == stack){        return;    }    free(stack);    stack = NULL;}

测试文件：

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       #include
       
        #include"LinkStack.h"struct Person{    struct LinkNode node;    char name[64];    int age;};void test(){        //创建数据    struct Person p1 = { NULL, "aaa", 10 };    struct Person p2 = { NULL, "bbb", 20 };    struct Person p3 = { NULL, "ccc", 30 };    struct Person p4 = { NULL, "ddd", 40 };    struct Person p5 = { NULL, "eee", 50 };    //初始化链式栈    LinkStack stack = Init_LinkStack();    //数据入栈    Push_LinkStack(stack, &p1);    Push_LinkStack(stack, &p2);    Push_LinkStack(stack, &p3);    Push_LinkStack(stack, &p4);    Push_LinkStack(stack, &p5);    //输出栈容器中元素    while (Size_LinkStack(stack) > 0){                //获得栈顶元素        struct Person *person = (struct Person *)Top_LinkStack(stack);        //打印        printf("Name:%s Age:%d\n", person->name, person->age);        //弹出栈顶元素        Pop_LinkStack(stack);        printf("Size:%d\n", Size_LinkStack(stack));    }    printf("----------------\n");    printf("Size:%d\n", Size_LinkStack(stack));    //销毁栈    Destroy_LinkStack(stack);}int main(){    test();    system("pause");    return EXIT_SUCCESS;}

以链表作为底层容器，实现栈的操作：

容器头文件和头文件的实现：见数据结构链表的实现

栈的头文件：

#pragma once#include"LinkList.h"struct StackNode{    struct LinkNode node;};typedef void *LinkStack;//初始化LinkStack Init_LinkStack();//入栈void Push_LinkStack(LinkStack stack, void *data);//出栈void Pop_LinkStack(LinkStack stack);//获得栈顶元素void *Top_LinkStack(LinkStack stack);//大小int Size_LinkStack(LinkStack stack);//销毁栈void Destroy_LinkStack(LinkStack stack);

栈的头文件实现：

#include"LinkStack.h"//初始化LinkStack Init_LinkStack(){    return Init_LinkList();}//入栈void Push_LinkStack(LinkStack stack, void *data){    Insert_LinkList(stack, 0, data);}//出栈void Pop_LinkStack(LinkStack stack){    RemoveByPos_LinkList(stack, 0);}//获得栈顶元素void *Top_LinkStack(LinkStack stack){    return Get_LinkList(stack, 0);}//大小int Size_LinkStack(LinkStack stack){    return Size_LinkList(stack);}//销毁栈void Destroy_LinkStack(LinkStack stack){    Destroy_LinkList(stack);}

测试代码：

define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       #include
       
        #include"LinkStack.h"struct Person{    struct StackNode node;    char name[64];    int age;};void test(){    //创建测试数据    struct Person p1 = { NULL, "aaa", 10 };    struct Person p2 = { NULL, "bbb", 20 };    struct Person p3 = { NULL, "ccc", 30 };    struct Person p4 = { NULL, "ddd", 40 };    struct Person p5 = { NULL, "eee", 50 };    //初始化栈    LinkStack stack = Init_LinkStack();    //数据入栈    Push_LinkStack(stack , &p1);    Push_LinkStack(stack, &p2);    Push_LinkStack(stack, &p3);    Push_LinkStack(stack, &p4);    Push_LinkStack(stack, &p5);    //输出栈中元素    while (Size_LinkStack(stack) > 0){            //获得栈顶元素        struct Person *person = (struct Person*)Top_LinkStack(stack);        //输出元素        printf("Name:%s Age:%d\n",person->name,person->age);        //弹出栈顶元素        Pop_LinkStack(stack);    }    printf("Size%d\n",Size_LinkStack(stack));    //销毁栈    Destroy_LinkStack(stack);}int main(){    test();    system("pause");    return EXIT_SUCCESS;}