数据结构——栈的详解[通俗易懂]

栈和队列是两种重要的线性结构,从数据结构的角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表的子集。他们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,他们是和线性表大不相同的两类重要的的抽象数据类型。C语言和C++中的栈C语言中的栈栈的定义C语言中栈的基本操作栈的初始化判断是否为空栈判断是否为满栈入栈出栈C语言实现栈的具体代码C++中的栈C++中栈的基…

大家好,又见面了,我是你们的朋友全栈君。

栈和队列是两种重要的线性结构,从数据结构的角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表的子集。他们是操作受限的线性表,因此,可称为限定性的数据结构。但从数据类型角度看,他们是和线性表大不相同的两类重要的的抽象数据类型。

C语言中的栈

栈的定义

栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说,表尾端称为栈顶(top),表头端称为栈低(bottom)。不含元素的空表称为空栈。因为栈限定在表尾进行插入或者删除,所以栈又被称为后进先出的线性表(简称LIFO:Last in, First out.结构)。
栈的示意图

C语言中栈的基本操作

栈的基本操作主要有:栈的初始化、判空、判满、取栈顶元素、在栈顶进行插入和删除。在栈顶插入元素称为入栈,在栈顶删除元素称为出栈

栈的初始化

栈和线性表类似,也有两种存储表示方法顺序栈链栈,链栈的操作是线性表操作的特例,操作比较容易实现。顺序栈即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置,top = 0表示空栈。由于栈在使用的过程中所需要的大小难以估计,所以通常是先为栈分配一个基本容量,然后再使用的过程中,当栈的空间不够使用的时候再继续追加存储空间。我们以下述类型说明作为顺序栈的定义:

typedef struct{ 
   
	SDataType *base; //栈底指针
	SDataType *top;  //栈顶指针
	int StackSize;   //当前已经分配的存储空间,以元素为单位 
}SqStack;

栈的初始化操作为:按照设定的初始分配量进行第一次存储分配,这里使用==malloc()==函数来分配存储空间。malloc()函数的详细说明请看:malloc详细说明。base作为栈底指针,它始终指向栈底,所以s.top = s.base可以作为栈空的标记。top为栈顶指针,top的初值指向栈底。每当插入一个元素时top加1,弹出一个元素时top减1,因此,非空栈中的栈顶指针始终在栈顶元素的下一个位置上
栈顶指针和栈中元素的关系图

//初始化顺序栈,构造一个空栈
Status InitStack(SqStack &S){ 
   
	//分配存储空间 
	S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));
	if(!S.base){ 
   
		//如果分配失败,则返回error 
		return OVERFLOW;
	}
	//S.top 始终指向栈顶元素的下一个位置 
	S.top = S.base;    //初始状态下为空栈 
	S.StackSize = STACK_INIT_SIZE;   //当前已经分配的存储容量为100个 
	return OK;	
}

判断是否为空栈

当我们弹出栈顶元素时,往往需要判断一下栈是否为空来防止发生下溢。上面我们说到==base作为栈底指针,它始终指向栈底,所以s.top = s.base可以作为栈空的标记。==所以我们可以这样判断栈是否为空:

//判断是否为空栈
void judgeNull(SqStack &s){ 
   
	if(s.top == s.base){ 
   
		printf("此栈为空栈!\n");
	}else{ 
   
		printf("此栈不为空栈!\n");
	}
}

判断是否为满栈

当我们使一个元素入栈的之前,我们往往需要判断一下栈是否为满栈,防止发生上溢的情况。因为我们定义了一个StackSize来表示当前已经分配的存储空间,所以我们可以用s.top – s.base 来算出当前已经使用的栈空间。所以当s.top - s.base == s.StackSize时表示已经满栈:

//判断是否为满栈
void judgeFull(SqStack &s){ 
   
	if(s.top-s.base == s.StackSize){ 
   
		printf("栈满!\n");
	}else{ 
   
		printf("栈未满!\n");
	} 
}

入栈

入栈时我们首先要判断栈是否为满栈,如果为满栈我们要首先追加存储空间,然后才能将元素入栈。realloc()函数详解请看realloc详解

