栈的本质是线性表，可以说他是一种特殊的线性表，因为只能在线性表的一端进行操作（栈顶），不能操作的那一端交栈底。
 
栈的性质：后进先出（LIFO）
 
 
栈可以分为两种：静态栈和动态栈
 
两种栈的实现都可以复用单链表的代码，其中静态栈可以复用顺序表的代码；动态栈可以复用单链表的代码。其实可以从头到尾实现一个栈数据结构，但是那样做是没有意义的。代码复用的思想是工程中常见的，而且基于已经测试过的代码就减少了中间会遇到的其它问题。
 
而且由于栈的操作仅仅能在线性表的一端进行，所以无论是入栈还是出栈的操作，时间复杂度都是O(1)
 
首先是静态栈的实现，项目中需要添加之前实现的顺序表代码。需要注意的是栈顶的选择可以有两种方式，在顺序表的头部或者尾部，这里选择线性表的尾部作为栈顶，也就是说只能允许在这一端进行操作；相应的在进行出栈操作时也是从线性表的尾部开始。
 
SeqStack* SeqStack_Greate(int capacity)
{
	return SeqList_Create(capacity);
}

void SeqStack_Destroy(SeqStack* stack)
{
	SeqList_Destroy(stack); 
}

void SeqStack_Clear(SeqStack* stack)
{
	SeqList_Clear(stack);
}

int SeqStack_Push(SeqStack* stack, void* item)
{
	return SeqList_Insert(stack, item, SeqList_Length(stack));	// 选择线性表的尾部作为栈顶，在这一端操作栈
}

void* SeqStack_Pop(SeqStack* stack)
{
	return SeqList_Delete(stack, SeqList_Length(stack) - 1); 
}

// 返回栈顶元素
void* SeqStack_Top(SeqStack* stack)
{
	return SeqList_Get(stack, SeqList_Length(stack) - 1);
}

int SeqStack_Size(SeqStack* stack)
{
	return SeqList_Length(stack);
}

int SeqStack_Capacity(SeqStack* stack)
{
	return SeqList_Capacity(stack);
}
 
动态栈的实现比顺序栈要复杂，首先需要定义结点的结构体，用来表示每次进栈或者出栈的元素，然后进栈和出栈的操作也要malloc和free相应的内存空间。
 
// 定义栈的每一个结构体组成
typedef struct _tag_LinkStackNode
{
    LinkListNode header;
    void* item;		// 保存地址
} TLinkStackNode;

// 创建一个只含头结点的栈
LinkStack* LinkStack_Create()
{
    return LinkList_Create();
}

void LinkStack_Destroy(LinkStack* stack)
{
    LinkStack_Clear(stack);

    LinkList_Destroy(stack);
}

// 链表中的每一个元素都是malloc出来的，单纯clear会产生内存泄漏
void LinkStack_Clear(LinkStack* stack)
{
    while( LinkStack_Size(stack) > 0 )
    {
        LinkStack_Pop(stack);
    }
}

int LinkStack_Push(LinkStack* stack, void* item)
{
    TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
    int ret = (node != NULL) && (item != NULL);
    
    if( ret )
    {
        node->item = item;	// 保存传进来的参数地址
        
        ret  = LinkList_Insert(stack, (LinkListNode*)node, 0); // 使用队头作为栈顶
    }
    
    if(!ret)
    {
        free(node);
    }
    
    return ret;
}

void* LinkStack_Pop(LinkStack* stack)
{
    TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);	// 首元素为栈顶
    void* ret = NULL;
    
    if( node != NULL )
    {
        ret = node->item;	// 返回删除的元素
        
        free(node);		// 释放掉结点空间 
    }
    
    return ret;
}

void* LinkStack_Top(LinkStack* stack)
{
    TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
    void* ret = NULL;
    
    if( node != NULL )
    {
        ret = node->item;	// 返回栈顶元素结点
    }
    
    return ret;
}

int LinkStack_Size(LinkStack* stack)
{
    return LinkList_Length(stack);
}
 
 

一.简介
 
在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P33),通过学习,能独立把赫斌老师教的敲出来,由于动态栈(链表阉割版)的功能很少,我并没有增加什么其它功能,但是我自己实现了静态栈(数组阉割版),还有就是分享一些我对动态栈,以及静态栈的理解.
 
二.什么是栈
 
简介已经说了,栈可以分为静态栈和动态栈.
 
静态栈是用数组来实现而动态栈是用链表来实现.
 
栈实现的功能就是:先进后出.
 
