栈的链式存储实现过程

1、定义栈的数据结构：

/* 节点结构体*/
typedef struct Node {
    int value;             // 节点的值
    struct Node* next;     //  下一个节点的地址
} Node;
/* 栈结构体*/
typedef struct {
    Node* top;             // 栈顶，指向首个节点的地址
} Stack;

2、初始化栈

void InitStack(Stack* stack){
    stack->top = (Node*)malloc(sizeof(Node));   // 为栈顶申请内存
    stack->top->next = NULL;                    // 将栈顶的指向的下一个节点置为空，防止出现野指针
}

3、入栈，即向栈的头部追加一个新的节点

void Push(Stack *stack,int value){
    Node* node;                            // 创建新节点
    node = (Node*)malloc(sizeof(Node));    // 为节点申请内存
    node->value = value;                   // 为节点赋值
    node->next = stack->top->next;         // 将栈顶指向的节点放在新创的节点之后
    stack->top->next = node;               // 将栈顶指向新的节点 
}

4、出栈，即将队尾的元素弹出

Node* Pop(Stack *stack){
    Node* del = NULL;                     // 创建一个空节点用来储存首个节点
    del = stack->top->next;               // 将栈的首个节点赋值给刚刚创建的空节点
    if(del != NULL){                      // 判断栈内是否有节点
        stack->top->next = del->next;     // 将栈顶指向下一个节点 
    }
    return del;
}

5、得到栈的长度

int Length(Stack *stack)
{
    int length = 0;
    Node *nNode;                // 创建新节点
    nNode = stack->top->next;   // 将栈顶指向节点赋值给新节点
    while (nNode != NULL)       // 判断是否循环到队尾
    {
        length++;
        nNode = nNode->next;    // 将指针指向下一个节点
    }
    return length;
}

5、显示单个节点的值

void NodeDisPlay(Node* node){
    printf("This Node Value is %d.\n",node->value);
}

6、遍历栈，每次将指针指向下个节点输入节点的值，通过指针是否为空判断是否到达栈尾

void StackDisplay(Stack *stack){
    Node *nNode;                 // 创建新节点
    nNode = stack->top->next;    // 将栈顶指向节点赋值给新节点
    while (nNode != NULL)        // 判断是否循环到队尾
    {
        NodeDisPlay(nNode);      // 显示当前节点的值
        nNode = nNode->next;     // 将指针指向下一个节点
    }
}

清空栈

void CleanStack(Stack *stack){
    Node *pNode, *tmp;            // pNode节点用来存储栈节点，tmp用来释放内存
    pNode = stack->top->next;     // 将栈顶指向节点赋值给pNode
    while(pNode != NULL){
        tmp = pNode;              // 记住需要释放的内存地址
        pNode = pNode->next;
        free(tmp);                // 释放该地址的内存
    }
}

销毁整个栈

void Destory(Stack *stack){
    CleanStack(stack);      // 首先清空栈
    free(stack->top);       // 释放栈
}

下面是完整的代码

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


typedef struct Node
{
    int value;         // 节点的值
    struct Node *next; //  下一个节点的地址
} Node;
typedef struct
{
    Node *top; // 栈顶，指向首个节点的地址
} Stack;
void InitStack(Stack *stack)
{
    stack->top = (Node *)malloc(sizeof(Node)); // 为栈顶申请内存
    stack->top->next = NULL;                   // 将栈顶的指向的下一个节点置为空，防止出现野指针
}
void Push(Stack *stack, int value)
{
    Node *node;                          // 创建新节点
    node = (Node *)malloc(sizeof(Node)); // 为节点申请内存
    node->value = value;                 // 为节点赋值
    node->next = stack->top->next;       // 将栈顶指向的节点放在新创的节点之后
    stack->top->next = node;             // 将栈顶指向新的节点
}
Node *Pop(Stack *stack)
{
    Node *del = NULL;       // 创建一个空节点用来储存首个节点
    del = stack->top->next; // 将栈的首个节点赋值给刚刚创建的空节点
    if (del != NULL)
    {                                 // 判断栈内是否有节点
        stack->top->next = del->next; // 将栈顶指向下一个节点
    }
    return del;
}
int Length(Stack *stack)
{
    int length = 0;
    Node *nNode;              // 创建新节点
    nNode = stack->top->next; // 将栈顶指向节点赋值给新节点
    while (nNode != NULL)     // 判断是否循环到队尾
    {
        length++;
        nNode = nNode->next; // 将指针指向下一个节点
    }
    return length;
}
void NodeDisPlay(Node *node)
{
    printf("This Node Value is %d.\n", node->value);
}
void StackDisplay(Stack *stack)
{
    Node *nNode;              // 创建新节点
    nNode = stack->top->next; // 将栈顶指向节点赋值给新节点
    while (nNode != NULL)     // 判断是否循环到队尾
    {
        NodeDisPlay(nNode);  // 显示当前节点的值
        nNode = nNode->next; // 将指针指向下一个节点
    }
}
void CleanStack(Stack *stack)
{
    Node *pNode, *tmp;        // pNode节点用来存储栈节点，tmp用来释放内存
    pNode = stack->top->next; // 将栈顶指向节点赋值给pNode
    while (pNode != NULL)
    {
        tmp = pNode; // 记住需要释放的内存地址
        pNode = pNode->next;
        free(tmp); // 释放该地址的内存
    }
}
void Destory(Stack *stack)
{
    CleanStack(stack); // 首先清空栈
    free(stack->top);  // 释放栈
}

int main()
{
    Stack *stack;  
    InitStack(stack);
    Push(stack, 1);
    Push(stack, 2);
    Push(stack, 3);
    StackDisplay(stack);
    printf("This Stack's length is %d.\n",Length(stack));
    Node *newNode = Pop(stack);
    printf("This Stack's length is %d.\n", Length(stack));
    NodeDisPlay(newNode);
    StackDisplay(stack);
    Destory(stack);
    return 0;
}

栈的链式存储实现过程

推荐阅读更多精彩内容