栈：
      后进先出（Last In First Out，LIFO）的线性序列，称为“栈”。栈也是一种线性表，只不过它是操作受限的线性表，只能在一端进出操作。进出的一端称为栈顶（top）,另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储，分别称为顺序栈和链栈。
顺序栈：
     顺序栈需要两个指针，base表示栈底指针（指向首地址或基地址），top表示栈顶指针。（top指针永远指向空，即指向栈顶元素的下一位置）
typedef 
顺序栈的动态分配：
顺序栈的静态分配：
顺序栈初始化：
bool 
顺序栈入栈：
       注意：每次入栈前，都需要判断栈是否已满。
bool 
顺序栈出栈：
      注意：每次出栈前都需要判断栈是否为空。
bool 
顺序栈取栈顶：
int 
链栈：
       链栈只需要一个指针S指向栈顶元素即可。
链栈入栈：
    链栈入栈操作：入栈前：指针S指向栈顶结点；入栈后：新生成的结点，指针p指向它；然后把入栈前的栈顶结点的地址赋值给新生成结点的next域，最后更新S指针指向新生成的结点（指向栈顶结点）。
链栈出栈：
 链栈出栈：需要一个指针p标记栈顶元素，用于最后释放空间。出栈：首先：指针p指向栈顶结点，然后更新栈顶指针s指向下一个结点；最后释放指针p指向的结点即可。
链栈取栈顶：
 链栈取栈顶只需要s->data,一步操作即可。
队列：
      先进先出（First In First Out，FIFO）的线性序列，称为“队列”。队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作：一端进，一端出。进的一端称为队尾(rear),出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。
顺序队列
     队列的顺序存储形式，可以用一段连续的空间存储数据元素，用两个整数变量记录队头和队尾元素的下标。
顺序队列动态分配
typedef  
顺序队列静态分配：
顺序队列初始化
//队列的初始化
顺序队列入队：
      将新入队的元素，插在队尾，然后更新下表Q.rear。Q.rear和Q.front都是数组的下标，Q.base是数组。每次入队前要先判断对是否已满。
Q
也可以一边入队，一遍出队。出队Q.front向后移动。
e
      当尾指针指向了空，但是队列前面还存在未占用的空间，这种情况叫做假溢出。此时，将新来的元素插入到队首，这种队列叫做循环队列。代码如下处理，每次移动指针后对Maxsize取余处理临界状态。
