栈是什么？如果用生活中最常见的例子，我想到是书本的放置（当然这是部分人喜欢的做法）。但是给人的感觉是非常直接的，书本整齐跨一叠在一起，放在最上面的那本最先拿走，放在最底下那本书就最后拿走，形象吧，生活中有很多后进先出的栗子，就不一一说明了，用图来说明应该很好理解。
 
 
放在最上面的那本书的位置叫栈顶，栈顶是可变的，比如说你拿走了西游记，那么栈顶就是红楼梦得位置。相对应的栈底是不可操作的一端。
 栈是一种特殊的线性表，特殊之处在于只能在一端对其进行操作，把元素放到栈中，这操作叫压栈(push)，压栈之后，栈顶指针就向上移动。把元素从栈顶弹出，这叫出栈(pop)，出栈后栈顶指针向下移动。访问栈只能从栈顶元素进行。栈是很重要的数据结构，在很多算法都有应用，比如图的深度优先遍历算法(DFS)，Dijkstra算法的中转站。
 
栈的实现分为两种，一是顺序栈，用数组来实现，二是链式栈，用指针将结点串联起来，与链表相似，但仅能在栈顶进行操作。
 
先实现简单的顺序栈，顺序栈简直不要太简单，上代码：
 
#ifndef STATICSTACK_H
#define STATICSTACK_H

template <typename T, int N>
class StaticStack
{
protected:
	T array[N];	// 使用模板参数决定栈的大小
	int m_top;	// 使用整型作为标记，相当于栈顶指针
	int m_size;	// 栈中数据元素的个数
public:
	StaticStack()	// 初始化操作得做一下
	{
		m_top = -1;
		m_size = 0;
	}
	
	bool push(const T& obj)	// 压栈操作，就是往数组增加一个元素
	{
		bool ret = m_size < N;	// 满了就没办法了
		
		if( ret )
		{
			array[++m_top] = obj;
			++m_size;
		}
		
		return ret;
	}
	
	bool pop()	// 出栈操作
	{
		bool ret = m_size > 0;
		
		if( ret )
		{
			--m_top;
			--m_size;
		}
		
		return ret;
	}
	
	T top()	// 获取栈顶元素
	{
		return array[m_top];
	}
	
	void clear()	// 把栈清空
	{
		m_top = -1;
		m_size = 0;
	}
	
	int size()	// 获取栈的大小
	{
		return m_size;
	}
	
	~StaticStack()
	{
		clear();
	}
};

#endif
 
来用一下这个简单顺序栈。记住，后进先出！
 
#include <iostream>
#include "StaticStack.h"

using namespace std;

int main(int argc, const char* argv[])
{
	StaticStack<int, 10> stack;

	for(int i = 0; i < 10; ++ i)
	{
		stack.push(i);
	}
	// 入栈的时候是 0123456789 的顺序
	
	for(int i = 0; i < 10; ++ i)
	{
		cout << stack.top() << endl;
		stack.pop();
	}
	
	return 0;
}
 
 
输出正确。OK,顺序栈就可以跳过了，因为顺序栈的实现依赖于原生数组，所以在定义的时候必须给定大小，并且在使用的过程中不能动态改变其大小，这是顺序栈的一个缺点，另外，当顺序栈存放的元素是类类型，那么在定义顺序栈时就会自动调用类的构造函数，有多少个元素就会调用多少次，这样做显然会降低效率，所以顺序栈的使用相对较少。
 
现在重点来实现链式栈吧，有了顺序栈的基础，实现链式栈也相当容易。
 直接上代码：
 
#ifndef LINKSTACK_H
#define LINKSTACK_H

template <typename T>
class LinkStack
{
protected:
	struct Node
	{
		T data;
		Node* next;
	};
	mutable Node header;	// 使用头节点会方便各种操作
	int m_size;
	
public:
	LinkStack()
	{
		header.next = NULL;
		m_size = 0;
	}
	
