[tOC]

栈

• 先进后出只能从栈顶访问和删除的数据结构，栈数据结构可以用于匹配分隔符以及大数相加的操作，可以用向量（数组）和链表的方式实现，其中链表的方式与抽象栈更匹配。在向量和链表形式的栈中，出栈操作的复杂度为O(1)，在向量栈中最坏的入栈复杂度为O(n)，而在链表栈中仍为O(1)。

单调栈

• 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
• 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大
• 数组值相等的时候，下标压在一起
• 一般解决一个数组中，离索引index两边最近的比它大的或小的值

队列

• 一端用于新加元素，一端用于删除元素的数据结构。同样队列也可以使用数组和链表的方式实现。在双向链表的实现中，入队和出队的复杂度为O(1)，单向链表的出队操作复杂度为O(n)。

优先队列

常见问题

迷宫问题

• 迷宫问题通常可以使用栈数据结构解决，将迷宫中的位置墙看做1，通道看做0，整个迷宫看做一个二维数组，从初始点开始，将上下左右可以通过的点坐标依次存入栈Stack，从栈顶取出一个位置作为当前位置，并按上述顺序继续搜索可以通过的点并存入栈中，当栈为空时则没有路径可以走出迷宫，当栈顶为出口时则找到正确路径