打个比喻就是把一块一块的方块放进一个箱子里,等到你不想放,想要从箱子取出来的时候,第一个出来的,就是你最后一次放的,而最后一个出来的,只能是最后一个出来,这就是所谓的先进后出.
 
具体图解
 
栈的实现需要确定顶部与底部.
 
静态栈与动态栈的区别:
 
      静态栈必须提前确定栈的大小(有限的),并且都是连续的.

      动态栈可以无限大小(内存够的情况下),并且是不连续的.
 
三.动态栈的图解
 

 由于图片较多…具体可以链接下载详看:百度网盘
 
四.函数功能实现的源码
 
理解不了可以看第三部分的图解
 
void init(PSTACK);	                                    	//初始化
 
 
void push_stack(PSTACK , int);	                            //入栈(压栈)
 
 
void traversal_output(PSTACK );	                             //遍历输出
 
 
int air(PSTACK );	                              	//判断是否为空
 
 
int pop(PSTACK , int*);	                                    	//出栈
 
 
void empty(PSTACK );	                              //清空栈
 
 
五.源码分享(可复现)
 
动态栈链接:百度网盘
 
静态栈链接:百度网盘
 
六.栈可以应用在那些方面
 
1.函数调用
 
2.中断
 
3.表达式求值(计算器)
 
4.内存分配
 
5.缓冲处理
 
6.迷宫

动态变量和静态变量的区别：
 
1、存储位置
 
动态变量：存储在内存出栈数据区
 
静态变量：存储在全局数据区（静态数据区）
 
2、生命期
 
动态变量：根据你定义的位置确定，比如你在一个函数中定义的，那么超出该函数范围变量将失效
 
静态变量：程序结束时才释放
 
3、作用域
 
动态变量：同样的要根据你定义的位置才能确定，和第二点的一样
 
静态变量：当前文件中有效
 
堆和栈的区分：
 
堆（Heap）栈（Stack）
 
1、内存分配方面：
 
堆：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式是类似于链表。可能用到的关键字如下：new、malloc、delete、free等等。
 
栈：由编译器(Compiler)自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
 
2、申请方式方面：
 
堆：需要程序员自己申请，并指明大小。在c中malloc函数如p1 = (char *)malloc(10)；在C++中用new运算符，但是注意p1、p2本身是在栈中的。因为他们还是可以认为是局部变量。
 
栈：由系统自动分配。 例如，声明在函数中一个局部变量 int b；系统自动在栈中为b开辟空间。
 
3、系统响应方面：
 
堆：操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样代码中的delete语句才能正确的释放本内存空间。另外由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
 
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
 
4、大小限制方面：
 
堆：是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
 
栈：在Windows下, 栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是固定的（是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
 
5、效率方面：
 
堆：是由new分配的内存，一般速度比较慢，而且容易产生内存碎片，不过用起来最方便，另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。
 
栈：由系统自动分配，速度较快。但程序员是无法控制的。
 
6、存放内容方面：
 
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
 
栈：在函数调用时第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈，然后是函数中的局部变量。 注意: 静态变量是不入栈的。当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
 
7、存取效率方面：
 
堆：char *s1 = “Hellow Word”；是在编译时就确定的；
 
栈：char s1[] = “Hellow Word”； 是在运行时赋值的；用数组比用指针速度要快一些，因为指针在底层汇编中需要用edx寄存器中转一下，而数组在栈上直接读取。

#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MAX_SIZE 100

typedef struct Stack
{
	DataType _arr[MAX_SIZE];//栈的元素最大个数
	int _top;//栈顶
	int _bottom;//栈低
	int len;//栈大小
}Stack,*Pstack;

// 栈的初始化 
void StackInit(Stack* s); 

// 入栈 
void StackPush(Stack* s, DataType data); 

// 出栈 
void StackPop(Stack* s); 

// 获取栈顶元素 
DataType StackTop(Stack* s); 

// 获取栈中元素个数 
int StackSize(Stack* s); 

// 检测栈是否为空 
int StackEmpty(Stack* s);
 test

#include"Stack.h"
void StackInit(Stack* S)
{
	S->_bottom = S->_top = 0;
	S->len = 0;
}

void StackPush(Stack* S, DataType data)
{
	if(S->len == MAX_SIZE)
	{
	printf("栈满溢出，添加失败！\n");
	return;
	}
	S->_top++;
	S->_arr[S->_top] = data;
	S->len++;
	printf(" %d 入栈成功!\n",data);
}

