引入

上一节，我们了解了栈的基本信息，知道了栈的各种特性，并且试着初始化了一个空栈。今天我们就来看看，如何将数据存入栈中。

入栈操作

入栈，我们有称之为压栈，简单来说就是向栈中存放数据。

  • 入栈从栈顶进行。
  • 每压入一个数据，top 的指针就要+1
  • 直到栈满了为止

代码实现

#define StackSize 100  //首先设置一个容量
//这里需要注意，实参的 s 需要先创建内存空间
void push(struct Stack *s,int data){
//下面开始判断栈是否满了，用头部-底部，如果距离为最大容量，就是满了
    if(s->top - s->base >= s->StackSize){
//给底部赋值一个新的最大容量，为什么是底部？因为那是起始地址
        s->base=(int *)realloc(s->base, (s->StackSize+10)*sizeof(LEN));
//顶部等于新底部+最大容量，就是顶部
        s->top=s->base+s->StackSize;  
//最大容量记得增加
        s->StackSize=s->StackSize+10;
    }
    //下面这两个才是实际的压栈
    *(s->top)=data;  //顶部的地址的值赋值为传递进来的形参
    s->top++;  //顶部向后移动一位
}

需要注意的事，我们的压栈分为两个部分，判断满栈和压入数据

判断满栈

  • 如果头部地址-底部地址，大于等于最大容量，就是满了
  • 底部存储的其实地址重新设置一个更大的地址
  • 使用 realloc 函数，使得新底部地址等于老底部+扩容量
  • 新头部跟老底部结合，新头部等于老底部+最大容量（因为满了嘛）
  • 最后将最大容量扩大

压入数据

  • 因为头部已经是在可写入位置了，所以直接将头部存储 data
  • 然后将头部向后移动，准备下一次写入数据。

出栈操作

出站相对如入栈就要简单的多

  • 注意是否为空栈
  • 先把 top 移动回来一位，再取值
  • 栈的当前容量-1

代码实现

int pop(struct Stack *s){
int data;
if(s->base==s->top){  //判断是否为空栈
return 0;
}
data=*--(s->top);  //先减减再取值
return data;
}

注意

我们这里 top 和 base，存储的都是地址，也就是是说

  • top 和 base 里面存储的是地址
  • 地址里面是一个动态生成的 int 型的100个数据位的地址
  • base 在地址的起始位置
  • top 在地址的当前存放数据的下一位，方便随时数据压进来
  • 你也可以把 base 和 top 理解为两个整数，然后表示的就是数组的下标
  • 但是使用指针将更加的灵活！

代码

这里放一个全套的代码，从初始化、压栈到出栈。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
#define LEN sizeof(int)
#define INCREMENT 10

struct Stack{
    int *top;
    int *base;
    int StackSize;
};

struct Stack *Stackinit(struct Stack *s){
    s->base=(int *)malloc(MAXSIZE * LEN);
    s->top=s->base;
    s->StackSize=MAXSIZE;
    return s;
}

void push(struct Stack *s, int data){
    if(s->top-s->base>=s->StackSize){
        s->base=(int *)realloc(s->base,(INCREMENT+s->StackSize)*LEN);
        s->top=s->base+s->StackSize;
        s->StackSize=s->StackSize+INCREMENT;
    }
    *(s->top)=data;
    s->top++;
}

int pop(struct Stack *s){
    int data;
    if(s->top==s->base){
        return 0;
    }
    data=*--(s->top); 
    return data;
}

int main(){
    struct Stack *s;
    s=(struct Stack *)malloc(LEN);
    s=Stackinit(s);
    push(s,5);
    push(s,4);
    push(s,3);
    push(s,2);
    push(s,1);
    printf("%d\n",pop(s));
    printf("%d\n",pop(s));
    printf("%d\n",pop(s));
    printf("%d\n",pop(s));
    printf("%d\n",pop(s));
}

输出
1
2
3
4
5

我们明明是5 4 3 2 1输入的，但确实1 2 3 4 5输出，证明确实是从栈的顶端取得的数据。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。