数据结构的C++实现之栈的链式存储结构

数据结构的C++实现之栈的链式存储结构2013-08-17 Simba888888 当单链表限定只能在头部进行插入和删除操作的时候，即为链栈，一般我们会将单链表的头指针和栈的栈顶指针top合二为一，通常对链栈来说，是不需要头节点的，因为我们维护了栈顶指针。对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top = = NULL的时候。

示例代码：（改编自《大话数据结构》）

#include <iostream>using namespace std;typedef int ElemType;typedef struct Node{ElemType data;struct Node *next;} Node, *NodePtr;typedef struct LinkStack{NodePtr top; //栈顶指针int count; //元素个数} LinkStack;/*构造一个空栈 */bool InitStack（LinkStack *ps）{cout << "Init Stack ..." << endl;ps->top = NULL;ps->count = 0;return true;}/*置为空栈 */bool ClearStack（LinkStack *ps）{cout << "Clear Stack ..." << endl;if （ps->top == NULL）return true;NodePtr p = ps->top;NodePtr q;while （p）{q = p->next;free（p）;p = q;}ps->top = NULL;ps->count = 0;return true;}bool StackEmpty（LinkStack LS）{return LS.count == 0;}int StackLength（LinkStack LS）{cout << "Stack Length: ";return LS.count;}/* 返回栈顶元素 */bool GetTop（LinkStack LS, ElemType *pe）{*pe = LS.top->data;cout << "Get Top Item " << *pe << endl;return true;}/* 压栈 */bool Push（LinkStack *ps, ElemType Elem）{cout << "Push Item " << Elem << endl;NodePtr s = （NodePtr）malloc（sizeof（Node））;s->data = Elem;s->next = ps->top;ps->top = s;ps->count++;return true;}/* 出栈 */bool Pop（LinkStack *ps, ElemType *pe）{NodePtr p = ps->top;*pe = p->data;ps->top = p->next;free（p）;ps->count--;cout << "Pop Item " << *pe << endl;return true;}/* 输出栈元素 */bool StackTraverse（LinkStack LS）{cout << "Stack Traverse ..." << endl;NodePtr p = LS.top;while （p ！= NULL）{cout << p->data << " ";p = p->next;}cout << endl;return true;}int main（void）{LinkStack LS;InitStack（&LS）;for （int i = 0; i < 5; i++）Push（&LS, i）;StackTraverse（LS）;int result;GetTop（LS, &result）;Pop（&LS, &result）;StackTraverse（LS）;if （！StackEmpty（LS））cout << StackLength（LS） << endl;ClearStack（&LS）;StackTraverse（LS）;return 0;}

输出为：

如果栈的使用过程中元素变幻不可预料，有时很小，有时非常大，那么最好使用链栈，反之如果变化在可控范围内，建议使用顺序栈会更好一些。