#include <stdio.h>
#include<stdbool.h>		//引入bool数据类型
#define MaxSize 10        //定义最大长度
typedef int ElemType;    //定义数据元素类型为整型

//顺序表
// c

typedef struct
{
    int data[MaxSize];    //用静态的"数组"存放数据元素
    int length;            //顺序表的当前长度（总长度）
}SqList;                //顺序表的类型定义


void InitList(SqList* L);
bool ListInsert(SqList* L,int i,int e);
bool ListDelete(SqList* L,int i,int* e);
ElemType GetElem(SqList L, int i);
int LocateElem(SqList L, ElemType e);
void TraverseList(SqList L);
/*关于销毁
- 静态分配：静态数组，系统自动回收空间。
- 动态分配：动态数组（malloc、 free），需要手动free。*/


int main() {
  SqList L;        //声明一个顺序表L
  int number; 		//number为元素个数
  ElemType value;  //value为查找的元素值

  InitList(&L);    //初始化顺序表L

  printf("请输入需要插入的元素个数:");
  scanf("%d",&number);
    printf("依次输入%d个元素:",number);
  for(int i=1; i<=number; i++){
    scanf("%d",&value);
    ListInsert(&L, i, value);  //在顺序表L的第1个位置插入元素value
  }
  TraverseList(L);  //输出顺序表L


  ListInsert(&L, 1, 11);  //在顺序表L的第1个位置插入元素11
  printf("插入之后的顺序表：");
  TraverseList(L);  //输出顺序表L

  printf("L的第1个位置的元素值：");
  printf("%d\n", GetElem(L, 1));  //获取顺序表L的第1个位置的元素值

  printf("查找元素值为11的元素的位序：");
  printf("%d\n", LocateElem(L, 11));  //查找元素值为11的元素，返回其位序

  ElemType e;
  ListDelete(&L, 1, &e);  //删除顺序表L的第1个位置的元素，并用e返回其值
  printf("返回刚删除的e的值：%d\n", e);
  TraverseList(L);  //输出顺序表L

  return 0;
}


//----------------------------------------------------
//基本操作：初始化一个顺序表
void InitList(SqList* L){
    for(int i=0; i<MaxSize; i++) //MaxSize是顺序表的最大长度L->length
        L->data[i]=0;    //将所有数据元素设置为默认初始值0
    L->length=0;            //顺序表初始长度为0
}

// 插入：在表L中的第i个位置上插入指定元素e。
//把新的数据插入的目标位置之后，把目标位置后面的数据依次向后进行移动。O(n)
bool ListInsert(SqList* L,int i,int e){
    if(i<1 || i>L->length+1)    //判断i的范围是否有效
        return false;
    if(L->length>=MaxSize)    //当前存储空间已满，不能插入
        return false;

    for(int j=L->length; j>=i; j--) //将第i个元素及之后的元素后移
        L->data[j]=L->data[j-1];
    L->data[i-1]=e;        //在位置i处放入新的数据e
    L->length++;            //长度加1
    return true;
}

// 删除。删除表L中第i个位置的元素，并用e返回删除元素的值。
//O(n)
bool ListDelete(SqList* L,int i,int* e){
    if(i<0||i>L->length)//判断i的范围是否有效
        return false;
    *e=L->data[i-1];//将被删除的元素赋值给e
    for(int j=i;j<L->length;j++)//将第i个位置后的元素前移
        L->data[j-1]=L->data[j];
    L->length--;//线性表长度减1
    return true;
}

// 按位查找操作。获取表L中第i个位置的元素的值。
//O(1)
ElemType GetElem(SqList L, int i){
    if(i<0 || i>L.length)//判断i的范围是否有效
        return NULL;
    return L.data[i-1];
}

// 按值查找操作。在表L中查找具有给定关键字值的元素。
//O(n)
int LocateElem(SqList L, ElemType e){
  for(int i=0;i<L.length;i++)
    if(L.data[i]==e)
      return i+1;    //数组下标为i的元素值等于e，返回其位序i+1
  return -1;//退出循环，说明查找失败
}

