栈---链栈（C++）

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有都是在单链表的表头进行的。

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。

链栈的实现（不带头结点）

栈的顺序存储类型：

typedef struct ListNode {
 ElemType data;//数据域
 ListNode* next;//指针域
}ListNode,*LinkStack;

初始化：

void InitStack(LiStack& s) {
 s = NULL;
}

判断链栈是否为空：

bool StackEmpty(LiStack s) {
 if (s == NULL) {
  return true;
 }
 else {
  return false;
 }
}

入栈（头插法）：链表不考虑栈满的情况

void Push(LiStack& s, ElemType x) {
 LinkNode* p = new LinkNode;
 if (p == NULL) {//申请空间失败
  return;
 }
 //头插法，插入链表
 p->data = x;
 p->next = s;
 s = p;
}

出栈：

void Pop(LiStack& s, ElemType& x) {
 if (s == NULL) {//栈空
  return;
 }
 //从表头开始删除
 x = s->data;
 LinkNode* p = s;
 s = s->next;
 free(p);
}

读栈顶元素：

ElemType GetTop(LiStack s) {
 if (s == NULL) {//栈空
  return -1;
 }
 return s->data;
}

销毁栈：

void DestoryStack(LiStack& s) {
 s->next = NULL;
 free(s);
}