网站建设整体策划,网站建设 51下拉平台,正安网站建设,设计在线设计网站目录
栈
栈的复杂度
空间复杂度O(1)
时间复杂度O(1)
栈的应用
1、栈在函数调用中的应用#xff1b;
2、栈在求表达式的值的应用#xff1a;
栈的实现 栈 后进先出#xff0c;先进后出#xff0c;只允许在一端插入和删除
从功能上#xff0c;数组和链表可以代替栈…目录
栈
栈的复杂度
空间复杂度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;
}