//入栈
Status Push(SqStack &s,SDataType e){ 
   
	SDataType *p;
	//首先判断栈是不是满的(上溢) 
	if(s.top-s.base == s.StackSize){ 
   
		//追加空间 
		p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));
		if(!p){ 
   
			//如果没有找到符合条件的存储空间,则返回error 
			return OVERFLOW;
		}
		//成功找到则使s.base指向p 
		s.base = p;
		s.top = s.base + s.StackSize;
		s.StackSize +=  STACKINCREMENT;
	}
	//先插入元素,然后将栈顶指针加 1 
	*(s.top) = e;
	s.top++;
	return OK;
}

出栈

出栈时我们首先要判断栈是否为空栈。如果栈已经空了,则返回error。

//出栈
Status Pop(SqStack &s,SDataType &e){ 
   
	//判断是否会发生下溢 
	if(s.top != s.base){ 
   
		s.top--;    //先将栈顶指针减 1 
		e = *(s.top);
	}else{ 
   
		return 0;
	}
	return e;
}

C语言实现栈的具体代码

#include<stdio.h>
#include<malloc.h>

#define STACK_INIT_SIZE 100 //栈的初始容量 
#define STACKINCREMENT 10 //容量增量
#define OK 1 
#define OVERFLOW -2
typedef int SDataType;
typedef int Status;

typedef struct{ 
   
	SDataType *base; //栈底指针
	SDataType *top;  //栈顶指针
	int StackSize;   //当前已经分配的存储空间,以元素为单位 
}SqStack;

//初始化顺序栈,构造一个空栈
Status InitStack(SqStack &S){ 
   
	//分配存储空间 
	S.base = (SDataType *)malloc(STACK_INIT_SIZE*sizeof(SDataType));
	if(!S.base){ 
   
		//如果分配失败,则返回error 
		return OVERFLOW;
	}
	//S.top 始终指向栈顶元素的下一个位置 
	S.top = S.base;    //初始状态下为空栈 
	S.StackSize = STACK_INIT_SIZE;   //当前已经分配的存储容量为100个 
	return OK;	
} 

//入栈
Status Push(SqStack &s,SDataType e){ 
   
	SDataType *p;
	//首先判断栈是不是满的(上溢) 
	if(s.top-s.base == s.StackSize){ 
   
		//追加空间 
		p = (SDataType *)realloc(s.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SDataType));
		if(!p){ 
   
			//如果没有找到符合条件的存储空间,则返回error 
			return OVERFLOW;
		}
		//成功找到则使s.base指向p 
		s.base = p;  //系统会将原来的内容复制过来
		s.top = s.base + s.StackSize;
		s.StackSize +=  STACKINCREMENT;
	}
	//先插入元素,然后使栈顶指针加 1 
	*(s.top) = e;
	s.top++;
	return OK;
} 

//出栈
Status Pop(SqStack &s,SDataType &e){ 
   
	//判断是否会发生下溢 
	if(s.top != s.base){ 
   
		s.top--;    //先将栈顶指针减 1 
		e = *(s.top);
	}else{ 
   
		return 0;
	}
	return e;
}

//判断是否为空栈 
void judgeNull(SqStack &s){ 
   
	if(s.top == s.base){ 
   
		printf("此栈为空栈!\n");
	}else{ 
   
		printf("此栈不为空栈!\n");
	}
}

//判断是否为满栈
void judgeFull(SqStack &s){ 
   
	if(s.top-s.base == s.StackSize){ 
   
		printf("栈满!\n");
	}else{ 
   
		printf("栈未满!\n");
	} 
} 

int main(){ 
   
	SqStack s;
	SDataType element;
	
	InitStack(s);  //初始化栈
	//将1-5入栈
	for(int i=1;i<=10;i++){ 
   
		Push(s,i);
	}
	
	judgeNull(s);
	judgeFull(s);
	
	printf("出栈:\n");
	//只要栈不为空 
	while(s.top != s.base){ 
   
		Pop(s,element);    //出栈的元素用e接收 
		printf("%d ",element);
	}
	
	printf("\n"); 
	judgeNull(s);
	
	return 0;
	 
} 

C++中的栈

C++ 对模板(Template)支持得很好,STL 就是借助模板把常用的数据结构及其算法都实现了一遍,并且做到了数据结构和算法的分离。STL的代码从广义上讲分为三类:algorithm(算法)、container(容器)和iterator(迭代器),几乎所有的代码都采用了模板类和模版函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中,STL被组织为下面的13个头文件:<algorithm >、<deque >、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。其中的<stack>就是栈。

