栈

 代码          含义
 s.push(ele)   元素ele入栈增加元素
 s.pop()       弹出栈顶元素
 s.top()       s.top() == 栈顶元素
 s.empty()     判断栈内是否为空，空为真
 s.size()      返回栈内元素的个数

数组模拟栈的遍历

1
2
3
4
5
6
7
8
9
10

// 栈 从左至右为栈底到栈顶
int s[100];
// p 代表栈顶指针,初始栈内无元素，p为-1
int p = -1;
for(int i = 0; i <= 11; ++i) {
	//入栈
	s[++p] = i;
}
// 出栈
int top_element = s[p--];

栈的应用

题目大意：有 n 个人从左到右排成一队，全部人向右看，每个人会被比自己高的人挡住，求出每个人是被哪个位置的人挡到。如果没有被挡住就输出 0。

思考：因为向右看，所以最右一个人一定是输出 0，从右向左考虑，如果一个人 a，a 的左边人如果比 a 高，那么 a 就失去挡住别人的能力，如果左边人比 a 矮，那么两人都可能有挡住别人的能力。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 栈s存答案， 栈x存有能力挡住别人的人
stack<int> s, x;
//倒序遍历（向右看
for (int i = n; i >= 1; i--)
{
  //a左边的人如果高，a就失去挡住别人的能力，出栈！
  while (!x.empty() && a[i] >= a[x.top()]) x.pop();
  //全部弹出，栈内没有比他高的，则存入0
  if (x.empty()) s.push(0);
  //此时就是a左边的人矮，则被a挡住，将a的位置存入答案栈a
  else s.push(x.top());
  //入栈
  x.push(i);
}

例题 1 例题 2

队列

 代码          含义
 q.push(ele)   队列尾部进入元素ele
 q.pop()       弹出队首元素
 q.front()     q.front() == 队首元素
 q.back()      q.back() == 队尾元素
 q.empty()     判断队列是否为空，空为真
 q.size()      返回队列元素的个数

队列应用

问题大意：生长问题 或者 保质期问题 这类问题难点在于随着时间推移，队列所维护的所有元素会发生题目规律变化（可能是多久后过期，多久后长度增加量）

思路一:

将维护的变量设置为结构体一起维护，常规

思路二：

定义变量 delta，将所有变化对 delta 进行，再每次对队列元素操作时，先进行对应的 delta 处理，新元素存入时，扣除当前时间 delta 变化再存入（就是把新元素等价于旧元素经过时间后的变化）

例题

双端队列

 代码                               含义
 push_back(ele) / push_front(ele)   把ele插入队尾 / 队首
 back() / front()                   == 队尾 / 队首元素
 pop_back() / pop_front()           删除队尾 / 队首元素
 erase(iterator it)                 删除迭代器所指的元素
 erase(ita, itb)                    删除迭代器a，b范围内元素（左闭右开
 empty()
 size()
 clear()                            清空deque