数据结构之‘栈’

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);
}

原文地址：https://blog.csdn.net/2402_83250773/article/details/142329118

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！