栈的动态实现

短命女 2022-06-06 09:18 190阅读 0赞

#### 栈的动态实现 ####

*  栈是一种先进后出的数据结构，已经使用数组实现过栈，这里通过链表来实现栈；
 *  对于栈来说，添加元素和删除元素都在一端进行，所以实现过程是比较容易的；
 *  按照栈的数据结构要求首先需要实现一下几种操作：  
    
    
     *  1.栈的初始化操作`CreateStack()`；
     *  2.添加元素操作`push()`；
     *  3.删除元素操作`pop()`;
     *  4.访问栈顶元素`top()`;
     *  5.栈的大小判断操作`StackSize()`;
 *  首先需要定义栈的数据类型

typedef struct StackNode *StackNodePointer;
    
    struct StackNode
    {
        int data;
        StackNodePointer next;
    };

*  这里仅仅模拟实现一个栈，所以对于第一个节点的指针变量使用全局变量的方式，首先进行栈的初始化工作；

StackNodePointer snode = NULL;
    StackNodePointer CreateStack()
    {
        snode = (StackNodePointer)malloc(sizeof(StackNodePointer));
        snode->data = 0;
        snode->next = NULL;
        return snode;
    }

*  栈里面添加元素，就是链表元素的插入操作，可以使用头插法，也可以使用尾插法，这里是用头插法；

void push(int value)
    {
        StackNodePointer newhead = NULL;
        newhead = (StackNodePointer)malloc(sizeof(StackNodePointer));
        newhead->data = value;
        newhead->next = snode;
        snode = newhead;
    }

*  栈里面删除元素其实就是链表头节点的删除操作(因为元素插入使用的是头插法)；

void pop()
    {
        if(snode->next==NULL){
            fprintf(stderr,"The stack is NULL\n");
            exit(EXIT_FAILURE);
        }
        StackNodePointer previous = snode;
        snode = snode->next;
        free(previous);
    }

*  访问栈顶元素，不进行元素的删除操作，所以需要由返回值类型一般来说需要是定义的栈的数据类型；

StackNodePointer top()
    {
        if(snode->next==NULL){
            fprintf(stderr,"The Stack is NULL\n");
            exit(EXIT_FAILURE);
        }
        return snode;
    }

*  栈的大小统计函数；

int StackSize()
    {
        int size = 0;
        while (snode->next != NULL)
        {
            snode = snode->next;
            ++size;
        }
        return size;
    }

*  栈的打印函数，这个主要是用来判断里面元素的存储情况的；

void PrintStack()
    {
        StackNodePointer PrintNode = snode;
        while (PrintNode->next != NULL)
        {
            printf("[ %d ]\n", PrintNode->data);
            PrintNode=PrintNode->next;
        }
    }

*  程序运行的完整程序；

#include<stdio.h>
    #include<stdlib.h>
    
    
    typedef struct StackNode *StackNodePointer;
    
    struct StackNode
    {
        int data;
        StackNodePointer next;
    };
    
    StackNodePointer snode = NULL;
    StackNodePointer CreateStack()
    {
        snode = (StackNodePointer)malloc(sizeof(StackNodePointer));
        snode->data = 0;
        snode->next = NULL;
        return snode;
    }
    
    void push(int value)
    {
        StackNodePointer newhead = NULL;
        newhead = (StackNodePointer)malloc(sizeof(StackNodePointer));
        newhead->data = value;
        newhead->next = snode;
        snode = newhead;
    }
    
    void pop()
    {
        if(snode->next==NULL){
            fprintf(stderr,"The stack is NULL\n");
            exit(EXIT_FAILURE);
        }
        StackNodePointer previous = snode;
        snode = snode->next;
        free(previous);
    }
    
    StackNodePointer top()
    {
        if(snode->next==NULL){
            fprintf(stderr,"The Stack is NULL\n");
            exit(EXIT_FAILURE);
        }
        return snode;
    }
    
    int StackSize()
    {
        int size = 0;
        while (snode->next != NULL)
        {
            snode = snode->next;
            ++size;
        }
        return size;
    }
    
    void PrintStack()
    {
        StackNodePointer PrintNode = snode;
        while (PrintNode->next != NULL)
        {
            printf("[ %d ]\n", PrintNode->data);
            PrintNode=PrintNode->next;
        }
    }
    
    
    int main()
    {
        CreateStack();
        push(10);
        push(9);
        push(8);
        push(7);
        push(6);
        push(5);
        push(4);
        push(3);
        push(2);
        push(1);
        PrintStack();
        pop();
        printf("The top is [%d]\n",top()->data);
        PrintStack();
        printf("size: [ %d ]\n", StackSize());
        return 0;
    }