（重点）链式栈
顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用完而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用。而对于链式栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间，另外当某个项目不使用时也可将内存返还给系统。顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013-08-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读