数据结构之‘栈’

1.简介

• 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。
• 进行（数据插入和删除操作）的一端称为栈顶，另一端称为栈底。
• 压栈：（栈的插入操作）叫做 --------进栈/压栈/入栈
• 出栈：（栈的删除操作）叫做---------出栈

2. 栈的初始化和销毁

3. 进栈和出栈

3.1 进栈

进栈时要考虑空间是否足够：

空间足够：有效数据个数<空间大小。
空间不足：有效数据个数=空间大小。

还需要考虑当时capacity是否为0。
如果ps->capacity=ps->top=0,这时给capacity*2也没用。这时需要给它赋值

//进栈
void stackPush(stack* ps, Datatype x);

void stackPush(stack* ps, Datatype x)
{assert(ps); //ps不能为空，空的不能解引用//先判断空间是否足够if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;Datatype* tmparr = (Datatype*)realloc(ps->arr, newcapacity * sizeof(Datatype));if (tmparr==NULL){perror("realloc fail");exit(1);  //非0数均可}ps->arr = tmparr;ps->capacity = newcapacity;}//空间足够，则插入数据ps->arr[ps->top] = x;(ps->top)++;
}

stack st;   //stack是栈的结构，st是栈类型的变量
StackInit(&st);  //将变量名为st的栈的地址传过去
stackPush(&st, 23);
stackPush(&st, 24);
stackPush(&st, 25);
stackPush(&st, 26);

3.2 出栈

1. 出栈也是从栈顶出，最上面的先出去（top）。
2. 需要判断栈是否为空（栈空不可以出数据），即ps->top是否为0

//出栈
void stackPop(stack* ps);

3.3 栈的打印

之前我们判断代码是否正确，可以将其打印出来，栈的打印略有不同。栈不能 随机访问和遍历，只能访问栈顶的那一个元素，所以，只能知道栈顶，然后将其删除，使下一个数据成为栈顶，然后便可以访问。--------->取栈顶元素。

1. 单纯的取栈顶元素

//取栈顶元素(返回的则是栈顶元素，类型是Datatype)
Datatype stackTop(stack* ps);

Datatype stackTop(stack* ps)
{assert(ps);assert(!stackEmpty(ps));return ps->arr[(ps->top) - 1];
}

2. 取出来+删除

void test01()
{stack st;   //stack是栈的结构，st是栈类型的变量//进栈StackInit(&st);  //将变量名为st的栈的地址传过去stackPush(&st, 23);stackPush(&st, 24);stackPush(&st, 25);stackPush(&st, 26);//打印+出栈while (!stackEmpty){Datatype print=stackTop(&st);printf("%d ", print);//出栈stackPop(&st);}//销毁StackDestroy(&st);
}