写在前面

学打代码之前先学会做个人,没事不要瞎写 i++++ii+=1 之类的阴间玩意。

堆叠的定义

  • 是一种受限的线性表,只能在顶顶插入和删除
  • 堆叠是后进先出的
  • 对于一个堆叠的操作有创建、删除、增删查、判断是否是空

Sequence Stack

用顺序存储的方式来创建一个堆叠
一个顺序堆叠的结构是

#define maxSize 114514
typedef struct {
    int value[maxSize];
    int top;
} seqStack

声明一个 sequence stack

void stack() {
    seqStack stackName;
}

只要执行了 seqStack stackName ,电脑就会马上自动分配内存。
能就尽量不要再malloc()了,能自动的东西为什么不让他自动?

stack::init

初始化栈顶指针

void initStack(seqStack &stackName) {
    stackName.top = stackName -1;
}

为什么需要把stackName.top-1?
因为init一个stack之后,top默认是0。然而,因为这个stack是刚刚init来的,里面还没有任何数据,也就是说0的位置也还没有数据。所以显然这时候堆叠顶高度为0是不合理的。因此需要把堆叠顶高度设置为-1

stack::isEmpty

由于初始化时候stackName.top应为-1,所以判断一个堆叠是不是空的只要看看这个堆叠的高度是不是-1就OK了。

bool stackIsEmpty(seqStack stackName) {
    if(stackName.top == -1) {
        return true;
    }
    else {
        return false;
    }
}

⚠ 注意!注意!注意!
我这里写的所有stackName.top都是指堆叠中最顶顶的有有效数据的那一层,而不是指可以插入数据的那一层
所以做题的时候必须要注意。
如果做题的时候题目出的是后者,下面所有操作都要做相应的修改。毕竟电视节目有好多种,但是不是每一种都适合小朋友看,不要背题好吗 :-)

stack::push

往上面push要先康康这个stack是不是已经满了,然后才能往里面塞东西。
比如说上面已经有define maxSize 114514,那么就看看这个堆叠目前的高度是不是114513(maxSize -1)。

bool push(seqStack &stackName, int value) {
    if(stackName.top == maxSize -1) {
        return false;
    }
    stackName.top = stackName.top + 1;
    stackName.value[stackName.top] = value;
    return true;
}

stack::pop

先看看这个堆叠是不是空的,毕竟你不能删除一个不存在东西。
因为一般pop的时候要返回被pop的数据,所以 function type 跟翻stackname.value设置成int

int pop(seqStack &stackName) {
    if(stackName.top == -1) {
        return false;
    }
    stackName.top = stackName.top -1;
    return stackName.value[stackName.top +1];
}

这样玩的话只是形式上删除了数据,实际上数据没有真的从内存里删掉。

stack::top

存取堆叠顶部的数据,和pop的区别是,存取堆叠顶的行为不会使stackName.top-1。
而且一样地,要先看看这个堆叠是不是空的,毕竟你不能存取一个不存在的东西((

int top(seqStack stackName) {
    if(stackName.top == -1) {
        return false;
    }
    return stackName.value[stackName.top];
}

Linkde Stack

这个玩意儿就相当于一个只能操作第一个元素的 Linked list.
它的结构是

typedef struce linkedNode {
    int value;
    struct linkedNode* next;
}* linkedStack;

标签: none