// 遍历
void TraverseList(SqList L){
  for(int i=0; i<L.length; i++)
    printf("%d  ", L.data[i]);
  printf("\n");
}

#include<stdio.h>
#include<stdbool.h>		//引入bool数据类型
#include<stdlib.h>
typedef int ElemType;    //定义数据元素类型为整型

//创建单链表Singly Linked List
// c
// 要使用双指针初始化

// Define a structure for a node in the linked list
// 定义链表中节点的结构
typedef struct LNode{
    ElemType data;        //每个结点存放一个数据元素
    struct LNode *next;    //指针指向下一个节点
}LNode, *LinkList;


bool InitList(LinkList* L);	//初始化
bool Empty(LinkList L);		//判空

bool ListInsert(LinkList L, int i, ElemType e);//插入
bool InsertNextNode(LNode *p, ElemType e);		//后插
bool InsertPriorNode(LinkList L, LNode *p, ElemType e);//前插

bool ListDelete(LinkList L, int i, ElemType* e);	//按照位序删除元素
bool DeleteNode(LinkList L,LNode *p);          //删除指定的某一个元素
void DestroyList(LinkList* L);					//销毁

LNode* GetElem(LinkList L, int i);		    //按照位序查找
LNode* LocateElem(LinkList L, ElemType e);//按照给定的值查找

int Length(LinkList L);		//链表长度
void TraverseList(LinkList L);//遍历输出链表的所有元素

LinkList CreateListTail(int n);//尾插法建立链表


int main()
{
  LinkList L;
  InitList(&L);
  L = CreateListTail(5);
  printf("链表长度：%d\n", Length(L));

//-------------------------测试代码-----------------------
// 查找
    //查找第一个元素
    LNode *p = GetElem(L, 1);
    if(p){
        printf("查找第一个元素：%d\n", p->data);
    }else{
        printf("查找失败\n");
    }

    //查找3
    p = LocateElem(L, 3);
    if(p){
        printf("查找3成功：%d\n", p->data);
    }else{
        printf("查找3失败\n");
    }


// 插入
    printf("在第1个位置插入100：");
    ListInsert(L, 1, 100);
    TraverseList(L);

    printf("在第6个位置,后插入200：");
    if( InsertNextNode(GetElem(L, 6), 200) ){
        printf("后插成功\n");
    }
    else{
        printf("后插失败\n");
    }
    TraverseList(L);

    printf("在第1个位置,前插入300：");
    if( InsertPriorNode(L, GetElem(L, 1), 300) ){
        printf("前插成功\n");
    }
    else{
        printf("前插失败\n");
    }
    TraverseList(L);


// 删除
ElemType e=0;
    printf("删除第8个位置的元素：");
    if( ListDelete(L, 8, &e) ){
        printf("删除成功，删除的元素是：%d\n", e);
    }
    else{
        printf("删除失败\n");
    }
    TraverseList(L);

    printf("删除结点1：");
    // printf("%d",GetElem(L, 1)->data);
    if( DeleteNode(L, GetElem(L, 1))){
        printf("删除成功\n");
    }
    else{
        printf("删除失败\n");
    }
    TraverseList(L);

// 销毁
    printf("销毁链表：");
    DestroyList(&L);
    TraverseList(L);
//-----------------------------------------

  return 0;
}


//----------------------------------------------------------
//初始化一个单链表（带头结点）
bool InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(LNode)); // Allocate memory for the head node
    if (*L == NULL) {
        return false; // Allocation failed
    }
    (*L)->next = NULL; // Initialize the next pointer of the head node
    return true;
}

// 判断单链表是否为空（带头结点）
bool Empty(LinkList L){
    return L==NULL ? true : false;
}

/**
 *
 * @brief 按位序插入(带头结点)：在表L中的第i个位置上插入指定元素e。
 * @details 在 i 位置插入e，相当于在 i 前面 i-1 位置后插入e，所以Get查找的是i-1。
 * 时间复杂度O(n)
 * @note step1.判断插入的是不是头结点，如果是则false;
 * step2.循环找到第i-1个结点;
 * step3.判断i-1的合法性;
 * step4.在i-1之后插入新结点。
 *
 * @param L
 * @param i
 * @param e
 * @return true
 * @return false
 *
 */
