数据结构学习笔记（七）——链栈

1 链栈:采用链式存储的栈。链栈的优点是不存在栈满上溢的情况（只有在内存溢出时才会出现栈满，通常不考虑）。规定栈的所有操作都是在单链表的表头进行，第一个数据节点是栈顶节点，最后一个节点是栈底节点。

2 链栈的各种算法如下:

链栈的基本算法一

（1）初始化栈InitStack(s)：建立一个新的空栈s,实际上创建链栈的头节点，并将其next域置为NULL

void InitStack(LiStack * &s){

s = (LiStack *)malloc(sizeof(LiStack));

s -> next = NULL;

}

（2）销毁栈，DestroyStack(s)：释放栈s占用的存储空间

void DestroyStack(LiStack * &s){

LiStack * p = s, * q = s -> next;

while(q != NULL){

free(p);

p = q;

q = p -> next;

}

free(p); // 此时p指向尾节点，释放其空间

}

（3） 判断栈是否为空StackEmpty(s)：栈s为空的条件是s -> next == NULL

bool StackEmpty(LiStack *s){

return (s -> next == NULL);

}

链栈的基本算法二

（4） 进栈Push(s,e):将新数据节点插入到头节点之后

void Push(LiStack * &s,ElemType e){

LiStack * p;

p = (LiStack *)malloc(sizeof(LiStack));

p -> data = e; // 新建元素e对应的节点 *p

p -> next = s -> next; // 插入*p节点作为开始节点

s -> data[s -> top] = e; // 元素e放在栈顶指针处

s -> next = p;

}

（5） 出栈Pop(s,e):在栈不为空的条件下，将头节点的指针域所指数据节点的数据域赋给e，然后将该数据节点删除

bool Pop(LiStack * &s,ElemType &e){

LiStack * p;

if(s -> next == NULL) // 栈为空的情况

return false;

p = s-> next; // p指向开始节点

e = p -> data;

s -> next = p -> next; // 删除*p节点

free(p); // 释放*p节点

return true;

}

（6）取栈顶元素GetTop(s,e):在栈不空的情况下，将头节点的指针域所指数据节点的数据域赋给e

bool GetTop(LiStack * &s,ElemType &e){

if(s -> next == NULL) // 栈为空的情况

return false;

e = s-> next -> data; // 取栈顶元素

return true;

}