Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/5.操作受限的线性表 -- 栈 -- 链栈.md

5.1  带头结点

#include <stdlib.h>

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
}SNode,*LinkStack;

//带头结点
bool InitLinkStack(LinkStack &linkStack) {
    SNode *pNode = (SNode *) malloc(sizeof(SNode));
    if (pNode == NULL) {
        return false;
    }
    linkStack = pNode;
    linkStack->next = NULL;
    return true;
}

bool IsEmpty(LinkStack linkStack) {
    if (linkStack->next == NULL) {
        return true;
    } else {
        return false;
    }
}

bool Push(LinkStack &linkStack, int e) {
    SNode *pNode = (SNode *) malloc(sizeof(SNode));
    if (pNode == NULL) {
        return false;
    }
    pNode->data = e;
    pNode->next = linkStack->next;
    linkStack->next = pNode;
    return true;
}

bool Pop(LinkStack &linkStack, int &e) {
    if (linkStack->next == NULL) {
        return false;
    }
    e = linkStack->next->data;
    linkStack->next = linkStack->next->next;
    free(linkStack->next);
    return true;
}

bool GetTop(LinkStack linkStack, int &e) {
    if (linkStack->next == NULL) {
        return false;
    }
    e = linkStack->next->data;
    return true;
}

5.2  不带头结点

#include <stdlib.h>

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} SNode, *LinkStack;

//不带头结点
bool InitLinkStack(LinkStack &linkStack) {
    linkStack = NULL;
    return true;
}

bool IsEmpty(LinkStack linkStack) {
    if (linkStack == NULL) {
        return true;
    } else {
        return false;
    }
}

bool Push(LinkStack &linkStack, int e) {
    SNode *pNode = (SNode *) malloc(sizeof(SNode));
    if (pNode == NULL) {
        return false;
    }
    pNode->data = e;
    pNode->next = linkStack;
    linkStack = pNode;
    return true;
}

bool Pop(LinkStack &linkStack, int &e) {
    if (linkStack == NULL) {
        return false;
    }
    SNode *topNode=LinkStack;
    e = topNode->data;
    linkStack = topNode->next;
    free(topNode);
    return true;
}

bool GetTop(LinkStack linkStack, int &e) {
    if (linkStack == NULL) {
        return false;
    }
    e = linkStack->data;
    return true;
}