顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用完而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用。
而对于链式栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间，另外当某个项目不使用时也可将内存返还给系统。
顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。
图3.2给出了顺序栈的进栈和出栈过程。
链栈即采用链表作为存储结构实现的栈。为便于操作，我们采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针，如图3.4所示。
 |
在图3.4中，top为栈顶指针，始终指向当前栈顶元素前面的头结点。若top->next=NULL，则代表栈空。采用链栈不必预先估计栈的最大容量，只要系统有可用空间，链栈就不会出现溢出。采用链栈时，栈的各种基本操作的实现与单链表的操作类似。对于链栈，在使用完毕时，应该释放其空间。
链栈的结构可用C语言定义如下：
typedef struct node
{
StackElementType data;
struct node *next;
}LinkStackNode;
typedef LinkStackNode *LinkStack;
顺序栈是数组实现。链式栈是链表实现。 顺序栈内存空间是连续的。 链式栈内存空间是不连续的.
头文件：stack.h
1 //stack.h 2 3 //定义函数结果状态代码 4 #define TRUE 1 5 #define FALSE 0 6 #define OK 1 7 #define ERROR 0 8 #define OVERFLOW -1 9 #define UNDERFLOW -2 10 11 //定义函数返回值类型 12 typedef int Status; 13 //定义链式栈的数据元素的类型 14 typedef int ElemType; 15 16 //定义链式栈的存储结构 17 struct LNode{ 18 ElemType data; //数据域 19 struct LNode *next; //指针域 20 }; 21 22 struct LStack{ 23 struct LNode *top; //栈顶指针 24 }; 25 26 //声明链式栈的基本操作 27 Status InitStack(LStack &s); //构造一个空栈 28 Status DestroyStack(LStack &s); //销毁一个栈 29 Status StackEmpty(LStack s); //判断是否为空栈 30 Status StackLength(LStack s); //返回栈的长度 31 Status Push(LStack &s,ElemType e); //元素入栈 32 Status Pop(LStack &s,ElemType &e); //元素出栈 33 Status GetTop(LStack s,ElemType &e); //返回栈顶元素 34 Status StackTraverse(LStack s); //遍历栈
实现函数：stack.cpp
1 //stack.cpp 2 3 #include"stack.h" 4 #include<iostream> 5 using namespace std; 6 7 Status InitStack(LStack &s) 8 //操作结果：构造一个空栈S 9 { 10 struct LNode *p; 11 p=(LNode *)malloc(sizeof(LNode)); 12 if(!p){ 13 cout<<"严重错误：链式栈初始分配头节点失败，程序退出"; 14 exit(ERROR); 15 } 16 s.top=p; 17 p->next=NULL; 18 return OK; 19 } 20 21 Status DestroyStack(LStack &s) 22 //初始条件：栈s已存在 23 //操作结果：栈s被销毁 24 { 25 struct LNode *p; 26 p=s.top; 27 while(p){ 28 s.top=p->next; 29 free(p); 30 p=s.top; 31 } 32 return OK; 33 } 34 35 Status StackEmpty(LStack s) 36 //初始条件：栈s已存在 37 //操作结果：若栈s为空栈，则返回TRUE，否则FALSE 38 { 39 if(s.top->next==NULL) return TRUE; 40 return FALSE; 41 } 42 43 Status StackLength(LStack s) 44 //初始条件：栈s已存在 45 //操作结果：返回s的元素个数，即栈的长度 46 { 47 int length=0; 48 struct LNode *p; 49 p=s.top; 50 while(p->next){ 51 length++; 52 p=p->next; 53 } 54 return length; 55 } 56 57 Status Push(LStack &s,ElemType e) 58 //初始条件：栈s已存在 59 //操作结果：插入元素e成为新的栈顶元素 60 61 { 62 struct LNode *p; 63 p=(LNode *)malloc(sizeof(LNode)); 64 if(!p)exit(OVERFLOW); 65 s.top->data=e; 66 p->next=s.top; 67 s.top=p; 68 return OK; 69 } 70 71 Status Pop(LStack &s,ElemType &e) 72 //初始条件：栈s已存在且非空 73 //操作结果：删除s的栈顶元素，并且用e返回其值 74 75 { 76 struct LNode *p; 77 if(!(s.top->next))exit(UNDERFLOW); 78 p=s.top; 79 s.top=p->next; 80 e=s.top->data; 81 free(p); 82 return OK; 83 } 84 85 Status GetTop(LStack s,ElemType &e) 86 //初始条件：栈s已存在且非空 87 //操作结果：用e返回s的栈顶元素 88 { 89 if(!(s.top->next))exit(ERROR); 90 s.top=s.top->next; 91 e=s.top->data; 92 return OK; 93 } 94 95 Status StackTraverse(LStack s) 96 //从栈顶开始依次输出 97 { 98 struct LNode *p; 99 if(!(s.top->next))exit(ERROR); 100 p=s.top; 101 while(p->next){ 102 p=p->next; 103 cout<<p->data<<endl; 104 } 105 return OK; 106 107 }
测试函数：test.cpp
1 //test.cpp 2 3 #include"stack.h" 4 #include<iostream> 5 using namespace std; 6 7 int main() 8 { 9 int e; 10 struct LStack s; 11 InitStack(s); 12 Push(s,4); 13 GetTop(s,e); 14 cout<<e<<endl; 15 Push(s,5); 16 Push(s,6); 17 Push(s,7); 18 Push(s,8); 19 Push(s,9); 20 GetTop(s,e); 21 cout<<e<<endl; 22 cout<<StackLength(s)<<endl; 23 Pop(s,e); 24 Pop(s,e); 25 Pop(s,e); 26 Pop(s,e); 27 28 cout<<StackEmpty(s)<<endl; 29 30 StackTraverse(s); 31 32 return 0; 33 }
方法二：
1 /******************************************************************************* 2 /* <PRE> 3 /* 版权所有 : - 4 /* 模块名 : 栈和队列 5 /* 文件名 : lstack.cpp 6 /* 功能描述 : 链栈的表示与实现 7 /* 作者 : <xxx> 8 /* 版本 : 1.0 9 /* ----------------------------------------------------------------------------- 10 /* 备注 : - 11 /* ----------------------------------------------------------------------------- 12 /* 修改记录 : 13 /* 日 期 版本 修改人 修改内容 14 /* 2011/01/01 1.0 <xxx> 创建 15 /* </PRE> 16 *******************************************************************************/ 17 #include "stdio.h" 18 #include "stdlib.h" 19 20 /****************************************************************************** 21 /* 数据类型和常量定义 22 /******************************************************************************/ 23 typedef int Status; 24 typedef int SElemType; 25 26 #define TRUE 1 27 #define FALSE 0 28 #define OK 1 29 #define ERROR 0 30 #define OVERFLOW -2 31 32 /****************************************************************************** 33 /* 数据结构声明 34 /******************************************************************************/ 35 typedef struct SNode { 36 SElemType data; 37 struct SNode *next; 38 }SNode; 39 40 typedef struct LinkStack { 41 SNode *base; 42 SNode *top; 43 }LinkStack; 44 45 46 /******************************************************************************* 47 /* <FUNC> 48 /* 函数名 : InitStack 49 /* 功能 : 构造空栈 50 /* 参数 : - 51 /* 返回值 : - 52 /* 备注 : - 53 /* 作者 : <xxx> 54 /* </FUNC> 55 *******************************************************************************/ 56 Status InitStack(LinkStack &S) { 57 S.top = S.base = NULL; 58 return OK; 59 } 60 61 /******************************************************************************* 62 /* <FUNC> 63 /* 函数名 : Push 64 /* 功能 : 入栈 65 /* 参数 : - 66 /* 返回值 : - 67 /* 备注 : 插入元素e为新的栈顶元素 68 /* 作者 : <xxx> 69 /* </FUNC> 70 *******************************************************************************/ 71 Status Push(LinkStack &S, SElemType e) { 72 SNode *p = (SNode *)malloc(sizeof(SNode)); 73 if (!p) exit(OVERFLOW); 74 p->data = e; 75 p->next = S.top; 76 S.top = p; 77 return OK; 78 } 79 80 /******************************************************************************* 81 /* <FUNC> 82 /* 函数名 : Push 83 /* 功能 : 出栈 84 /* 参数 : - 85 /* 返回值 : - 86 /* 备注 : 若栈不空, 则删除S的栈顶元素, 用e返回其值, 并返回OK; 否则返回ERROR 87 /* 作者 : <xxx> 88 /* </FUNC> 89 *******************************************************************************/ 90 Status Pop(LinkStack &S, SElemType &e) { 91 if (S.top == S.base) 92 return ERROR; 93 SNode *p = S.top; 94 S.top = S.top->next; 95 e = p->data; 96 free(p); 97 return OK; 98 } 99 100 /******************************************************************************* 101 /* <FUNC> 102 /* 函数名 : StackEmpty 103 /* 功能 : 判断栈是否为空 104 /* 参数 : - 105 /* 返回值 : - 106 /* 备注 : 若栈空则返回TRUE; 否则返回FALSE 107 /* 作者 : <xxx> 108 /* </FUNC> 109 *******************************************************************************/ 110 Status StackEmpty(LinkStack S) 111 { 112 if (S.base == S.top) return TRUE; 113 else return FALSE; 114 } 115 116 117 /******************************************************************************* 118 /* <FUNC> 119 /* 函数名 : main 120 /* 功能 : 测试函数 121 /* 参数 : - 122 /* 返回值 : - 123 /* 备注 : - 124 /* 作者 : <xxx> 125 /* </FUNC> 126 *******************************************************************************/ 127 void main() 128 { 129 LinkStack S; SElemType e; 130 InitStack(S); 131 Push(S, 10); 132 Push(S, 20); 133 if(OK == Pop(S, e)) printf("%d\n", e); 134 if(OK == Pop(S, e)) printf("%d\n", e); 135 if(OK == Pop(S, e)) printf("%d\n", e); 136 }