C++的STL已经将栈的操作都封装成了函数,我们只需要引进#include<stack>头文件即可使用。

C++中栈的基本操作

初始化

我们可以直接使用stack<int> s;来创建一个空的 stack 对象。

判断是否为空栈

使用empty()函数来判断栈是否为空。
empty()函数详解

入栈

使用push()函数来完成入栈操作。
push()函数详解

出栈

使用pop()函数实现出栈
pop()函数详解

返回栈顶元素

使用top()函数返回栈顶元素
top()函数详解

返回栈中元素数目

使用size()函数返回栈中元素的数目。
size()函数详解


以上就是C语言和C++中栈的基本用法了,如果你觉得我的文章对你有用请点个赞支持一下吧,如果喜欢我写的文章那么请点个关注再走。
嘿嘿
下一篇将继续写数据结构的队列,后续将会再写一些有关栈和队列的具体应用。我是ACfun:一个成长中的程序猿,感谢大家的支持。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126019.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • linux sigpipe信号,Linux下SIGPIPE信号及其处理「建议收藏」

    linux sigpipe信号,Linux下SIGPIPE信号及其处理「建议收藏」在Linux下写socket的程序的时候,如果尝试send到一个disconnectedsocket上,就会让底层抛出一个SIGPIPE信号。这个信号的缺省处理方法是退出进程,大多数时候这都不是我们期望的。因此我们需要重载这个信号的处理方法。调用以下代码,即可安全的屏蔽SIGPIPE:structsigactionsa;sa.sa_handler=SIG_IGN;sigaction(S…

  • c语言函数回调详解_c语言回调函数例子

    c语言函数回调详解_c语言回调函数例子关于静态库和动态库的使用和制作方法。http://blog.csdn.net/morixinguan/article/details/52451612今天我们要搞明白的一个概念叫回调函数。什么是回调函数?百度的权威解释如下:回调函数就是一个通过函数指针调用的函数。如果你把函数的指针(地址)作为参数传递给另一个函数,当这个指针被用来调用其所指向的函数时,我们就说这是回调函数。回调函数不是由该函数的实…

    2022年10月30日
  • springboot的单元测试(junit单元测试实例)

    转载 原文:https://www.codenong.com/cs106212170/文章目录一.Junit测试二.集成测试1.SpringBoot测试-测试其中的Bean2.SpringBootWeb测试-启动tomcat3.SpringBootWeb测试-不启动tomcat(模拟环境)三.单元测试1.web层测试2.mybtismapper测试3.测试任意的bean4.Mock操作四.相关注解的汇总五.参考网站一.Junit测试当你的单元测试代码不需要用到..

  • 十四、迭代器模式—— 一个一个的遍历 #和设计模式一起旅行#「建议收藏」

    套路要深…故事背景今天要介绍一下迭代器,首先简单说明一下,什么是迭代器,为什么要使用迭代器。 迭代器(Iterate) 的意思就是反复做某件事情。那为什么要反复做某件事情呢,比如我们有个容器里面装了很好东西(这些东西都是同一类型的),要从容器中取每一个东西出来,就要反复去做一个取出的事情。故事主角迭代器模式 : 提供一种方法顺序访问一个聚合对象中的各个元素,而…

  • android 6.0锁屏界面时间位置修改[通俗易懂]

    android 6.0锁屏界面时间位置修改[通俗易懂]在SystemUI里的Android.mk中LOCAL_STATIC_JAVA_LIBRARIES:=KeyguardLOCAL_STATIC_JAVA_LIBRARIES+=com.mediatek.systemui.extLOCAL_JAVA_LIBRARIES:=telephony-commonLOCAL_JAVA_LIBRARIES+=mediatek-

  • JAVA中使用alibaba fastjson实现JSONObject、Object、Json字符串的转换

    JAVA中使用alibaba fastjson实现JSONObject、Object、Json字符串的转换Object转JSON字符串:StringjsonStr=JSONObject.toJSONString(object);JSON字符串转JSONObject:JSONObjectjsonObject=JSONObjcet.parseObject(jsonStr);JSON字符串转Object对象Tt=JSON.parseObject(jsonStr,…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号