bool ListInsert(LinkList L, int i, ElemType e){
    //step1判断插入的是不是头结点，如果是则false。
    if(i<1)        //位序0是头结点
        return false;

    //step2循环找到第i-1个结点。
    //这样p就是i前一个结点，插入p的后面
    LNode *p = GetElem(L, i-1);

  //step3判断i-1的合法性。
    if(p==NULL)     //i-1值不合法
        return false;

  //step4在i-1之后插入新结点。
    LNode *newNode = (LNode *)malloc(sizeof(LNode));//新结点
    newNode->data = e;
    newNode->next = p->next;
    p->next = newNode;    //将结点newNode连到p之后
    return true;    //插入成功
}

//后插操作：在p结点之后插入元素e
//时间复杂度O(1)
bool InsertNextNode(LNode *p, ElemType e){
    if (Empty(p))
        return false;
    LNode *newNode = (LNode *)malloc(sizeof(LNode));
    if (newNode==NULL)    //内存分配失败
        return false;

    newNode->data = e;        //用结点newNode保存数据元素e
    newNode->next = p->next;
    p->next = newNode;        //将结点newNode连到p之后
    return true;
}

//前插操作：在表L中的指定p结点之前插入元素e
//两种方法：
//	1是朴素的遍历一遍，然后在p-1后面插入e; 时间复杂度O(n)
//	2是在新建一个结点，存放p的内容，链接p->next，这样它就变成了p，这时候p就可以赋值为新的结点了。时间复杂度O(1)
bool InsertPriorNode(LinkList L, LNode *p, ElemType e){
    if (Empty(p) || p==L)   //插入头结点or空结点前面
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL)    //内存分配失败
        return false;

    s->next = p->next;
    p->next = s;    	//新结点s连到p之后
    s->data = p->data;  //将p中元素复制到s中
    p->data = e;    	//p中元素覆盖为e
    return true;
}


/**
 * @brief 按位序删除元素(带头结点)：删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
 * @details 因为无法获取链表里面一个结点的上一个结点，所以这里直接获取 i-1 结点，来删除 i 结点。
 * 时间复杂度O(n)
 * @note step1.新建节点q指向要删除的i结点;
 * step2.用e返回删除的结点内容;
 * step3.i-1结点直接指向i的下一个结点(q->next)，来断开i结点;
 * step4.释放i的空间(释放q)。
 *
 * @param L
 * @param i
 * @return ElemType
 */
bool ListDelete(LinkList L, int i, ElemType* e){
    if(i<1 || i>Length(L))
      	return false;

    //因为无法获取链表里面一个结点的上一个结点，所以这里直接获取 i-1 结点，来删除 i 结点。
    LNode *p = GetElem(L, i-1);    //获取第i-1元素
    if(p==NULL)    //i-1值不合法
        return false;

    LNode *q = p->next; //令q指向被删除结点（拿到结点），也就是p->next
    *e = q->data;        //用e返回元素的值
    p->next = q->next;  //将*q结点从链中“断开”
    free(q);            //释放结点的存储空间
    return true;        //删除成功
}


/**
 * @brief 指定结点删除：删除表L中指定的某一个结点p。
 * @details 时间复杂度O(1)
 * @note 解释：1->2->3->4。
 * 若要删掉1，可以先令前两个数据交换，2->1->3->4;
 * 再让1的指针链断开，令2指向3： 2->（1）-3->4;
 * 把1断开，于是就是2->3->4。
 *
 *【注意】如果p结点是最后一个结点则无法使用这种，只能依次遍历。
 *
 * @param L
 * @param p
 * @return true
 * @return false
 */