(
循环队列队空：
循环队列队空条件：
Q
循环队列队满:
      队满条件：浪费一个空间，当Q.rear的下一个元素为Q.front是表示队满。
(
循环队列入队
入队：
Q
//循环队列的入队
循环队列出队
       循环队列出队：
e
 队列中元素个数：
(
//循环队列的出队
链队：
    需要头指针，出队跳过第一个结点，入队将新结点插入到尾部即可。
链队出队：指针q指向要跳过的结点，如下图：
q
链队入队：将新生成的结点，next域置空，原链队的next保存新生成的结点地址，更新Q.rear指向新入队的结点即可。
Q
栈完整代码：
https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/3.1.SqStack.cpp​github.com
队列完整代码：
https://github.com/xinhai2017/Data-Structures-and-Algorithms/blob/master/3.2.SqQueue.cpp​github.com

1. 栈的定义
栈的定义：限定仅在表尾进行插入和删除操作的线性表。同时因为只能在表尾进行操作，所以栈又称为后进先出的线性表。见下图，浅灰色的元素后进入栈结构，出栈的时候却是第一个出去。
我们针对栈结构元素的插入和删除，分别叫做“Push”压栈和“Pop”弹栈。
2. 顺序栈的插入和删除
既然栈是线性表，而线性表包括顺序表和链表，那么同样栈也包括顺序栈和链栈。顺序栈中我们定义一个top指针，其实这里只是个游标，对应着栈顶元素的下标，比如top是0，那栈顶元素下标就是0，表示只有一个0号元素，通常规定如果top等于-1，表示空栈。见下图所示，一个有5个元素空间的顺序栈结构，当top=1时，有两个元素，top=-1时，空栈，top=4时，满栈。
那么进栈操作就很明显，只要移动我们的top游标即可，进一个top++，而删除的时候则top--
3. 代码实现
那么我们就来实现下顺序栈的push和pop，以及清空栈clear
还是先定义一下数据元素，包含一个id和一个name
typedef struct DataElement
{
	int id;
	const char* name;
}DataElement;
接着定义顺序栈结构，包括数组元素、top指针（游标）、数组长度
typedef struct SeqStack
{
	DataElement elements[MAX_SIZE];	//栈内元素数组
	int top;	//栈顶（数组中下标），如果为-1，表明栈是空的
	int length;	//当前栈的元素个数
}SeqStack;
然后我们来实现一下压栈push操作。注意：我们插入的元素下标是要将top加加后得到的值，因为top加加后才指向新的元素空间。
void PushSeqStack(SeqStack* seqStack, DataElement element)
{
	if (seqStack->top == MAX_SIZE)
	{
		printf("满栈，压栈失败！n");
		return;
	}
	seqStack->top++;
	seqStack->elements[seqStack->top] = element;
	seqStack->length++;
	return;
}
接着实现弹栈pop操作，同理我们需要先将top值减减。
void PopSeqStack(SeqStack* seqStack)
{
	if (seqStack->top == -1)
	{
		printf("空栈，弹栈失败！n");
		return;
	}
	seqStack->top--;
	seqStack->length--;
	return;
}
然后实现一下初始化函数，初始化数组的长度和top指针后，直接压栈即可。
void InitSeqStack(SeqStack* seqStack, int length, DataElement* dataArray)
{
	seqStack->length = 0;
	seqStack->top = -1;
	for (int i = 0; i < length; i++)
	{
		PushSeqStack(seqStack, dataArray[i]);
	}
}
接着实现清空栈，直接将top赋值-1，数组长度归零即可。
void ClearSeqStack(SeqStack* seqStack)
{
	seqStack->length = 0;
	seqStack->top = -1;
}
然后是“是否为空”函数，也很简单，只需判断top是否为-1
int IsEmpty(SeqStack* seqStack)
{
	if (seqStack->top == -1)
		return 1;
	return 0;
}
最后为了测试，实现一个打印顺序栈。这和遍历数组没多大区别。
void PrintSeqStack(SeqStack* seqStack)
{
	if (seqStack->top == -1)
	{
		printf("空栈！n");
		return;
	}
	for (int i = 0; i < seqStack->length; i++)
	{
		printf("%dt%sn", seqStack->elements[i].id, seqStack->elements[i].name);
	}
}
4. 测试代码
接着我们测试一下，先初始化待插入的数据元素
DataElement dataArray[] =
{
    { 1, "娜美"},
    { 2, "罗宾"},
    { 3, "大和"},
    { 4, "汉库克"}
};
然后实现测试函数，这次我们动态分配顺序栈空间，然后将4个元素全部压入栈中，接着将表尾元素弹栈，最后清空栈。
void TestSeqStack()
{
    SeqStack* seqStack = (SeqStack*)malloc(sizeof(SeqStack)); 
    int length = sizeof(dataArray) / sizeof(dataArray[0]);
    InitSeqStack(seqStack, length, dataArray);
    printf("压栈后：n");
    PrintSeqStack(seqStack);
    PopSeqStack(seqStack);
    printf("弹栈后：n");
    PrintSeqStack(seqStack);
    ClearSeqStack(seqStack);
    printf("清空栈后：n");
    PrintSeqStack(seqStack);
    free(seqStack);
}
编译运行，可以看到，弹栈后4号元素“汉库克”（下标为3的元素）被删除了。清空后也是没问题。
5. 总结
优点：顺序栈在插入和删除时候不需要移动元素，只需移动top指针。
缺点：顺序栈和顺序表一样，都需要预先定好数组空间，不像链表那样机动。

栈只允许在有序的线性资料集合的一端(top)进行加入数据(push)和移除数据(pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。
两种栈的实现方式: 1.顺序栈(数据实现) 2.链式栈(链表实现)
1.顺序栈(数组实现栈)
顺序栈的实现
0.准备工作
#define OK 1
1.构建空栈
// 构建一个空栈S
2.将栈置空
// 将栈置空
3.判断顺序栈是否为空
// 判断顺序栈是否为空;
4.返回栈的长度
// 返回栈的长度
5.获取栈顶元素
// 获取栈顶
6. push元素e为新栈顶元素
// 插入元素e为新栈顶元素
7. pop S栈顶元素,并且用e带回
// popS栈顶元素,并且用e带回
8. 从栈底到栈顶依次对栈中的每个元素打印
// 从栈底到栈顶依次对栈中的每个元素打印
9.使用栈并打印
// 使用栈
打印出来的结果
2.链式栈
0.结构
1.入栈(push)
第0步：创建节点node
第1步:   把创建的node的next指向栈顶top
第2步：把top指向创建的node
2.出栈(pop)
第1步: 记录需要弹出的节点P
第2步: 把top指向top的next节点
第3步: 释放节点P
链式栈的实现
0.准备工作
#define OK 1
1.构造一个空栈S
// 构造一个空栈S
2.把链栈S置为空栈
Status 
3. 检测空栈
// 若栈S为空栈,则返回TRUE, 否则返回FALSE
4.栈的长度
// 返回S的元素个数,即栈的长度
5. 获取栈顶元素
// 若链栈S不为空,则用e返回栈顶元素,并返回OK ,否则返回ERROR
6. 入栈(Push)
// 插入元素e到链栈S (成为栈顶新元素)
7. 出栈(Pop)
// 若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR
8.遍历链栈
// 遍历链栈，其实就是遍历链表
9.使用和打印
int 
打印的结果:

数据结构-栈
更简单的介绍，在《程序是怎样跑起来的》一书中有简要形象的说明
一.栈的基本概念
栈是一种特殊的线性表，其插入删除操作都只能在表的尾部进行。
栈中允许插入、删除操作的一端称为栈顶，另一端称为栈底。
通常栈的插入操作叫入栈，栈的删除操作叫做出栈。
栈的插入和删除操作只允许在栈顶进行，每次入栈的元素即成为栈顶元素，每次最先出栈的总是栈顶元素，所以栈是一种后进先出的线性表。
二.顺序栈
1.介绍
顺序栈是用数组实现的，因为入栈和出栈操作都是在栈顶进行的，所以增加变量top来指示栈顶元素的位置，top指向栈顶元素存储位置的下一个存储单元的位置，空栈时top=0。
2.基本操作
1）入栈操作
 入栈操作push(x)是将数据元素x作为栈顶元素插入顺序栈中，主要操作如下：
判断顺序栈是否为满，若满则抛出异常
将x存入top所指的存储单元位置
top加1
def 
2)出栈操作
 出栈操作pop()是将栈顶元素从栈中删除并返回，主要步骤如下：
判断顺序栈是否为空，若空则返回null
top减1
返回top所指的栈顶元素的值 
def 
3.应用
利用顺序栈实现括号匹配：
def 
三.链栈
1.介绍
采用链式存储结构的栈称为链栈，由于入栈和出栈只能在栈顶进行，不存在在栈的任意位置进行插入和删除操作，所以不需要设置头节点，只需要将指针top指向栈顶元素节点。
2.基本操作 
1）入栈操作
入栈操作push(x)是将数据域为x的节点插入到链栈的栈顶，主要步骤如下：
构造数据值域为x的新节点
改变新节点和首节点的指针域，使新节点成为新的栈顶节点 
def 
2)出栈操作
出栈操作pop()是将栈顶元素从链栈中删除并返回其数据域的值，主要步骤如下：
判断链栈是否为空，若空则返回null
修改top指针域的值，返回被删节点的数据域的值
def