栈是什么？如果用生活中最常见的例子，我想到是书本的放置（当然这是部分人喜欢的做法）。但是给人的感觉是非常直接的，书本整齐跨一叠在一起，放在最上面的那本最先拿走，放在最底下那本书就最后拿走，形象吧，生活中有很多后进先出的栗子，就不一一说明了，用图来说明应该很好理解。


放在最上面的那本书的位置叫栈顶，栈顶是可变的，比如说你拿走了西游记，那么栈顶就是红楼梦得位置。相对应的栈底是不可操作的一端。

栈是一种特殊的线性表，特殊之处在于只能在一端对其进行操作，把元素放到栈中，这操作叫压栈(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，要是用人工的智能来数，得花点点点时间。

 首先，栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

压栈：指数据的插入操作（入数据在栈顶）。

出栈：指数据的删除操作（出数据也在栈顶）。


 栈的实现：一般可以用数组或者链表，但是用数组实现更优一点，因为数组在尾插尾删上的代价较小。


 下面，我们来实现支持动态增长的栈：


typedef int STDataType;
/top永远指向栈顶元素，top可以反映出栈的元素的个数
typedef struct Stack{
	STDataType* _a;
	int _top;
	int _capacity;
}Stack;

/初始化时，可以不给数组开空间，可以直接在插入数据的时候进行数组空间的开辟和增容的考虑
void StackInit(Stack* ps){
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}

void StackDestory(Stack* ps){
	assert(ps);
	free(ps->_a);
	ps->_capacity = 0;
	ps->_top = 0;
}

/增容时要考虑到capacity为0的情况
/一般以2倍速增容
void StackPush(Stack* ps, STDataType x){
	assert(ps);
	if (ps->_top == ps->_capacity){
		if (ps->_capacity == 0){
			ps->_capacity = 10;
		}
		else{
			int newcapacity = 2 * ps->_capacity;
			ps->_capacity = newcapacity;
		}
		/realloc:用来追加数组空间！！！！
		ps->_a = (STDataType*)realloc(ps->_a,sizeof(STDataType)*ps->_capacity);
	}
	ps->_a[ps->_top++] = x;
}

void StackPop(Stack* ps){
	assert(ps);
	/要保证栈里有元素
	if (ps->_top > 0){
		ps->_top--;
	}
	else{
		return;
	} }

/取栈顶元素（千万不要忘了，数组的下标从0开始！！）
STDataType StackTop(Stack* ps){
	assert(ps);
	return ps->_a[ps->_top-1];
}

int StackEmpty(Stack* ps){
	assert(ps);
	if (ps->_top == 0){
		return 1;
	}
	else{
		return 0;
	}
}

int StackSize(Stack* ps){
	assert(ps);
	return ps->_top;
}

void StackPrint(Stack* ps){
	assert(ps);
	//非空
	while (StackEmpty(ps) != 1){
		printf("%d ", StackTop(ps));
		StackPop(ps);
	}
	printf("\n");
}

使用场景：经常用在需要更新数据，新进来的数据和现有的数据进行对比，然后新进来的数据替换原有数据，依次类推。这个过程中要必须注意新旧数据的切换顺序，所以里列表的索引很关键。
列表
Python中列表是可变的，这是它区别于字符串和元组的最重要的特点，一句话概括即：列表可以修改，而字符串和元组不能。
以下是 Python 中列表的方法：
方法和描述
list.append(x) 把一个元素添加到列表的结尾，相当于 a[len(a):] = [x]。
list.extend(L) 通过添加指定列表的所有元素来扩充列表，相当于 a[len(a):] = L。
list.insert(i, x) 在指定位置插入一个元素。第一个参数是准备插入到其前面的那个元素的索引，例如 a.insert(0, x) 会插入到整个列表之前，而 a.insert(len(a), x) 相当于 a.append(x) 。
list.remove(x) 删除列表中值为 x 的第一个元素。如果没有这样的元素，就会返回一个错误。
list.pop([i]) 从列表的指定位置移除元素，并将其返回。如果没有指定索引，a.pop()返回最后一个元素。元素随即从列表中被移除。（方法中 i 两边的方括号表示这个参数是可选的，而不是要求你输入一对方括号，你会经常在 Python 库参考手册中遇到这样的标记。）
list.clear() 移除列表中的所有项，等于del a[:]。
list.index(x) 返回列表中第一个值为 x 的元素的索引。如果没有匹配的元素就会返回一个错误。
list.count(x) 返回 x 在列表中出现的次数。
list.sort() 对列表中的元素进行排序。
list.reverse() 倒排列表中的元素。
list.copy() 返回列表的浅复制，等于a[:]。
将列表当做堆栈使用(后进先出)
列表方法使得列表可以很方便的作为一个堆栈来使用，堆栈作为特定的数据结构，最先进入的元素最后一个被释放（后进先出）。用 append() 方法可以把一个元素添加到堆栈顶。用不指定索引的 pop() 方法可以把一个元素从堆栈顶释放出来。例如：
>>> list_t=["a","b","c"]
>>> list_t.append("d")
>>> list_t.append("e")
>>> list_t
['a', 'b', 'c', 'd', 'e']
>>> list_t.pop()
'e'
>>> list_t
['a', 'b', 'c', 'd']
>>> list_t.pop()
'd'
>>> list_t
['a', 'b', 'c']
将列表当作队列使用（后进后出）
也可以把列表当做队列用，只是在队列里第一加入的元素，第一个取出来；但是拿列表用作这样的目的效率不高。在列表的最后添加或者弹出元素速度快，然而在列表里插入或者从头部弹出速度却不快（因为所有其他的元素都得一个一个地移动）
>>> from collections import deque
>>> list_t=deque(["a","b","c"])
>>> list_t.append("d")
>>> list_t
deque(['a', 'b', 'c', 'd'])
>>> list_t.popleft()
'a'
>>> list_t
deque(['b', 'c', 'd'])
>>>

栈(Stack)是一种特殊的线性表，其插入和删除操作均在表的一端进行，是一种运算受限的线性表

栈顶(top)是栈中允许插入和删除的一端。

栈底(bottom)是栈顶的另一端

顺序栈：
#include<stdio.h>
#include<stdlib.h>
#define Stack_Init_Size 100 //栈容量
#define StackIncrement 10 //栈增量
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int SElemType;
typedef int Status;
typedef struct {
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;
Status InitSqStack(SqStack* S)
{
	S->base = (SElemType*)malloc(Stack_Init_Size * sizeof(SElemType));
	S->top = S->base;
	S->stacksize = Stack_Init_Size;
	return OK;
}
Status Push(SqStack* s, SElemType e)
{
	if (s->top - s->base >= s->stacksize)
	{
		s->base = (SElemType*)realloc(s->base,((int)s->stacksize + StackIncrement) * sizeof(SElemType));
		if (s->base==NULL)
			exit(OVERFLOW);
		s->top = s->base + s->stacksize;
		s->stacksize += StackIncrement;
	}
	*(s->top) = e;
	s->top++;
	return OK;
}
SElemType Pop(SqStack* s)
{
	SElemType e;
	if (s->top == s->base)
	{
		return ERROR;
	}
	else
	{
		s->top--;//注意出栈是先--
		e = *(s->top);
		return e;
	}
}
Status Destroy(SqStack* S)
{
	free(S->base);
	S->base = NULL;
	S->top = NULL;
	S->stacksize = 0;
	return OK;
}
Status Clear(SqStack* S)
{
	S->top = S->base;
	return OK;
}
Status Is_empty(SqStack* S)
{
	if (S->top == S->base)
		return TRUE;
	else
		return FALSE;
}
int Length(SqStack* S)
{
	return (int)(S->top - S->base);
}
void StackTraverse(SqStack* s)
{
	SElemType* p;
	p = s->top;
	while (p!=s->base)
	{ 
		p--;
		printf("%d\n", *(p));
	}
}
SElemType GetTop(SqStack* s)
{
	s->top--;
	return *s->top;
}
int main()
{
	SqStack* s=(SqStack*)malloc(sizeof(SqStack));
	InitSqStack(s);
	for (int i = 0; i < 10; ++i)
	{
		Push(s, i);
	}
	printf("长度： %d\n", Length(s));
	for (int i = 0; i < 10; ++i)
	{
		printf("%d\n", Pop(s));
	}
	return 0;
}

链式栈
#include<stdio.h>
#include<stdlib.h>
#define Stack_Init_Size 100 //栈容量
#define StackIncrement 10 //栈增量
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int SElemType;
typedef int Status;
typedef struct SNode {
	SElemType data;
	struct  SNode* next;
}SNode,*LinkStack;
LinkStack InitStack()//注意这个初始化方式！！！！！！
{
	LinkStack s = (SNode*)malloc(sizeof(SNode));
	if (!s)
		exit(OVERFLOW);
	s->next = NULL;
	return s;
}
void Push(LinkStack s, SElemType e)
{
	LinkStack p = (SNode*)malloc(sizeof(SNode));
	if (p == NULL)
		exit(OVERFLOW);
	p->data = e;
	p->next = NULL;
	p->next = s->next;
	s->next=p;//与单链表的头插法相似
}
SElemType Pop(LinkStack s)
{
	LinkStack q;
	q = s->next;
	SElemType e= q->data;
	s->next = q->next;  
	free(q);//删除单链表的第一个元素
	return e;
}
void DestroyStack(LinkStack s)
{
	free(s);
}
void ClearStack(LinkStack s)
{
	s->next = NULL;
}
Status StackEmpty(LinkStack s)
{
	if (s->next == NULL)
		return TRUE;
	else
	{
		return FALSE;
	}
}
int StackLength(LinkStack s)
{
	int i = 0;
	SNode* p = s->next;
	while (p!=NULL)
	{
		i++;	
		p = p->next;
	}
	return i;
}
SElemType GetTop(LinkStack l)
{
	return l->next->data;
}
void StackTravers(LinkStack s)
{
	SNode* p = s->next;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}
int main()
{
	LinkStack s = (SNode*)malloc(sizeof(SNode));
	s=InitStack();
	for (int i = 0; i < 10; i++)
	{
		Push(s, i);
	}
	Pop(s);
	StackTravers(s);
	return 0;
}