数据结构小结——链式栈

上一篇介绍了顺序栈，和顺序表差不多，那么这篇介绍的链式栈和链表又差不多，个人认为它其实就是一个满足先入后出原则的链表。

不多说了，先看下它的结构：

typedef int StackData; //这个结构体定义的是栈中的节点 typedef struct _node { StackData data; struct _node *next; }Node; //这个结构体定义的是栈顶指针 typedef struct _linkStack { Node *top; }LinkStack;

首先第一步是创建栈，即给栈分配一段空间：

LinkStack *Create_Stack() { LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack)/sizeof(char)); if (s == NULL) { errno = MALLOC_ERROR; return NULL; } // 置空栈 s->top = NULL; return s; }

同链表一样，链式栈是不存在栈满这种情况的，除非机器的内存不够了，不过这种情况正常是不会发生的。但是栈空这种情况还是要判断一下的：

int StackEmpty (LinkStack *s) { if (s == NULL) { errno = ERROR; return FALSE; } return s->top == NULL; }

入栈操作即链表的尾插：

int Push (LinkStack *s, StackData x) { if (s == NULL) { errno = ERROR; return FALSE; } // 新建结点 Node* node = (Node*)malloc(sizeof(Node)/sizeof(char)); if (node == NULL) { errno = MALLOC_ERROR; return FALSE; } node->data = x; node->next = s->top; s->top = node; return TRUE; }

出栈即将栈顶元素取出来丢掉：

int Pop (LinkStack *s, StackData *x) { if (s == NULL) { errno = ERROR; return FALSE; } if (StackEmpty(s)) { errno = EMPTY_STACK; return FALSE; } Node *p = s->top; *x = p->data; s->top = p->next; free(p); return TRUE; }

栈的基本操作也就这些，需要完整代码请直接下载（免积分）