【数据结构】栈的链表实现

1.构造结构体作为链表的节点

typedef struct Node{ int Date; struct Node *Next; } LinkStack;

2.建栈操作

为指针S分配一块空间，返回后作为链表的头节点。其后继为空，表示栈为空。向栈中压入元素后，它的直接后继就是栈顶元素。 LinkStack *CreateStack() { LinkStack *S; S = malloc(sizeof(struct Node)); S->Next = NULL; return S; }

3.判断栈是否为空

int IsEmpty(LinkStack *S) { return(S->Next == NULL); }

4.进栈操作

因为是链式存储，所以不须要检查栈是否已满。直接将新节点以首插法的方式插入链表头部即完成进栈操作。 void Push(LinkStack *S, int item) { LinkStack *TmpCell; TmpCell = (LinkStack*)malloc(sizeof(struct Node)); TmpCell->Date = item; TmpCell->Next = S->Next; S->Next = TmpCell; }

5.出栈操作

出栈前首先检查栈是否已空。 int Pop(LinkStack *S) { LinkStack *FirstCell; int TopElem; if(IsEmpty(S)){ printf("栈已空"); return NULL; } else{ FirstCell = S->Next; S->Next = FirstCell->Next; TopElem = FirstCell->Date; free(FirstCell); return TopElem; } }