堆栈、队列、单调栈、单调队列1

Stack和Queue——栈和队列

• 栈的定义:栈是限定仅在表头进行插入和删除操作的线性表(先进后出)
• 队列的定义:队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。(先进先出)
  stack常用函数:
• push()——向栈顶压入元素
• pop()——弹出栈顶元素
• top()——访问栈顶元素
  queue常用函数:
• front()——访问队首元素
• back()——访问队尾元素
• push()——向队尾插入元素
• pop()——弹出队首元素

出栈顺序

题目描述:
有n个人，按照1，2，3...n的顺序依次进栈，判读能否以题目所给序列出栈。(n <= 100000)
eg:

• 4 3 2 1
• 1 2 3 4
• 1 3 2 4
• 1 4 2 3

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int n;
stack<int> stk;
int main() {
	ios;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int j = 1;
	for (int i = 1; i <= n; i++) {
		stk.push(i);
		while (!stk.empty() && a[j] == stk.top()) {
			stk.pop();
			j++;
		}
	}

	if (!stk.empty()) cout << "No";
	else cout << "Yes";


	return 0;
}

栈和排序

思路:
如果栈顶元素比后面没入栈的元素都大，那么它就应该出栈

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int a[N], maxn[N];	//maxn数组预处理后缀最大值
int n;
stack<int> stk;
int main() {
	ios;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	//预处理
	for (int i = n; i >= 1; i--) {
		maxn[i] = max(a[i], maxn[i + 1]);
	}

	for (int i = 1; i <= n; i++) {
		stk.push(a[i]);
		while (!stk.empty() && stk.top() > maxn[i + 1]) {	//还没进栈的元素是否没有比栈顶元素大的
			printf("%d ", stk.top());
			stk.pop();
		}
	}
	
	//如果栈内还有元素，就直接输出
	while (!stk.empty()) {
		printf("%d ", stk.top());
		stk.pop();
	}
	return 0;
}

好串

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
typedef long long LL;

string s;
stack<int> stk;
int main() {
	ios;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'a') {
			stk.push('a');
		} else {
			if (stk.empty()) {
				cout << "Bad" << endl;
				return 0;
			} else {
				stk.pop();
			}
		}
	}

	if (stk.empty()) cout << "Good";
	else cout << "Bad";
	return 0;
}