链式栈

以链表作为基础实现栈空间（链式栈）

/********************************************************************************
 *
 *  file name:  LinkedStack.c
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  function :  实现链式栈的入栈（Push）与出栈（Pop）
 *  note     :  None
 *
 *  CopyRight  (c)  2023-2024   [email protected]    All  Right  Reseverd
 *   ****************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// 链栈中的元素的数据类型，用户可以根据需求进行修改
typedef int DataType_t;

// 构建记录链栈LinkedStack的各项参数（栈底地址，栈容量，栈顶元素的小标）的结构体
typedef struct LinkedStack
{
    struct LinkedStack *next;
    DataType_t data;
} LinkStack_t;

/************************************************************************
 *  name     :  LinkStack_Dreate
 *  function :  创建一个空的链栈，并对数据域与指针域进行初始化
 *  argument :  None
 *
 *
 *  retval   :  返回头结点的地址
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  note     :  None
 *   *********************************************************************/
LinkStack_t *LinkStack_Create(void)
{
    // 创建一个头结点并对头结点申请内存
    LinkStack_t *Head = (LinkStack_t *)calloc(1, sizeof(LinkStack_t));
    // 判断申请堆内存是否成功
    if (NULL == Head)
    {
        perror("calloc memroy from Head is failed");
        exit(-1);
    }

    // 进行初始化
    Head->next = NULL;

    return Head;
}


/************************************************************************
 *  name     :  LinkStack_NewNode
 *  function :  创建一个新的结点并对数据域与指针域进行初始化
 *  argument :
 *              @Data :入栈的数据
 *
 *  retval   :  返回新结点的地址
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  note     :  None
 *   *********************************************************************/
LinkStack_t *LinkStack_NewNode(DataType_t Data)
{
    // 1.创建一个新结点并对新结点申请内存
    LinkStack_t *New = (LinkStack_t *)calloc(1, sizeof(LinkStack_t));
    if (NULL == New)
    {
        perror("Calloc memory for NewNode is Failed");
        return NULL;
    }

    // 对新结点的指针域与数据域进行初始化
    New->data = Data;
    New->next = NULL;

    return New;
}


/************************************************************************
 *  name     :  LinkStack_Push
 *  function :  入栈
 *  argument :  
 *              @Head :头结点的地址
 *              @Data :入栈的数据
 *  retval   :  true and false
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  note     :  None
 *   *********************************************************************/
bool LinkStack_Push(LinkStack_t *Head, DataType_t Data)
{
    // 创建一个新的结点
    LinkStack_t *New = LinkStack_NewNode(Data);
    if (NULL == New)
    {
        printf("can not insert new node!\n");
        return false;
    }

    // 如果链栈为空
    if (NULL == Head->next)
    {
        // 头结点的next指针指向新结点
        Head->next = New;
        return true;
    }

    // 链栈为非空
    New->next = Head->next; // 新结点的next指针指向首结点
    Head->next = New;       // 头结点的next指针指向新结点

    return true;
}

/************************************************************************
 *  name     :  LinkStack_Pop
 *  function :  出栈
 *  argument :  
 *              @Head :头结点的地址
 *              
 *  retval   :  true and false
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  note     :  None
 *   *********************************************************************/
bool LinkStack_Pop(LinkStack_t *Head)
{
    LinkStack_t *Phead = Head->next; // 备份首结点
    // 判断链栈是否为空
    if (NULL == Head->next)
    {
        printf("Linked Stack is empty!\n");
        return false;
    }

    // 链栈不为空
    if (NULL == Phead->next) // 链栈中只有一个首结点
    {
        Head->next = NULL; // 头结点的next指针指向NULL
        free(Phead);       // 释放首结点内存
    }
    else
    {
        Head->next = Phead->next; // 头结点指向待删除结点的直接后继
        Phead->next = NULL;       // 待删除结点的next指针指向NULL
        free(Phead);              // 释放删除结点的内存
    }
}

/************************************************************************
 *  name     :  LinkStack_Print
 *  function :  遍历链式栈的每个结点并输出每个结点的数据与的值
 *  argument :  
 *              @Head :头结点的地址
 *              
 *  retval   :  true and false
 *  author   :  [email protected]
 *  date     :  2024/04/25
 *  note     :  None
 *   *********************************************************************/
bool LinkStack_Print(LinkStack_t *Head)
{
    // 对单向循环链表的头结点的地址进行备份
    LinkStack_t *Phead = Head;

    // 判断当前链表是否为空，为空则直接退出
    if (NULL == Head->next)
    {
        printf("current linked stack is empty!\n");
        return false;
    }

    // 从首结点开始遍历
    while (Phead->next)
    {
        // 把头结点的直接后继作为新的头结点
        Phead = Phead->next;

        // 输出头结点的直接后继的数据域
        printf("data = %d\n", Phead->data);

        // 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
        if (Phead->next == NULL)
        {
            break;
        }
    }

    return true;
}

int main(void)
{
    LinkStack_t *Head = LinkStack_Create();
    LinkStack_Push(Head, 1);
    LinkStack_Push(Head, 2);
    LinkStack_Push(Head, 3);
    LinkStack_Print(Head);

    LinkStack_Pop(Head);
    LinkStack_Pop(Head);
    LinkStack_Pop(Head);
    LinkStack_Pop(Head);
    LinkStack_Print(Head);
    LinkStack_Push(Head, 1);
    LinkStack_Print(Head);
}