bool DeleteNode(LinkList L, LNode *p){
    if(p == NULL || p==L)        //若删除的节点为空结点或者头结点，操作无效
        return false;

    if(p->next != NULL){       //p是最后一个结点，则next=NULL，操作无效
        LNode *q = p->next;    //定义一个q指针，令q指向*p的后继结点
        p->data = q->data;     //和后继结点交换数据域，相当于将p节点的后一个结点的数据赋值到p结点中
        p->next = q->next;  //将*q结点从链中“断开”
        free(q);            //释放结点的存储空间
        return true;        //删除成功
    }
    return false;
}


//销毁一个单链表
//时间复杂度O(n)
void DestroyList(LinkList* L){
    LNode *current = (*L)->next;
    //循环释放各个数据结点
    while(current != NULL){    //判断头结点是否有后继结点，直到头结点后再无其他结点结束循环
        LNode *q = current;    //令q指向被删除结点（拿到结点）
        current = q->next;    //将*q结点从链中“断开”
        free(q);            //释放结点的存储空间
    }
    free(current);                //释放头结点
    free(*L);
    *L = NULL;          //头指针指向NULL
}


//按位查找：获取表L中第i个位置的元素的值。
//时间复杂度O(n)
LNode* GetElem(LinkList L, int i)
{
    if(i<0)        //判断i是否合法。i<0，那么头结点也可以返回。
        return NULL;
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p=L;            //L指向头结点,头结点是第0个结点（不存数据）

    while(p!=NULL && j<i){   //寻找第i个结点
        p=p->next;    //让p指针依次往后移
        j++;
    }
    return p;
}

//按值查找：在表L中查找具有给定关键字值的元素。
//时间复杂度O(n)
LNode* LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    //从第1个结点开始查找数据域为e的结点
    while(p != NULL && p->data != e)
        p = p->next;
    return p;    //找到后返回该结点指针，否则返回NULL
}


