(重点)链式栈

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏BY的专栏

Objective-C Runtime详解

40160
来自专栏ACM算法日常

POJ-3641:Pseudoprime numbers(快速幂)

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

11710
来自专栏desperate633

LintCode 简化路径题目分析代码

思路比较简单,遇到..就回到上一级,遇到.或者空就不处理。 我们使用一个队列来处理,同时将三个需要特殊处理的字符存到一个set里面

7010
来自专栏Ryan Miao

app令牌的一个token实现

app登陆验证不能使用session来判断了。然后查资料都说用令牌,没找到合适的方法,我的眼界太小。另外,越来越感觉基础的重要,比如,session是什么,我竟...

349120
来自专栏大内老A

.NET Core采用的全新配置系统[4]: “Options模式”下各种类型的Options对象是如何绑定的?

旨在生成Options对象的配置绑定实现在IConfiguration接口的扩展方法Bind上。配置绑定的目标类型可以是一个简单的基元类型,也可以是一个自定义数...

21270
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

47870
来自专栏尾尾部落

[剑指offer] 链表中环的入口结点

假设环长度为n,进入环之前结点个数为x,slow在环内走了k个结点,fast绕环走了m圈,则有2(x+k)=x+mn+k 可以得出x = mn - k。此时sl...

10330
来自专栏Code_iOS

Objective-C 内存管理(上)学习笔记

这里的“计数”表明必然会有一个东西(变量)来记录引用的变化,而在OC里这个变量就是retainCount;那么还有一个问题就是通过什么方式来操作这个变量,OC里...

7020
来自专栏开发与安全

数据结构:队列的顺序存储结构(循环队列)

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头...

24970
来自专栏技术博文

Base64 的 JavaScript 实现 js-base64

base64.js 是 Base64 的 JavaScript 实现。 wiki上给的解释: https://en.wikipedia.org/wiki/Bas...

42040

扫码关注云+社区

领取腾讯云代金券