### ACM的基础知识详解
ACM（Association for Computing Machinery）竞赛是一种国际性的计算机程序设计比赛，旨在考验参赛者在限定时间内解决复杂问题的能力。对于初学者而言，了解ACM的基础知识至关重要，这不仅包括基本的数据结构与算法，还包括如何有效地利用标准模板库（STL）中的各种容器。
#### 常用STL容器
STL提供了多种高效的容器，用于存储、操作数据。本文主要介绍三种常用的STL容器：栈(stack)、队列(queue)以及优先队列(priority_queue)。
##### 栈(Stack)
**定义**：栈是一种特殊的线性表，其插入和删除操作都仅发生在表的一端，这一端被称为栈顶(top)。栈的特点是“后进先出”(LIFO)，即最后进入栈的元素将最先被删除。
**使用方法**：
1. **参考网站**：
- 英文：`http://msdn.microsoft.com/en-us/library/h9sh48d5(VS.80).aspx`
- 中文：`msdn.microsoft.com/zh-cn/library/vstudio/56fa1zk5(v=vs.110).aspx`
2. **引用头文件**：
```cpp
#include<stack>
#include<iostream>
using namespace std;
```
3. **成员函数**：
- `empty()`：测试栈是否为空。
- `pop()`：从栈顶移除一个元素。
- `push(value)`：将一个元素添加到栈顶。
- `size()`：返回栈中元素的数量。
- `top()`：返回栈顶元素的引用。
**示例代码**：
```cpp
#include<stack>
#include<iostream>
using namespace std;
int main() {
stack<int> s1;
s1.push(10);
s1.push(20);
s1.push(30);
int i;
i = s1.top();
cout << "栈顶元素为：" << i << endl;
s1.pop();
i = s1.top();
cout << "弹出一个元素后，栈顶元素为：" << i << endl;
return 0;
}
```
**输出结果**：
```
栈顶元素为：30
弹出一个元素后，栈顶元素为：20
```
**应用案例**：二叉树的前序遍历
二叉树前序遍历可以通过栈来实现非递归算法。
```cpp
struct Node {
int data;
Node* child[2];
};
void DFS(Node* root) {
stack<Node*> st;
while (!st.empty() || root != nullptr) {
while (root != nullptr) {
cout << root->data << " ";
st.push(root);
root = root->child[0];
}
if (!st.empty()) {
root = st.top();
st.pop();
root = root->child[1];
}
}
}
```
##### 队列(Queue)
**定义**：队列也是一种特殊的线性表，允许在一端进行插入操作，在另一端进行删除操作。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队列的特点是“先进先出”(FIFO)。
**使用方法**：
1. **参考网站**：
- 英文：`http://msdn.microsoft.com/en-us/library/s1b6tszt(VS.80).aspx`
2. **引用头文件**：
```cpp
#include<queue>
#include<iostream>
using namespace std;
```
3. **成员函数**：
- `empty()`：检查队列是否为空。
- `push(value)`：在队尾添加一个元素。
- `pop()`：从队头移除一个元素。
- `front()`：返回队头元素的引用。
- `back()`：返回队尾元素的引用。
**示例代码**：
```cpp
#include<queue>
#include<iostream>
using namespace std;
int main() {
queue<int> q1;
q1.push(10);
q1.push(20);
q1.push(30);
cout << "队头元素为：" << q1.front() << endl;
cout << "队尾元素为：" << q1.back() << endl;
q1.pop();
cout << "移除一个元素后，队头元素为：" << q1.front() << endl;
return 0;
}
```
**输出结果**：
```
队头元素为：10
队尾元素为：30
移除一个元素后，队头元素为：20
```
##### 优先队列(Priority Queue)
**定义**：优先队列是一种特殊的队列，其中每个元素都有一个优先级，每次从队列中取出的是当前具有最高优先级的元素。默认情况下，优先队列按降序排序。
**使用方法**：
1. **引用头文件**：
```cpp
#include<queue>
#include<iostream>
using namespace std;
```
2. **成员函数**：
- `empty()`：测试优先队列是否为空。
- `push(value)`：向优先队列添加一个元素。
- `pop()`：从优先队列中移除一个元素。
- `top()`：返回优先队列中的最大元素。
**示例代码**：
```cpp
#include<queue>
#include<iostream>
using namespace std;
int main() {
priority_queue<int> pq1;
pq1.push(10);
pq1.push(20);
pq1.push(30);
cout << "优先队列的最大元素为：" << pq1.top() << endl;
pq1.pop();
cout << "移除最大元素后，优先队列的最大元素为：" << pq1.top() << endl;
return 0;
}
```
**输出结果**：
```
优先队列的最大元素为：30
移除最大元素后，优先队列的最大元素为：20
```
通过上述介绍，我们可以了解到栈、队列和优先队列的基本概念及其使用方法。这些容器在ACM竞赛中非常常见，熟练掌握它们能够帮助参赛者更高效地解决问题。此外，深入理解这些数据结构的内部实现机制也是提高编程能力的关键。