	bool push(const T& obj)	// 压栈操作
	{
		bool ret = true;	
		Node* n = new Node();
		
		if( n != NULL )
		{
			n->data = obj;
			Node* current = &header;	// 相当于链表的头插
			n->next = current->next;
			current->next = n;
			++m_size;
		}
		else
		{
			ret = false;
		}
		
		return ret;
	}
	
	bool pop()	// 出栈操作
	{
		bool ret = true;
		
		if( m_size > 0 )
		{
			Node* current = &header;	// 相当于链表的头删
			Node* todel = current->next;
			current->next = todel->next;
			--m_size;
			delete todel;
		}
		else
		{
			ret = false;
		}
		
		return ret;
	}
	
	T top() const	// 获取栈顶元素
	{
		Node* current = header->next;
		
		return current->data;
	}
	
	int size() const
	{
		return m_size;
	}
	
	void clear()	// 清空栈
	{
		while( m_size > 0 )
		{
			pop();
		}
	}
	
	~LinkStack()
	{
		clear();
	}
};

#endif
 
仅仅是实现一个栈好像没有什么好玩的，顺序栈操作一个数组，链式就几个指针操作。现在用栈来实现一个扫描函数，将字符串中的左右符号进行匹配。举个栗子，“（ a { b c [ d < e " f ’ g’ " h > i ] j } k）”,这样一个看起来复杂l凌乱的字符串，怎么知道它的左右符号匹不匹配呢？人工智能嘛，人工来数一下不就可以了吗？Good idea！简单的数几分钟就应该知道结果了，要是一本书那么多的字符串怎么来数？当然是把工作交给计算机！写个程序来检查左右符号是否匹配不就得了。主要注意的地方是左符号、右符号以及引号的处理，其他字符直接忽略。知道重点了，实现就容易了，说干就干，动手！
 
#include <iostream>
#include "LinkStack.h"

// 需要提前准备相应的辅助函数
bool is_Left(const char c)	// 判断是否为左符号
{
	return (c == '(') || (c == '{') || (c == '<') || (c == '[');
}

bool is_Right(const char c)	// 判断是否为右符号
{	
	return (c == ')') || (c == '}') || (c == '>') || (c == ']');
}
	
bool is_Quot(const char c)	// 判断是否为引号
{
	return (c == '\'') || (c == '\"');
}

bool is_Match(const char l,const char r)	// 进行匹配判断
{
	bool ret = ( (l == '(') && (r == ')') )   ||
		   ( (l == '{') && (r == '}') )   ||
		   ( (l == '[') && (r == ']') )   ||
		   ( (l == '<') && (r == '>') )   ||
		   ( (l == '\'') && (r == '\'') ) ||
		   ( (l == '\"') && (r == '\"') ) ;	
		   
	return ret;
}

bool scan_func(const char* str)	// 扫描字符串的函数
{
	bool ret = true;	
	int i = 0;
	str = str ? str : "";	// 参数合法性判断，如果参数为空，则用空字符串代替
	LinkStack<char> stack;	// 看着怎么使用栈吧

	while( ret && (str[i] != '\0') )	// 循环遍历字符串
	{					// 如果有不匹配的字符就立即结束循环
		if( is_Left(str[i]) )		// 左符号，直接入栈
		{
			stack.push(str[i]);
		}
		else if( is_Right(str[i]) )	// 右符号，判断栈是否为空
		{				// 如果栈为空，结束循环
			if( (stack.size() > 0) && (is_Match(stack.top(), str[i])) )		
			{
				stack.pop();	// 栈不为空，且与栈顶元素能匹配，那就把栈顶中的左符号出栈
			}
			else
			{
				ret = false;	
			}
		}
		else if( is_Quot(str[i]) )	// 引号判断
		{				// 如果栈为空或者与栈顶元素不匹配，入栈
			if( (stack.size() == 0) || (!is_Match(stack.top(), str[i])) )
			{
				stack.push(str[i]);
			}			// 与栈顶元素匹配，那就将栈顶的引号出栈
			else if( is_Match(stack.top(), str[i]) )
			{
				stack.pop();
			}
		}
	}
	
	return (ret && (stack.size() == 0) );
}