//求表的长度(带头结点，但是统计的时候不带头结点的数量)
//时间复杂度O(n)
int Length(LinkList L){
    int len = 0;    //统计表长
    LNode* p=L;
    while (p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

//链表的遍历输出
void TraverseList(LinkList L){
    if(!Empty(L)){
        LNode *p, *x;
        p = L;//将头指针赋值给p
        while(p->next != NULL){
            x = p->next;
            printf("%d ", x->data);
            p = p->next;
        }
        printf("\n");
    }
    else{
        printf("链表为空！\n");
    }
}


//尾插法建立链表
//时间复杂度O(n)
LinkList CreateListTail(int n) {//输入几个结点
    LNode *p;
    LNode *r;
    int i;

    //新建单链表L
    LinkList L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;//头结点
    L->data = 0;//防止脏数据
    r = L;//尾指针等于当前头结点

    //放入0 1 2 3...n
    for(i=0; i<n; i++){
        p = (LNode*)malloc(sizeof(LNode));//每次动态申请一个结构体空间存储
        p->data = i;
        r->next = p;
        r = p;//尾指针后移
    }
    r->next = NULL;
    return L;
}

#include<stdio.h>
#include<stdbool.h>		//引入bool数据类型
#include<stdlib.h>
typedef int ElemType;

// 创建双链表（Doubly Linked List）
// c

typedef struct DNode{
    ElemType data;              //数据域
    struct DNode *prior, *next;  //前驱和后继指针
}DNode, *DLinkList;


bool InitDLinkList(DLinkList* L);
bool Empty(DLinkList L);
int Length(DLinkList L);
bool InsertNextDNode(DNode *p, DNode *s);
bool DeleteNextDNode(DNode *p);
void DestroyDList(DLinkList* L);
bool BackwardTraverseList(DLinkList L_head);
void ForwardTraverseList(DLinkList L_tail);


//主函数
int main(){
    DLinkList L;
    InitDLinkList(&L);


    //插入
    int n=5;
    for(int i=1; i<n+1; i++){
        DNode * p = (DNode*)malloc(sizeof(DNode));//每次动态申请一个结构体空间存储
        DNode * tail=L;
        p->data = i;
        InsertNextDNode(tail,p);
        tail = p;   //尾指针后移
    }
    printf("Insert %d DNode: ",n);
    BackwardTraverseList(L);

    //删除L
    DeleteNextDNode(L);
    printf("DeleteNextDNode(L): ");
    BackwardTraverseList(L);

    //求双链表的长度
    printf("Length of DLinkList is %d\n",Length(L));

    //判断双链表是否为空
    if(Empty(L))
        printf("DLinkList is empty\n");
    else
        printf("DLinkList is not empty\n");

    //销毁双链表
    DestroyDList(&L);

    //向后遍历
    printf("BackwardTraverseList: ");
    if(!BackwardTraverseList(L)){
        printf("DLinkList is empty\n");
    }

    return 0;
}


//------------------------------------------------------------------
//初始化双链表
bool InitDLinkList(DLinkList* L){
    *L = (DLinkList)malloc(sizeof(DNode));//分配一个头结点
    if(L == NULL)            //内存不足，分配失败
        return false;

    (*L)->prior = NULL;        //头结点的前驱prior永远指向NULL
    (*L)->next = NULL;         //头结点之后暂时还没有结点
    return true;
}


//判断双链表是否为空（带头结点）
bool Empty(DLinkList L){
    if(L->next == NULL)
        return true;
    else
        return false;
}


//求双链表的长度（带头结点）
int Length(DLinkList L){
    DNode *p = L->next;      //p指向第一个结点
    int j=0;                 //计数器
    while(p){
        j++;
        p = p->next;
    }
    return j;
}


//插入：在p结点之后插入s结点。
//就是更改前驱后继的指针，插入新结点。
bool InsertNextDNode(DNode *p, DNode *s){
    if (p == NULL || s == NULL) //非法参数
        return false;

    //和后继的联系
    s->next = p->next;
    if(p->next != NULL){     //如果p结点有后继结点才可以进去这个后继节点，如果p是最后一个结点，则后继为NULL
        p->next->prior = s;
    }

    //和前驱的联系
    s->prior = p;
    p->next = s;

    return true;//插入成功
}


//删除：删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p == NULL)
        return false;
    DNode *q = p->next; //p的后继结点q
    if(q == NULL)
        return false;   //p没有后继结点

    p->next = q->next;  //使原本指向q的p的后继指向q的后继
    if(q->next != NULL) //q结点不是最后一个结点
        q->next->prior = p;
    free(q);     //释放结点空间
    return true; //删除成功
}


//销毁一个双链表
void DestroyDList(DLinkList* L){
    //循环释放各个数据结点
    while((*L)->next != NULL){ //判断头结点是否有后继结点，直到头结点后再无其他结点结束循环
        DeleteNextDNode(*L); //删除L结点的后继结点
    }
    free(*L);                //释放头结点
    *L = NULL;
}


//向后遍历双链表
bool BackwardTraverseList(DLinkList L_head){
    if(L_head == NULL)
        return false;   //空链表
    DNode *p = L_head->next;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return true;
}


//向前遍历
// 有bug
// void ForwardTraverseList(DLinkList L_tail){
//     DNode *p = L_tail->next;
//     while(p){
//         printf("%d ",p->data);
//         p = p->prior;
//     }
//     printf("\n");
// }

#include<stdio.h>
#include<stdbool.h>		//引入bool数据类型
#include <assert.h>		//引入断言
#include<Windows.h>

#define MaxSize 5				//栈最大可以存放的元素个数
typedef int ElemType;		//顺序栈存储的数据类型、用int代替ElemType

//创建顺序栈
// c
// top从-1开始
typedef struct
{
  ElemType data[MaxSize];  //栈底指针
  int top;		 //栈顶的位置 如 0、1、2、3、4....MaxSize
} SqStack;			 //顺序栈的结构体定义


bool InitStack(SqStack* stack);	//初始化栈
bool StackEmpty(SqStack stack);//判断是否为空
bool StackFull(SqStack stack);	//判断是否已满
int GetStackSize(SqStack stack);//获取顺序栈中元素个数

bool Push(SqStack* stack, ElemType value);//入栈
bool Pop(SqStack* stack, ElemType* value);//出栈
ElemType GetTop(SqStack stack);//获取栈顶的元素


//------------------------------------------------------
void PushStack(SqStack* stack){
    int number;
    ElemType value = 0;

    printf("请输入需要插入的元素个数:");
  scanf("%d",&number);

  while (number > 0){
    scanf("%d",&value);
    Push(stack, value);	//放入栈
    number--;
  }
}

int main()
{
  SqStack	stack;		//创建顺序栈
  InitStack(&stack);	//初始化顺序栈
    ElemType value = 5;      //插入5个元素
//例如插入5,4,3,2,1
    while (value > 0){
    Push(&stack, value);	//放入栈
    value--;
  }


  //获取栈顶的元素
  printf("当前栈顶的元素是：%d\n",GetTop(stack));

  //获取栈的元素个数
  printf("当前栈的元素个数是：%d\n",GetStackSize(stack));

  //出栈1个
  Pop(&stack, &value);
  printf("出栈元素是：%d\n",value);

  printf("出栈1个后的出栈顺序：\n");
  while (!StackEmpty(stack)){
    Pop(&stack, &value);
    printf("%d ",value);
  }
  printf("\n");
  return 0;
}


//----------------------------------------------------------------------
//初始化顺序栈
//初始化有两种方式：top=-1 或者 top=0
bool InitStack(SqStack* stack){
  assert(stack); // 这里一定要断言，如果是空指针的话，就无法找到整个数组

  stack->top = -1;		//初始化栈顶指针的位置为-1
  return true;
}

//判断栈空
bool StackEmpty(SqStack stack){
  if (stack.top == -1)
    return true;
  else
    return false;
}

//判断栈满
bool StackFull(SqStack stack){
  //top的位置值等于MaxSize时栈满,因为数据是从0开始的
  if (stack.top == MaxSize-1){
        printf("栈满\n");
    return true;
    }
  else
    return false;
}

//顺序栈中元素个数
int GetStackSize(SqStack stack){
  return stack.top+1;  //栈顶位置即top的数值，就是栈中元素的个数
}

/**
 * @brief 入栈:
 * 开辟一个新的空间,栈顶+1,然后将数据存入stack.data[stack.top]所在的位置.
 *
 * @param stack
 * @param value
 * @return true
 * @return false
 */
bool Push(SqStack* stack, ElemType value){
  if (StackFull(*stack)){
    return false;
  }
  //若栈未满，执行入栈操作
  stack->top++;		//栈顶自增1
  stack->data[stack->top] = value;    //以栈顶位置作为下标存储数据
  return true;
}

/**
 * @brief 出栈:
 * 读取栈顶stack.data[stack.top]的元素,然后使栈顶-1.
 *
 * @param stack
 * @param value
 * @return true
 * @return false
 */
bool Pop(SqStack* stack, ElemType* value){
  if(StackEmpty(*stack)){
    return false;
  }
  *value = stack->data[stack->top];	//以栈顶位置作为下标的值赋值给value返回
  stack->top--;	//栈顶自减1
  return true;
}

//读取栈顶元素
ElemType GetTop(SqStack stack){
  if(StackEmpty(stack)){
    printf("栈为空");
    return false;
  }
  return stack.data[stack.top];
}

//销毁栈、释放栈的内存
// 顺序栈是在声明栈时直接分配内存，并没有使用`malloc`函数，所以不需要手动`free`，函数运行结束后系统自动回收空间。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>		//引入bool数据类型

typedef int SElemType;  //链栈的数据元素类型假设为int整型

//创建链栈结构
// c

typedef struct StackNode
{
  SElemType data;   				//结点数据域
  struct StackNode* next;			//结点指针域
}StackNode, *LinkStack;				//struct StackNode的结点形式、链栈形式别名

void InitStack(LinkStack* stack);					//初始化链栈
bool StackEmpty(LinkStack stack);					//链栈判空
int StackLength(LinkStack stack);					//计算链栈长度元素个数
bool PushStack(LinkStack* stack, SElemType value);	//入栈
bool PopStack(LinkStack* stack, SElemType* value);	//出栈
SElemType GetTop(LinkStack stack);				//获取栈顶元素
bool StackPrint(LinkStack stack);					//遍历元素
void DestroyStack(LinkStack* stack);				//销毁链栈，释放内存


int main()
{
  //创建链栈
  LinkStack stack;
  SElemType value=1;

  InitStack(&stack);
  int number = 4;	//插入元素个数

  while ((number--) > 0) {
    PushStack(&stack, value);//插入所输入元素
        value++;
  }

  printf("当前栈的元素个数：%d\n",StackLength(stack));

  printf("栈顶元素：%d\n",GetTop(stack));
  StackPrint(stack);//遍历打印栈顶元素

  PopStack(&stack, &value);
  printf("出栈一次,栈顶元素为：%d\n",value);
  StackPrint(stack);

  DestroyStack(&stack);
  printf("栈已被销毁释放\n");
  printf("销毁栈后遍历栈结果： ");
  StackPrint(stack);

  // system("pause");
  return 0;
}


//链栈的初始化
void InitStack(LinkStack* stack){
  //构造一个空栈、栈顶指针置为空
  *stack = NULL;
}

//判断链栈是否为空
bool StackEmpty(LinkStack stack){
  return stack==NULL? true : false;
}


/**
 * @brief 获取栈顶长度。
 * 因为链表的最后一个节点的next指针是nullptr（或者说是NULL），代表链表的终止，
 * 所以可以将链表的遍历条件设置为当前节点指针不等于nullptr，这样在遍历过程中，
 * 当指针指向最后一个节点时，其next指针就会指向nullptr，循环条件就不再成立，
 * 遍历结束，可以避免继续遍历下一个不合法的节点。
 * @param stack
 * @return int
 */
int StackLength(LinkStack stack){
  int length = 0;
  StackNode* temp = stack;//创建临时指针temp与stack指向同一位置
  while (temp != NULL){
    length++;  			//链栈长度即为栈中元素个数，循环一次，长度++
    temp = temp->next; 	//temp指针下移一位
  }
  return length; 			//返回链栈长度
}

//入栈（前插法）
bool PushStack(LinkStack* stack, SElemType value){   //不用判栈满
  StackNode* temp = (StackNode*)malloc(sizeof(StackNode));//生成新结点temp
  temp->data = value; 	//将新节点数据域置为value
  temp->next = *stack; 	//将新结点插入栈顶
  *stack = temp; 			//更新栈顶指针
  return true;
}

//出栈：首先判空
bool PopStack(LinkStack* stack, SElemType* value){
  if (StackEmpty(*stack)){
    return false;
  }
  *value = (*stack)->data;  		//将栈顶数据域元素赋值给value
  StackNode* temp = *stack;	//创建一个temp指针，并将其指向 stack 指针所指向的内存地址，以便找到出栈位置并释放。
  *stack = (*stack)->next; 		//令栈顶指针指向下一位结点，即更新栈顶指针
  free(temp);   				//释放temp所指向的空间，即出栈元素所占的内存空间，temp本身会在函数结束后自动销毁。
  return true;
}

//取栈顶元素
SElemType GetTop(LinkStack stack){
  if (!StackEmpty(stack)){  	//若栈不为空		//返回栈顶元素
    return stack->data;
  }
  return NULL;
}


//遍历输出栈元素
bool StackPrint(LinkStack stack){
  if (stack != NULL){
    StackNode* temp = stack;	//创建一个指针与stack指向同一位置
    printf("出栈顺序：");
    while (temp != NULL){
      printf("%d ",temp->data);
      temp = temp->next;  		//temp向下移动一位
    }
    printf("\n");
    return true;
  }
  printf("栈为空\n");
  return false;
}


//销毁链栈，释放内存
void DestroyStack(LinkStack* stack){
  if (StackEmpty(*stack)) return;

  StackNode* current = *stack;
  while (current != NULL){
    StackNode* q = current;	//创建一个临时指针q，指向current所指向的内存地址
    current = q->next;	//更新栈顶指针
    free(q);			//释放q所指向的空间，即释放出栈元素所占的内存空间
  }
  free(current);		//释放临时指针
  *stack = NULL;
}