栈的基本 *** 作（C语言）

用C语言实现链栈的基本 *** 作：

顺序栈 *** 作：

• initSlist(&list)                  //初始化栈
• pushSlist(&list, data)      //入栈
• Pop(&list)                       //出栈
• printTop(&list)                //取当前栈顶的值

链栈 *** 作：

• initSNode(&S)                //初始化栈，创建一个空栈；

• pushSnode(&S, data)    //入栈

• PopSnode(&S)              //出栈

• getSnodeTop(&S)          //取当前栈顶的值

顺序栈：

链栈：（类似头插法）

总之..栈其实就是后进先出的线性表(类似水桶）

一、顺序栈 1、栈的相关结构体

// 宏定义一个栈容量
#define Slist_max_size 10;

// 构造顺序栈数据类型
typedef int Sint;
// 构造顺序栈的结构体
typedef struct Slist
{
    Sint *base;    //栈底
    Sint *top;     //栈顶
    int scapacity; //栈容量
} Slist;

2、初始化栈

// 初始化栈
void initSlist(Slist *list)
{

    // 栈底自由分配一个存储地址
    list->base = (Sint *)malloc(sizeof(Sint));
    if (!list->base)
    {
        printf("存储分配失败\n");
    }
    else
    {
        // 当top = base时表示为空栈
        list->top = list->base;
        list->scapacity = Slist_max_size;
        printf("top的地址:%p  ", list->top);
        printf("base的地址:%p\n", list->base);
        printf("初始化成功\n");
    }
}

3、入栈

// 入栈
void pushSlist(Slist *list, Sint data)
{
    if (list->top - list->base == list->scapacity)
    {
        printf("栈满了\n");
    }
    else
    {
        *list->top = data;
        printf("此时的栈顶的值:%d  ", *list->top);
        list->top++; //地址在当前地址上加4个字节（int型4个字节）
        printf("入栈后的top地址:%p  ", list->top);
        printf("入栈成功\n");
    }
}

4、出栈

// 出栈
void Pop(Slist *list)
{
    if (list->top == list->base)
        printf("栈空\n");
    else
    {
        list->top--;  //地址在当前地址上减4个字节（int型4个字节）
        printf("出栈后的top地址:%p\n", list->top);
    }
}

5、取当前栈顶的值

// 取栈顶的值
void printTop(Slist *list)
{
    if (list->top == list->base)
        printf("栈空\n");
    else
    {
        // 因为当前的栈顶top的地址是栈顶元素的上一个位置
        // 所以取值时需要-1降回栈顶元素的位置
        list->top--;
        printf("取栈顶值时top的地址:%p  ", list->top);
        printf("当前栈顶的值为%d\n", *list->top);
    }
}

测试结果

主函数：

int main()
{
    Slist list;
    initSlist(&list);
    pushSlist(&list, 6);
    pushSlist(&list, 10);
    Pop(&list);
    printTop(&list);
    // 测试判断栈是否为空功能
    printTop(&list);
    return 0;
}

开始运行..

top的地址:00000284a4c31650  base的地址:00000284a4c31650
初始化成功
此时的栈顶的值:6  入栈后的top地址:00000284a4c31654  入栈成功
此时的栈顶的值:10  入栈后的top地址:00000284a4c31658  入栈成功
出栈后的top地址:00000284a4c31654
取栈顶值时top的地址:00000284a4c31650  当前栈顶的值为6
栈空

二、链栈 1、栈的相关结构体

// 栈的数据类型
typedef int DATA;
// 栈的结构体
typedef struct SNode
{
  DATA data;
  struct SNode *next;
}SNode;

// 创建一个栈顶结构体
typedef struct Stop
{
  struct SNode *Top;
}Stop;

2、初始化栈

// 初始化栈
void initSNode(Stop *S)
{
  S = (Stop*)malloc(sizeof(Stop));     // 分配内存
  S->Top = NULL;                       // 空栈时栈顶置空
  printf("初始化完成\n");
}

3、入栈

// 入栈
void pushSnode(Stop *S, DATA data)
{
  SNode *p = (SNode*)malloc(sizeof(SNode));
  p->data = data;
  p->next = S->Top;
  printf("S的地址——%p\n", S);
  printf("入栈前栈顶的地址——%p\n",S->Top); 
  S->Top = p;
  printf("入栈成功\n");
  printf("入栈后栈顶的地址——%p\n", S->Top);
  printf("当前栈顶的值是:%d\n", S->Top->data);
}

4、出栈

// 出栈
void PopSnode(Stop *S)
{
  SNode *Pt = (SNode*)malloc(sizeof(SNode));
  Pt = S->Top;
  printf("释放前的地址——%p\n", S->Top);
  S->Top = S->Top->next;           // 释放后栈顶往后指
  free(Pt);
  printf("释放成功\n");
  printf("释放后的地址——%p\n", S->Top);
}

5、取当前栈顶的值

// 取栈顶的值
void getSnodeTop(Stop *S)
{
  if (!S->Top)
  {
    printf("当前是空栈，请先入栈\n");
  }
  else 
  {
    printf("取栈顶值时的地址——%p\n", S->Top);
    printf("当前栈顶的值是:%d\n", S->Top->data);
  }
}

测试结果

主函数：

//测试入栈6，入栈10，之后把10出栈，最后输出栈顶值
int main(void) {
  Stop S;
  initSNode(&S);
  pushSnode(&S, 6);
  pushSnode(&S, 10);
  PopSnode(&S);
  getSnodeTop(&S);
  return 0;
}

开始运行...
初始化完成
S的地址——0x7ffd4db62b90
入栈前栈顶的地址——0x7ffd4db62c80
入栈成功
入栈后栈顶的地址——0x1acb690
当前栈顶的值是:6
S的地址——0x7ffd4db62b90
入栈前栈顶的地址——0x1acb690
入栈成功
入栈后栈顶的地址——0x1acb6b0
当前栈顶的值是:10
释放前的地址——0x1acb6b0
释放成功
释放后的地址——0x1acb690
取栈顶值时的地址——0x1acb690
当前栈顶的值是:6