#define Maxlength 8

/**
 * 数据结构类型：顺序栈
 * 插入方法：尾插法
 * 是否有头节点：否
 * 说明：在主函数直接定义一个结构体节点，取地址作形参，避免使用malloc函数而考虑二重指针问题
 */

typedef struct Stack {
    int data[Maxlength];
    int top;      //结构体内不能赋值
}LStack;

int StackInit(LStack *L) { //初始化
    L->top = -1;
}

int StackIn(LStack* L,int x) {
    if(L->top == Maxlength-1) {
        return -1;   //栈满
    }
    L->data[++L->top] = x;
    return 1;
}

int StackOut(LStack* L){
    if(L->top == -1){
        return -1;
    }
    return L->data[L->top--];
}

/*
void main() {
    LStack p;
    StackInit(&p);
    StackIn(&p,1);
    StackIn(&p,2);
    StackIn(&p,3);
    printf("%d",StackOut(&p));
    printf("%d",StackOut(&p));
    printf("%d",StackOut(&p));
    printf("%d",StackOut(&p));
}
*/

#include <malloc.h>
#include "stdio.h"

/**
 * 数据结构类型：单链栈
 * 插入方法：头插法
 * 是否有头节点：否
 * 说明：函数返回头节点版本，在弹栈时只能选择弹出栈顶值（栈顶没有被删除）或者返回头节点（栈顶真正被删除）。
 */


typedef struct Linknode {
    int data;
    struct Linknode* next;
}LNode;


LNode* LinkStackIn(LNode* head,int x) {
    if(head == NULL) {   //判空
        head = (LNode*)malloc(sizeof(LNode));
        head->data = x;
        head->next = NULL;
        return head;
    }
    LNode* newnode = (LNode*)malloc(sizeof(LNode));
    newnode->data = x;
    newnode->next = head;
    head = newnode;
    return head;
}

int LinkStackOut(LNode* head){
    if(head == NULL) {
        return -1; //链表为空
    }
    int result = head->data;
    printf("result = %d\n",result);
    LNode* p = head;
    head = head->next;
    free(p);
    return head;
}

void LinkStackNull(LNode* head) {
    if(head == NULL) {
        printf("该栈为空\n");
    } else {
        printf("该栈不空\n");
    }
}
/*
void main(){
    LNode *head = NULL;
    head = LinkStackIn(head,6);
    head = LinkStackIn(head,1);
    head = LinkStackIn(head,2);
    head = LinkStackOut(head);
    head = LinkStackOut(head);
    LinkStackNull(head);
    head = LinkStackOut(head);
    LinkStackNull(head);
}
 */

`#include <malloc.h>
#include "stdio.h"

/**
 * 数据结构类型：双向链栈
 * 插入方法：尾插法
 * 是否有头节点：否
 * 说明：使用的是二重指针对链栈进行操作，当函数需要对链表进行修改时使用二重链表，才能将修改的结果同步到主函数。
 *      使用此方法，出栈时既可以弹栈，也能返回值
 */

typedef struct DLinkStack {
    struct DLinkStack* pre;    //前驱
    int data;
    struct DLinkStack* next;   //后继
}DLink;

void DStackIn(DLink** S,int x) {   //入栈
    if(*S == NULL) {
        *S = (DLink*) malloc(sizeof(DLink));
        (*S)->data = x;
        (*S)->pre = NULL;
        (*S)->next = NULL;
    } else {
        DLink *newNode = (DLink *) malloc(sizeof(DLink));
        newNode->data = x;
        newNode->pre = *S;
        (*S)->next = newNode;
        newNode->next = NULL;
        (*S) = newNode;
    }
}

int DStackOut(DLink** S) {
    if(*S == NULL) {
        return -1;
    }
    DLink *p = *S;
    *S = (*S)->pre;
    int result = p->data;
    free(p);
    return result;

}

void main() {
    DLink* L = NULL;
    DStackIn(&L,1);
    DStackIn(&L,2);
    DStackIn(&L,3);
    printf("%d",DStackOut(&L));
    printf("%d",DStackOut(&L));
}