作者:一个喜欢猫咪的的程序员
专栏:《数据结构》
喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》
目录
栈的概念和结构:
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
逻辑引导:
选择B和C。
第一题大家可能没有什么疑问,先入后出嘛,刚好跟原来的顺序相反。
第二题:我们来先讲一个A选项,我们可以先让1入栈,然后马上让1出栈,然后再让2 3 4入栈,再依次出栈。这样只有C选项无法实现。
栈的实现(数组栈):
结构:
当我们要实现数组栈的时候,我们跟顺序表的结构体一样,需要一个sz和capapity。因此我们要开辟一个结构体。
StackInit部分:
这种情况是不需要的断言,但我们这种方法不可行!
ps = (ST*)malloc(sizeof(ST));//这里是错的,形参不可以改变实参。
正确写法:
top为0和top为-1的区别:
StackDestory部分:
StackPush 部分:
void StackPush(ST* ps, STDatatype x) { assert(ps); if (ps->capacity == ps->top) { STDatatype* tmp = (STDatatype*)realloc(ps->a,ps->capacity * 2 * sizeof(ps->a)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; }
StackPop部分:
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
StackEmpty部分和StackSize部分:
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
Stack.h文件:
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int STDatatype; typedef struct Stack { STDatatype* a; int capacity; int top; }ST; void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps, STDatatype x); void StackPop(ST* ps); STDatatype StackTop(ST* ps); bool StackEmpty(ST* ps); int StackSize(ST*ps);
Stack.c文件:
#include"Stack.h" void StackInit(ST* ps) { //ps = (ST*)malloc(sizeof(ST));//这里是错的,形参不可以改变实参。 assert(ps); ps->a = (STDatatype*)malloc(sizeof(STDatatype) * 4); if (ps->a == NULL) { perror("Init fail"); exit(-1); } ps->capacity = 4; ps->top = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } void StackPush(ST* ps, STDatatype x) { assert(ps); if (ps->capacity == ps->top) { STDatatype* tmp = (STDatatype*)realloc(ps->a,ps->capacity * 2 * sizeof(ps->a)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDatatype StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } int StackSize(ST* ps) { assert(ps); return ps->top; }
Test.c文件:
#include"Stack.h" void test1() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); StackPop(&st); StackPop(&st); StackPop(&st); StackPop(&st); StackPop(&st); //StackPop(&st); StackDestory(&st); } int main() { test1(); return 0; }