目录
栈
栈的复杂度
空间复杂度O(1)
时间复杂度O(1)
栈的应用
1、栈在函数调用中的应用;
2、栈在求表达式的值的应用:
栈的实现
栈
后进先出,先进后出,只允许在一端插入和删除
从功能上,数组和链表可以代替栈。特定的数据结构是对特定场景的抽象,而且数组或链表暴露接口过多,自然容易出错。
符合先进后出特性的数据,可以使用栈
栈的形式
- 1、顺序栈 数组实现
- 2、链式栈 链表实现
栈的复杂度
空间复杂度O(1)
出栈和入栈只需要两个临时变量存储空间,空间复杂度O(1),存n个数据,不能说时间复杂度O(n),因为n个空间是必须的。出来原本的空间,算法还需要额外的存储空间
时间复杂度O(1)
时间复杂度 O(1),插入在满的时候会退化O(n),平摊也是O(1)
动态扩容的栈
栈满,申请更大数组,将原来数据搬到新数组中。
栈的应用
1、栈在函数调用中的应用;
为什么函数调用要用“栈”来保存临时变量呢?用其他数据结构不行吗? 其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构来实现,是最顺理成章的选择。
从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现这个,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。
2、栈在求表达式的值的应用:
编译器通过两个栈来实现。一个存值,一个存操作数。
比较运算符栈顶元素的优先级,高则将当前运算符压如栈;低或者相同,从运算符栈中取出栈顶运算符。从操作数中取出两个数,进行计算,计算后再将结果压入操作数栈,继续比较。
栈的实现
typedef struct _array_stack
{int size;int pos;int *array;
}arrayStack; arrayStack *arrayStack_create(int size)
{arrayStack *pStack = NULL;pStack = (arrayStack *)malloc(sizeof(arrayStack));if(pStack == NULL)return NULL;pStack->size = size;pStack->pos = -1;pStack->array = (int *)malloc(sizeof(int)*size);if(pStack->array ==NULL){free(pStack);return NULL;}return pStack;
}int arrayStack_pop(arrayStack *pStack)
{int data = 0;if(arrayStack_is_empty(pStack)){return -1;}data = pStack->array[pStack->pos];pStack->pos--;return data;
}
int arrayStack_push(arrayStack *pStack,int data)
{if(arrayStack_is_full(pStack))return;pStack->pos++;pStack->array[pStack->pos] = data;return 0;
}