数据结构
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或者多种特定关系的数据元素集合。通常情况下，精心选择的数据结构可以带来更高效的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
    数据结构是ADT（抽象数据类型）的物理实现。
    程序 = 数据结构 + 算法
    算法是为了解决问题而设计的，数据结构是算法需要处理问题的载体。
    1.顺序表：顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
    将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
    2.链表：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
    使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。
    3.栈：栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。 
    首先系统或者数据结构栈中数据内容的读取与插入（压入push和 弹出pop）是两回事！插入是增加数据，弹出是删除数据 ，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作 ，但读取栈中的数据是随便的没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。 [1] 而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用 即 cpu 与内存的交流通道 ，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令， 用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见 EU与BIU的概念介绍。  
    栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
    栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。栈可以用来在函数调用的时候存储断点，做递归时要用到栈！

本文目录：
 

 
 
数据结构分类
1、数组
2、栈
3、队列
4、链表
5、树
6、散列表
7、堆
8、图
 
 
 
数据结构分类
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 
 常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示： 
  
 每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。
 
1、数组
 
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。
 
int[] data = new int[100]；data[0]  = 1;
 
优点： 
 1、按照索引查询元素速度快 
 2、按照索引遍历数组方便
 
缺点： 
 1、数组的大小固定后就无法扩容了 
 2、数组只能存储一种类型的数据 
 3、添加，删除的操作慢，因为要移动其他的元素。
 
适用场景： 
 频繁查询，对存储空间要求不大，很少增加和删除的情况。
 
2、栈
 
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。 
  
 栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
 
3、队列
 
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下： 
  
 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
 
4、链表
 
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 
  
 链表的优点： 
 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 
 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
 
缺点： 
 因为含有大量的指针域，占用空间较大； 
 查找元素需要遍历链表来查找，非常耗时。
 
适用场景： 
 数据量较小，需要频繁增加，删除操作的场景
 
5、树
 
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
 
每个节点有零个或多个子节点； 
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
 
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。 
  
 二叉树是树的特殊一种，具有如下特点：
 
1、每个结点最多有两颗子树，结点的度最大为2。 
 2、左子树和右子树是有顺序的，次序不能颠倒。 
 3、即使某结点只有一个子树，也要区分左右子树。 
 
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
 
扩展： 
 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。
 
6、散列表
 
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
 
记录的存储位置=f(key) 
 
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
 
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下： 
  
 从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。 
 
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
 
7、堆
 
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
 
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
 
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
 
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 
 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下： 
  
 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
 
8、图
 
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 
 
按照顶点指向的方向可分为无向图和有向图： 
  
  
 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

学习数据结构与算法，还是很有必要看几本相关的书籍，但根据不同基础的人，合适看的书也不一样，因此，针对不同层次、不同语言的人，推荐几本市面上口碑不错的书。
 
1. 入门级
 
针对刚入门的同学，建议不要急着去看那些经典书，像《算法导论》、《算法》这些比较经典、权威的书。虽然书很好，但看起来很费劲，如果看不完，效果会很不好。所以建议先看两本入门级的趣味书：
 
《大话数据结构》
《算法图解》
 
大话数据结构
 
将理论讲的很有趣，不枯燥。作者结合生活中的例子去对每个数据结构和算法进行讲解，让人通俗易懂。
 
算法图解
 
这是一本像小说一样有趣的算法入门书，书中有大量的图解，通俗易懂。
 
看完上面一本或两本入门级的书，你就会对数据结构和算法有个大概认识和学习。但这些入门级的书缺少细节、不够系统。所以想要深入的学习数据结构和算法，光看这两本书肯定是不够的。
 
2. 不同语言的教科书
 
国内外很多大学都是将《数据结构和算法分析》作为教科书。这本书非常系统、严谨、全面，难度适中，很适合对数据结构和算法有些了解，并且已经掌握了至少一门语言的同学学习。针对不同的语言，分别有：
 
 
《数据结构与算法分析:C语言描述》
 
 
《数据结构与算法分析:C++描述》
 
 
《数据结构与算法分析:java语言描述》
 
 
如果你不会C、C++、java，会Python或者JavaScript，可以看：
 
 
《数据结构与算法JavaScript描述》
 
 
《数据结构与算法:Python语言描述》
 
 
3. 面试书籍
 
现在很多大厂的面试都会考算法题，这里推荐几本面试算法书籍：
 
 
《剑指offer》
 
 
《编程珠玑》
 
 
《编程之美》
 
 
剑指offer
 
为面试算法量身定做的一本书。几乎包含了所有常见的、经典的面试题，如果能搞懂书里面的内容，一般公司的算法面试都应该没问题。
 
编程珠玑
 
这本书豆瓣评分有9分，评分很高。这本书最大的特色是讲了很多海量数据的处理技巧。其他算法书籍很少涉及海量数据。
 
编程之美
 
有些作者是微软工程师，算法题目较难，比较适合要面试Google、Facebook这样的公司的人去看。
 
4. 经典书籍
 
现在数据结构与算法最经典的书籍就是：
 
 
《算法导论》
 
 
《算法》
 
 
《计算机程序设计艺术》
 
 
这三本书非常经典，但都很厚，看起来比较费劲，估计很少有人能全部看完。但如果想更深入地学一遍数据结构和算法，还是建议去看看。
 
算法导论
 
章节安排不是循序渐进，里面有各种算法正确性、复杂度的证明、推导，对数学功底有一定要求，看起来有些费劲。
 
算法
 
偏重讲算法。内容不够全面，对数据结构方面的知识讲的不多，动态规划这么重要的知识点却没有讲。
 
计算机程序设计艺术
 
这本书包括很多卷，相比于其他书籍有更好的深度、广度、系统性和全面性。但如果你对数据结构和算法不是特别感兴趣，没有很好的数学、算法、计算机基础，很难把这本书读完、读懂。
 
5. 课外阅读
 
有些算法书籍也比较适合在平时悠闲的时候翻翻看看：
 
 
《算法帝国》
 
 
《数学之美》
 
 
《算法之美》
 
 
这些书都列举了大量的列子来解释说明，非常通俗易懂。
 
下面给出一张上面推荐的数据结构与算法书籍的思维导图：
 

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


 
文章目录
 
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()函数来判断栈是否为空。
 
 
入栈
 
使用push()函数来完成入栈操作。
 
 
出栈
 
使用pop()函数实现出栈
 
 
返回栈顶元素
 
使用top()函数返回栈顶元素
 
 
返回栈中元素数目
 
使用size()函数返回栈中元素的数目。
 
 
 
以上就是C语言和C++中栈的基本用法了，如果你觉得我的文章对你有用请点个赞支持一下吧，如果喜欢我写的文章那么请点个关注再走。
 
 下一篇将继续写数据结构的队列，后续将会再写一些有关栈和队列的具体应用。我是ACfun：一个成长中的程序猿，感谢大家的支持。