int main(int argc, const char* argv[])
{
	const char* str1 = " < ( [ { 123 } ] ) > ";
	const char* str2 = " \" \' 123 \' \" ";
	const char* str3 = "< 123 ";

	cout << endl;
	cout << str1 << " result of match : " << ( scan_func(str1) ? " true " : " false " ) << endl;
	
	cout << endl;
	cout << str2 << " result of match : " << ( scan_func(str2) ? " true " : " false " ) << endl;
	
	cout << endl;
	cout << str3 << " result of match : " << ( scan_func(str3) ? " true " : " false " ) << endl;
	
	
	return 0;
}
 
看看输出结果，多easy，要是用人工的智能来数，得花点点点时间。
 

 
文章目录
 
1.栈的简介
2. 栈的基本操作
（1）顺序栈
（2）链栈
   
3. push和pop的使用
4. 总结
 

 
1.栈的简介
 
简单来说，栈是一种特殊的线性表。
 
线性表对数据的顺序非常敏感，而且它对数据的增删操作非常灵活。在有序排列的数据中，可以灵活的执行增删操作，就好像是为排好队的数据增加了插队的入口。这既是灵活性也是缺陷，原因在于它的灵活性在某种程度上破坏了数据的原始顺序。在某些需要严格遵守数据处理顺序的场景下，我们就需要对线性表予以限制了。而栈就是一种被限制的线性表。
 
既然线性表那么灵活，那为啥还需要栈呢？
 
其实，单纯从功能上讲，线性表（数组或链表）可以替代栈。然而问题是，数组或者链表的操作过于灵活，这意味着，它们过多暴露了可操作的接口。这些没有意义的接口过多，当数据量很大的时候就会出现一些隐藏的风险。所以虽然栈限定降低了操作的灵活性，但也使得增删数据时，安全性和时效性更高。
 
那么具体是怎么限制的呢？
 
栈的数据结点被限制为后进先出，这意味着栈的数据新增操作只能在末端进行，不允许在栈的中间某个结点后新增数据。同时，栈的数据删除操作也只能在末端进行，不允许在栈的中间某个结点后删除数据。
 
因此，可以说栈是一种后进先出的线性表。
 
 
2. 栈的基本操作
 
栈有两种基本的操作：压栈与出栈。
 
如果需要给栈新增数据，就是压栈，也称作push。
 如果需要删除栈顶的数据，就是出栈，也称作pop。
 
前面我们学习了线性表，知道线性表有顺序存储结构的数组，也有采用链式存储结构的链表。同理，根据存储结构的不同，栈也被分为了顺序栈和链栈。
 
下面就来分别谈一下顺序栈和链栈的增删查操作。
 
（1）顺序栈
 
栈的顺序存储可以借助数组来实现。一般来说，会把数组的首元素存在栈底，最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。 假设栈中只有一个数据元素，则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。 当定义了栈的最大容量为 StackSize 时，则栈顶 top 必须小于 StackSize。
 
新增操作。就需要将新插入元素放在栈顶，并将栈顶指针增加 1。
删除操作。即出栈操作，只需要 top - 1 就可以了。
查找操作。栈没有额外的改变，跟线性表一样，它也需要遍历整个栈来完成基于某些条件的数值查找。
 
（2）链栈
 
关于链栈，就是用链表的方式对栈的表示。通常，可以把栈顶放在单链表的头部。由于链栈的后进先出，原来的头指针就显得毫无作用了。因此，对于链栈来说，是不需要头指针的。相反，它需要增加指向栈顶的 top 指针，这是压栈和出栈操作的重要支持。
 
