1.栈
1.1栈的概念及结构
1.1.1概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（LastInFirstOut）的则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.1.2结构
数组栈
链式栈
如果用尾做栈顶，尾插尾删，要设计成双向链表，否则删除数据效率低
如果用头做栈顶，头插头删，就可以设计成单链表
两种都可以，非要选一种，数组栈结构稍微好一点。
1.2接口函数
//要改变结构体的内容 //传结构体的指针 void StackInit(ST* ps); void StackDestory(ST* ps); void StackPush(ST* ps,STDataType x); void StackPop(ST* ps); STDataType StackTop(ST* ps); //取栈顶的数据 int StackSize(ST* ps); //栈中元素个数 bool StackEmpty(ST* ps); //判断栈是否为空1.3详细代码
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity; }ST; void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; //初始化时，top给的是0， // 意味着top指向栈顶数据的下一个 // ps->top=-1; //初始化时，top给的是 - 1， // 意味着top指向栈顶数据 ps->capacity = 0; } void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); //栈不为空才能删 ps->top--; } STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); //栈不为空才能取栈顶元素 return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); /* if (ps->top == 0) return true; else return false; */ return ps->top == 0; } void TestStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); //遍历栈中的数据 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestory(&st); } int main() { TestStack(); return 0; }
