[Acwing] 算法基础课总结二 数据结构

1. 单链表

1. 实现起来和 v e c t o r vector vector,这里主要是为了后面链式前向星打基础,通过 i d x idx idx进行添加值

2.双链表

1. 暂时不碰,感觉没有多大的意义

3. 栈

1. 模拟栈,维护一个栈顶指针, t o p top top对于每次操作对应 + − +- +−操作,手写栈方便了后面单调栈的讲解
2. 表达式求值,利用运算优先级表 , 对于每次操作考虑入栈,之后直接操作,属于大模拟

4. 队列

1. 模拟队列,不做过多解释

5.单调栈

1. 单调栈,可以维护左边第一个比他小的数,我们可以使用栈维护一个只比当前 i i i小的栈,对于当前元素的每次入栈我们都把比他大的数踢出栈

for(int i=1;i>a[i];
		while(!stk.empty() && stk.top() >= a[i])
		stk.pop();
		
		if(stk.empty())cout