新增操作。即压栈操作，与链表最后插入的新数据基本相同。需要额外处理的，就是栈的 top 指针。插入新的数据，则需要让新的结点指向原栈顶，即 top 指针指向的对象，再让 top 指针指向新的结点。
删除操作。只能在栈顶进行操作，因此，将栈顶的 top 指针指向栈顶元素的 next 指针即可完成删除。
查找操作。相对链表而言，链栈没有额外的改变，它也需要遍历整个栈来完成基于某些条件的数值查找。
 
对于链式栈来说，新增删除数据元素没有任何循环操作，其时间复杂度均为 O(1)。
 
通过分析你会发现，不管是顺序栈还是链栈，数据的新增、删除、查找与线性表的操作原理极为相似，时间复杂度完全一样，都依赖当前位置的指针来进行数据对象的操作。区别仅仅在于新增和删除的对象，只能是栈顶的数据结点。
 
3. push和pop的使用
 
如下图所示，使用push和pop分别在栈顶位置增加和删除元素。
 
 如下所示，先向栈中存入三个元素，再从栈中取出一个元素。
 
#include<iostream>
#include<stack>

using namespace std;

int main()
{
	stack<int> s;
	s.push(1);
	s.push(2);
	s.push(3);
	cout<<"栈顶的数是："<<s.top()<<endl;
	s.pop();
	cout<<"执行一次pop操作后，栈顶的数是："<<s.top()<<endl;
	return 0;
}
 
运行结果：
 
栈顶的数是：3
执行一次pop操作后，栈顶的数是：2
 
4. 总结
 
栈具有后进先出的特性，只允许数据从栈顶进出。
栈对于数据的新增操作和删除操作的时间复杂度都是 O(1）。而在查找操作中，栈和线性表一样只能通过全局遍历的方式进行，也就是需要 O(n) 的时间复杂度。
当你面对的问题需要高频使用新增、删除操作，且新增和删除操作的数据执行顺序具备后来居上的相反关系时，栈就是个不错的选择。

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
 
------------摘自百度百科。
 

 
 
顾名思义，栈也就是一个后进先出的一种数据结构。生活中就有很多后进先出的现象，如：一摞盒子，放在最下面的肯定死最先放进去的，但如果要去出来的话却是最后取出来的。
 

 
 
归纳先进后出的现象，可获得栈的非正式定义如下。
 
栈是一个满足如下条件的数据结构。
 
（1）数据项一个叠一个呈线性排列；
 
（2）所有的插入与删除操作在一段进行；
 
（3）最后插入的记录是第一个被删除的记录；
 
（4）栈的基本操作有三个：
 
①入栈，压入一个元素或记录到栈顶；
 
②出栈，将栈顶元素或记录移除；
 
③读栈，取出栈顶元素或记录。
 

 
 
下面给出栈的类定义：
 

//Stack in C++
#include<iostream>
using namespace std;
typedef int stackEntry;
const int maxstack = 100;						//栈的最大尺寸
class stack 
{
public:

	void stack::push(const stackEntry &item)			//如果栈未满，将元素item压入栈顶，否则报错（入栈操作）
	{
		if (count >= maxstack)
			cout << "栈上溢，无法压入元素";
		else
			data[count++] = item;
	}

	void stack::pop()						//如果栈未空，将栈顶元素删除，否则报错（出栈操作）
	{
		if (count == 0)
			cout << "栈下溢，无法弹出元素";
		else
			--count;
	}

	void stack::top(stackEntry &item) const				//如果栈未空，将栈顶元素取出放在item里，否则报错（取出栈顶元素）
	{
		if (count == 0)
			cout << "栈下溢，无法读取元素";
		else
			item = data[count - 1];
	}

	bool stack::empty() const					//判断栈是否为空
	{
		if (count > 0)
			return false;
		return true;
	}

	stack::stack()							//构建函数，初始化一个空栈
	{
		count = 0;
	}
private:
	int count;							//栈中元素个数的记录
	stackEntry data[maxstack];					//以连续分配的数组来存放栈元素
};



 

 

本文目录：
 

 
 
数据结构分类
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组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 
 
按照顶点指向的方向可分为无向图和有向图： 
  
  
 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。