引言
hello各位小伙伴，我还在，这一周真是累到吐血，每天都二三点才睡，早上7点又得爬起来上班。。。
不过，总算熬过来了，这一周终于有时间可以更新咯，至于java中的HashSet，HashMap等源码还没有进行解析，咱们别急，我抽空更。。。
今天给大家带来的是数据结构之
栈
不过，由于篇幅原因，今天的文章仅仅是上篇，如果估计没错的话，还有中篇、下篇等着呢，哈哈哈，大家有空时候瞅一眼就好了。
1、什么是栈
洗碗时，将洗好的碗一个叠着一个摆放到柜子中；
用碗时，再讲碗逐个取下来
恩，通常来说，摆放碗时是由下而上依次放置，而取碗时，则是从上到下依次取出。这些都是生活中的常理，这样的顺序，如果用我们的术语说的话，就是碗的取出的原则称为“后进先出”，即最后放的碗在取出的时候是先被取出来的。
“后进先出”记住这个术语
在各种数据结构中，栈 （stack）这个数据结构就遵循这个原则。
栈也是一种线性表，但是他是收到限制的线性表，我们在前边学到的顺序表，链表中，我们可以在他们的两端进行插入，删除操作，而栈呢，他只允许在一端进行插入和删除的操作，正如下图所示
如图所示，图中，有栈顶和栈底，
栈顶：栈中允许执行插入和删除操作的一端称为栈顶
栈底：栈中不允许执行插入和删除操作的一端称为栈底
入栈、压栈
向一个栈中插入新元素称之为入栈、压栈
入栈之后，该元素被放在栈顶元素的上边，成为新的栈顶元素。
执行入栈操作时，会先将元素插入到栈中，然后按照数据入栈的先后顺序，从下往上依次排列。
每当插入新的元素时，栈顶指针就会向上移动，指向新插入的元素。
当栈已满时，不能继续执行入栈操作。
出栈、弹栈
从一个栈中删除元素又称之为出栈、弹栈
把栈顶元素删除，使其下面的相邻元素成为新的栈顶元素
执行出栈操作时，栈顶元素会先被弹出，接着按照后进先出的原则将栈中的元素依次弹出，。
弹出栈顶元素后，栈顶指针就会向下移动，指向原来栈顶下面的元素，这个元素就成为了新的栈顶元素。
当栈为空时，不能继续执行出栈操作。
注意
如果要从栈中获取元素，只能通过栈顶指针取到栈顶元素，然后依次取出，除此之外没有别的方式。正如上图所示，如果栈顶元素an没有弹出时，an下边的元素是不能取到的。
由于栈遵循后进先出（Last In First Out,LIFO）原则，因此又把栈称为后进先出表
栈的常用操作如下：
* Create()(或 Init()):创建栈（或初始化栈）
* IsEmpty():判断栈是否为空
* Push():进栈
* Pop():出栈
* getTop():获取栈顶元素。只是读取栈顶元素，并不将元素弹出栈
* getSize():获取栈的长度
* Destory():销毁栈
进栈、出栈相当于线性表中的插入和删除操作，两者不同的是，栈顶是栈读取、插入的唯一出入口。
2、栈的实现
栈也是线性表，因此线性表的存储结构对栈也适用，栈也分为
顺序栈
链栈
两种存储结构。存储结构的不同使得实现栈的基本算法也有所不同。
2.1.1栈的顺序存储实现
栈的顺序存储也称为顺序栈，他利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时设置栈顶标识top来指示栈顶元素在顺序栈中的位置。向顺序栈中插入元素时，其过程如下图所示：
如上图所示，向栈中插入元素时，需先使top指针指向栈顶上面的空位，然后再进行赋值
删除栈中元素时，只将top指针向下移动，指向新的栈顶元素，删除过程如下图所示
由上图我们知道，弹栈是将top指针移动，指向新的栈顶位置，原来的栈顶元素依然存在于存储单元中，但是无法通过栈进行访问。
注意，我们介绍栈的时候画的是上下结构的，现在画的是水平结构的，这个只是表示形式，并不是栈真实的结构，真实的结构就是一堆内存地址，更表现形式没关系，知道这点就行了。
学习完栈的入栈，弹栈，原理后，下面通过代码实现了一个顺序栈，这个顺序栈所具备的功能如下：
* 顺序栈的初始化
* 判断栈是否为空
* 获取栈顶元素
* 弹栈、压栈
* 销毁栈
请看下方代码
seqstack.h(头文件)：
#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_
#define MAXSIZE 1024
#define INFINITY 65535
typedef struct{
int data[MAXSIZE];//在结构中定义一个数组
int top;//指示栈顶元素，在数组中相当于索引
}SeqStack;
void InitStack(SeqStack * stack);//初始化栈
int IsEmpty(SeqStack * stack);//判断栈是否为空
int SeqStack_Top(SeqStack * stack);//返回栈顶元素
int SeqStack_Pop(SeqStack * stack);//弹出栈顶元素
void SeqStack_push(SeqStack * stack,int val);//将元素val压入栈中
void SeqStack_Destory(SeqStack * stack);//销毁栈
#endif
seqstack.c(函数实现文件)
#include "seqstack.h"
void InitStack(SeqStack *stack){//初始化栈
stack->top=-1;
}
int IsEmpty(SeqStack * stack){//判断栈是否为空
if(stack->top=-1)
return 1;
return 0;
}
int SeqStack_Top(SeqStack * stack){//返回栈顶元素
if(!IsEmpty(stack)){
return(stack->data[stack->top]);
}
return INFINITY;//只是作为一个简单标识，有可能栈顶元素也为-1
}
int SeqStack_Pop(SeqStack * stack){//弹出栈顶元素
if(!IsEmpty(stack)){
return(stack->data[stack->top--]);//弹出一个元素后，top要减1
}
return INFINITY;
}
int SeqStack_Push(SeqStack * stack,int val){//将元素val压入栈中
if(stack->top>=MAXSIZE-1)//栈已经满了
return;
stack->top++;//栈顶索引+1
stack->data[stack->top]=val;//将值val赋给新的栈顶元素
}
void SeqStack_Detory(SeqStack * stack){//销毁栈
if(!IsEmpty(stack)){
free(stack);
}
}
下面是测试文件
main.c
#include <stdio.h>
#include <stdlib.h>
#include "seqstack.h"
int main(){
srand((unsigned)time(0));//以时间为种子产生随机数
SeqStack stack;//创建一个顺序栈
InitStack(&stack);//初始化栈
//向栈中添加元素
for(int i=0;i<50;i++){
SeqStack.push(&stack,rand()%1000);//添加随机产生的数
}
//获取栈顶元素
printf("栈顶元素：%d\n",SeqStack_Top(&stack));
//打印栈中元素
printf("栈中的元素:");
for(int i=0;i<50;i++){
if(i%5==0)
printf("\n");
}
printf("%d",SeqStack_Pop(&stack));
}
printf("\n");
system("pause");
return 0;
2.1.2栈的链式存储实现
栈的链式存储也称为链栈，他和链表的存储原理一样，多可以利用闲散的空间来存储元素，用指针来建立个结点之间的逻辑关系。
链栈也会设置一个栈顶元素的标识符top，称为栈顶指针。
他和链表区别是，只能在一段进行各种操作，如下所示
如图所示，链栈就是一个单端操作的链表，他的插入、删除操作就是在链表的一端进行。
接下来，我们实现一个链栈，其功能如下：
* 创建一个链栈
* 判断链栈是否为空
* 压栈、弹栈
* 获取栈顶元素
* 销毁链栈
然后，会在main.c中进行测试
代码如下
linkstack.h 头文件
#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
typedef struct Node * pNode;
typedef struct Stack * LinkStack;
struct Node{//数据结点
int data;//数据
pNode next;//指针
};
struct Stack{//此结构记录栈的大小和栈顶元素指针
pNode top;//栈顶元素指针
int size;//栈大小
};
LinkStack Create();//创建栈
int IsEmpty(LinkStack lstack);//判断栈是否为空
int getSize(LinkStack lstack);//获取栈的大小
int Push(LinkStack lstack,int val);//元素入栈
pNode getTop(LinkStack lstack);//获取栈顶元素
pNode Pop(LinkStack lstack);//弹出栈顶元素
void Destory(LinkStack lstack);//销毁栈
#endif
linkstack.c 操作函数实现文件
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
LinkStack Create(){
LinkStack lstack=(LinkStack)malloc(sizeof(struct Stack));
if(lstack!=null){
lstack->top=NULL;
lstack->size=0;
}
return lstack;
}
int IsEmpty(LinkStack stack){
if(stack->top==NULL||stack->size==0){
return 1;
}
return 0;
}
int getSize(LinkStack stack){
if(!IsEmpty(stack)){
return(stack->size);
}
return 0;
}
int Push(LinkStack stack,int val){
pNode node=(pNode)malloc(sizeof(struct Node));
if(node!=null){
node->data=val;
node->next=getTop(lstack);
lstack->top=node;
lstack->size++;
}
return 1;
}
pNode getTop(LinkStack lstack){
if(!IsEmpty(lstack)){
return lstack->top;
}
return NULL;
}
pNode Pop(LinkStack lstack){
if(IsEmpty(lstack)){
return NULL;
}
pNode node=lstack->top;
lstack->top=lstack->top->next;
lstack->size--;
return node;
}
void Destory(LinkStack lstack){
if(IsEmpty(lstack)){
free(lstack);
printf("栈以为空，无需清理\n");
return;
}
//如果栈不为空，需要把栈中的结点都释放
do{
pNode pTmp;
pTmp=Pop(lstack);
free(pTmp);
}
while(lstack->size>0);
printf("栈销毁成功\n");
}
测试文件 main.c
#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"
int main(){
srand((unsigned)time(0);
LinkStack lstack=NULL;
lstack=Create();
//判断栈是否为空
int ret;
ret=IsEmpty(lstack);
if(ret)
printf("栈为空\n");
else
printf("创建成功\n");
//向栈中压入数据
for(int i=0;i<10;i++){
Push(lstack,rand()%100);
}
ret=IsEmpty(lstack);
if(ret)
printf("栈为空\n");
else
printf("栈\n");
//求栈的长度
printf("栈的长度为%d\n",getSize(lstack));
pNode topNode=getTop(lstack);
printf("栈顶元素为%d\n",topNode->data);
//打印栈中的元素
while(lstack->size>0){
printf("%d",((int *)Pop(lstack)));
}
printf("\n");
//销毁栈
Destory(lstack);
system("pause");
return 0;
}
总结
ok,看完了上面的两个例子，大家应该对顺序栈和链栈有了一个认识了吧，其实这些思想和顺序表和链表很相似，只不过出入口变成了一个，这些东西还得需要大家好好领悟，好好练习下本文中的代码哟。
持续更新，谢谢关注~~~
