数据结构：栈

基本概念

栈是一种逻辑结构，是特殊的线性表。特殊在：

只能在固定的一端操作

只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进后出 / 后进先出”的逻辑，这种逻辑 就被称为栈。栈在生活中到处可见，比如堆叠的盘子、电梯中的人们、嵌套函数的参数等等

由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的“插入”、“删除”，另
起了下面这些特定的名称：
栈顶：可以进行插入删除的一端
栈底：栈顶的对端
入栈/压栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()
出栈/弹栈：将节点从栈顶剔除，也称为弹栈，函数名通常为pop()
取栈顶：取得栈顶元素，但不出栈，函数名通常为top()
基于这种固定一端操作的简单约定，栈获得了“后进先出”的基本特性，如下图所示，最后一个放入
的元素，最先被拿出来：

存储形式

栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺
序栈，或采用链式存储形成链式栈。

顺序栈

顺序存储意味着开辟一块连续的内存来存储数据节点，一般而言，管理栈数据除了需要一块连
续的内存之外，还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置，如果有多线
程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体
之中：

// 顺序栈节点
struct seqStack
{
    datatype *data; // 顺序栈入口
    int size;       // 顺序栈总容量
    int top;        // 顺序栈栈顶元素下标
};

链式栈

链式栈的组织形式与链表无异，只不过插入删除被约束在固定的一端。为了便于操作，通常也
会创建所谓管理结构体，用来存储栈顶指针、栈元素个数等信息：

// 链式栈节点
typedef struct node
{
    datatype data;
    struct node *next;
}node;
// 链式栈管理结构体
struct linkStack
{
    node *top; // 链式栈栈顶指针
    int  size; // 链式栈当前元素个数
};

基本操作

不管是顺序栈，链式栈，栈的操作逻辑都是一样的，但由于存储形式不同，代码的实现是不同的。
下面分别将顺序栈和链式栈的基本核心操作罗列出来：
顺序栈

sstack.h

#ifndef __SSTACK_H
#define __SSTACK_H
// 数据类型
typedef int DATA;
// 顺序栈结构体
typedef  struct
{
    DATA      *pData; // 栈中元素的地址
    int         size; // 栈的总容量
    int         top;  // 栈顶元素下标
}SeqStack;
// 初始化栈
int SStack_init(SeqStack *s, int num);
// 判断栈是否已满
int SStack_isfull(SeqStack *st);
// 判断栈是否为空
int SStack_isempty(SeqStack *st);
// 入栈/压栈
int SStack_push(SeqStack *st,DATA data);
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data);
// 回收栈
int SStack_free(SeqStack *st);
#endif

sstack.c

#include <stdlib.h>
#include "sstack.h"
// 初始化栈
int SStack_init(SeqStack* s,int num)
{
    s -> pData = (DATA*)calloc(sizeof(DATA),num);
    if(s -> pData == NULL)
       return -1;
    s -> size  = num ;
    s -> top   = -1;
    return 0;
}
// 判断栈是否已满
int SStack_isfull(SeqStack *st)
{
    return st -> top + 1 == st -> size;
}
int SStack_isempty(SeqStack *st)
{
    return st -> top == -1;
}
// 压栈/入栈
int SStack_push(SeqStack *st,DATA data)
{
    if(SStack_isfull(st))
       return -1;
    st -> top++;
    st -> pData[st -> top] = data;
    return 0;
}
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data)
{
    if(SStack_isempty(st))
       return -1;
    *data = st -> pData[st -> top];
    st -> top--;
    return 0;
}
// 回收栈
int SStack_free(SeqStack *st)
{
    if(st -> pData)
   {
         free(st->pData);
         st -> pData = NULL;
   }
    st -> top = -1;  
}

sstack_main.c

#include "sstack.h"
#include <stdio.h>
int main(void)
{
   SeqStack  st;
SStack_init(&st,10);
   register int i = 1;
   for(; i <=10; i++)
      SStack_push(&st,i);
   if(-1 == SStack_push(&st,1024))
     fprintf(stderr,"满栈,插入失败\n");
    while(!SStack_isempty(&st))
   {
         DATA   data = 0;
         SStack_pop(&st,&data);
         printf("%4d",data);         
   }
    printf("\n");
    SStack_free(&st);
   
    return 0;  
}