（重点）链式栈-白红宇

顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用完而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用。 而对于链式栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间，另外当某个项目不使用时也可将内存返还给系统。 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针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
     
        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<
      
       data<

测试函数：test.cpp

1 //test.cpp 2  3 #include"stack.h" 4 #include
     
       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<
      
       <

方法二：

1 /*******************************************************************************  2 /*   3 /* 版权所有    : -  4 /* 模块名      : 栈和队列  5 /* 文件名      : lstack.cpp  6 /* 功能描述    : 链栈的表示与实现   7 /* 作者        : 
      
         8 /* 版本        : 1.0  9 /* ----------------------------------------------------------------------------- 10 /* 备注        : - 11 /* ----------------------------------------------------------------------------- 12 /* 修改记录    : 13 /* 日 期        版本     修改人        修改内容 14 /* 2011/01/01   1.0      
       
                 创建 15 /* 
       
      
 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 /* 
     
       48 /* 函数名   : InitStack 49 /* 功能     : 构造空栈 50 /* 参数     : - 51 /* 返回值   : - 52 /* 备注     : - 53 /* 作者     : 
      
        54 /* 
      
      55 *******************************************************************************/ 56 Status InitStack(LinkStack &S) { 57     S.top = S.base = NULL; 58     return OK; 59 } 60  61 /******************************************************************************* 62 /* 
     
       63 /* 函数名   : Push 64 /* 功能     : 入栈 65 /* 参数     : - 66 /* 返回值   : - 67 /* 备注     : 插入元素e为新的栈顶元素 68 /* 作者     : 
      
        69 /* 
      
      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 /* 
     
       82 /* 函数名   : Push 83 /* 功能     : 出栈 84 /* 参数     : - 85 /* 返回值   : - 86 /* 备注     : 若栈不空, 则删除S的栈顶元素, 用e返回其值, 并返回OK; 否则返回ERROR 87 /* 作者     : 
      
        88 /* 
      
      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 /* 
     
      102 /* 函数名   : StackEmpty103 /* 功能     : 判断栈是否为空104 /* 参数     : -105 /* 返回值   : -106 /* 备注     : 若栈空则返回TRUE; 否则返回FALSE107 /* 作者     : 
      
       108 /* 
      
     109 *******************************************************************************/110 Status StackEmpty(LinkStack S)111 {112     if (S.base == S.top) return TRUE;113     else return FALSE;114 }115 116 117 /*******************************************************************************118 /* 
     
      119 /* 函数名   : main120 /* 功能     : 测试函数121 /* 参数     : -122 /* 返回值   : -123 /* 备注     : -124 /* 作者     : 
      
       125 /* 
      
     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 }