void StackPop(Stack* S)
{
	if(S->len == 0)
	{
	printf("栈为空！\n");
	return;
	}
	printf(" %d 出栈\n",S->_arr[S->_top]);
	S->_top--;
	S->len--;
	printf("此时栈顶元素为：%d\n",S->_arr[S->_top]);
}

DataType StackTop(Stack* S)
{
   if(S->len == 0)
	{
	printf("栈为空！\n");
	return;
	}
    printf("此时栈顶为： %d \n",S->_arr[S->_top]);
}

int StackSize(Stack* S)
{
	int ret = 0;
	ret = printf("栈中元素个数为：%d\n",S->len);
	return ret;
}

int StackEmpty(Stack* S)
{
   if(S->len == 0 )
	{
	printf("栈为空！\n");
	return 1;
	}
   else
   {
   printf("栈不为空！\n");
   return 0;
   }
}
main

#include"Stack.h"
test()
{
  Stack S;
  StackInit(&S);
  StackPush(&S, 1);
  StackPush(&S, 2);
  StackPush(&S, 3);
  StackPush(&S, 4);
  StackPush(&S, 5);
  StackSize(&S);
  StackTop(&S);
  StackPop(&S);
  StackPop(&S);
  StackEmpty(&S);



}
int main()
{
	test();
	system("pause");
}
动态栈
Stack.c
#include "stack.h"  
#include "Maze.h"  
  
void StackInit(Stack *S,int capacity)//栈初始化  
{  
    S->arr = (DataType*)malloc(capacity*sizeof(DataType));  
    if(NULL == S->arr)  
    {  
       printf("申请空间失败！\n");  
       return;  
    }  
    S->capacity = capacity;  
    S->size = 0;  
}  
  
  
void AddCapacity(Stack *S)//扩容  
{  
   if(NULL == S->arr)  
    {  
       printf("扩容失败\n");  
       return;  
    }  
   S->capacity = (DataType*)realloc(S->arr,sizeof(DataType)*(S->capacity)*2);//扩容为原来的二倍  
   if (NULL == S->arr)  
    {  
        printf("空间扩增失败!!!\n");  
        return;  
    }  
   S->capacity =2 * (S->capacity);  
}  
  
void PrintfStack(Stack *S)//打印栈  
{  
   int i = 0;  
   if(NULL == S->arr)  
    {  
       printf("打印失败\n");  
       return;  
    }  
   for(;i<S->size;i++)  
   {  
       printf("%d\n",S->arr[i]);  
   }  
   printf("\n");  
}  
  
void StackPush(Stack *S,DataType data)//入栈  
{  
    if(NULL == S->arr)  
    {  
       printf("入栈失败\n");  
       return;  
    }  
    if(S->capacity == S->size)//空间已满  
    {  
       AddCapacity(S);  
    }  
    S->arr[S->size] = data;  
    S->size++;  
}  
  
void StackPop(Stack *S)//出栈  
{  
   if(NULL == S->arr)  
    {  
       printf("出栈失败\n");  
       return;  
    }  
   S->size--;  
}  
  
DataType StackTop(PStack P)//获取栈顶元素  
{  
    return P->arr[P->size - 1];  
  /* int ret = 0; 
   if(NULL == S->arr) 
    { 
       printf("获取栈失败\n"); 
       return; 
    } 
   if(0 == S->size) 
   { 
   printf("栈为空！\n"); 
   return; 
   } 
   
   printf("栈顶元素为：%d \n", S->arr[S->size - 1]);*/  
}  
  
void StackSize(Stack *S)//获取元素个数  
{  
   if(NULL == S->arr)  
    {  
       printf("获取栈失败\n");  
       return;  
    }  
   printf("元素个数为：%d\n",S->size);  
}  
  
int StackEmpty(Stack *S)//检测栈是否为空  
{  
    if(NULL == S->arr)  
    {  
       printf("获取栈失败\n");  
       return 0;  
    }  
    if(S->size == 0)  
    {  
    printf("栈为空\n");  
    return 1;  
    }  
    return 0;  
}  


Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef struct int DataType
typedef struct Stack
{
   DataType *_arr;
   int  capacity;
   int  size;
}Stack;
// 栈的初始化   
void StackInit(Stack *S, int capacity);  
  
// 入栈   
void StackPush(Stack *S, DataType data);  
  
// 出栈   
void StackPop(Stack *S);  
  
// 获取栈顶元素   
DataType StackTop(Stack *S);  
  
// 获取栈中元素个数   
void StackSize(Stack *S);  
  
// 检测栈是否为空   
int StackEmpty(Stack *S);