那么我这里再列出四个关于栈的问题，大家可以思考一下。以下是以C++为例，使用其他编程语言的同学也对应思考一下，自己使用的编程语言里栈和队列是什么样的。
- C++中stack 是容器么？
- 我们使用的stack是属于哪个版本的STL？
- 我们使用的STL中stack是如何实现的？
- stack 提供迭代器来遍历stack空间么？
相信这四个问题并不那么好回答， 因为一些同学使用数据结构会停留在非常表面上的应用，稍稍往深一问，就会有好像懂，好像也不懂的感觉。
有的同学可能仅仅知道有栈和队列这么个数据结构，却不知道底层实现，也不清楚所使用栈和队列和STL是什么关系。
所以这里我再给大家扫一遍基础知识，
首先大家要知道 栈和队列是STL（C++标准库）里面的两个数据结构。
C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。
那么来介绍一下，三个最为普遍的STL版本：
-
HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
-
P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
-
SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。
接下来介绍的栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。
来说一说栈，栈先进后出，
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。
那么问题来了，STL 中栈是用什么容器实现的？
从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。
deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
刚刚讲过栈的特性，对应的队列的情况是一样的。
队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。
队列
是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）
c++队列queue模板类的定义在<queue>头文件中,queue 模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。
C++队列Queue类成员函数有:
back() 返回最后一个元素
empty() 如果队列空则返回真
front() 返回第一个元素
pop() 删除第一个元素
push() 在末尾加入一个元素
size() 返回队列中元素的个数
优先队列：C++优先队列类似队列，但是在这个数据结构中的元素按照一定顺序排列。
成员函数有：
1.empty() 如果优先队列为空，则返回真
2.pop() 删除第一个元素
3.push() 加入一个元素
4.size() 返回优先队列中拥有的元素的个数
5.top() 返回优先队列中有最高优先级的元素
232:用栈实现队列
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
if(stOut.empty())
{
while(!stIn.empty())
{
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
225：用队列实现栈
class MyStack {
public:
queue<int>que1;
queue<int>que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
size--;
while(size--)
{
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
que1 = que2; // 再将que2赋值给que1
while (!que2.empty()) { // 清空que2
que2.pop();
}
return result;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};20：有效的括号
class Solution {
public:
bool isValid(string s) {
if(s.size()%2 != 0){return false;}
stack<char>st;
for(int i = 0;i < s.size();i++)
{
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
else if(st.empty() || s[i] != st.top()){return false;}
else st.pop();
}
return st.empty();
}
};1047:删除字符串中的所有相邻重复项
class Solution {
public:
string removeDuplicates(string s) {
stack<char>st;
for (char s : s) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string s2 = "";
while(!st.empty())
{
s2 += st.top();
st.pop();
}
reverse (s2.begin(), s2.end());
return s2;
}
};150:逆波兰表达式求值
stoll（）：
此函数将在函数调用中作为参数提供的字符串转换为long long int。它解析str并将其内容解释为指定基数的整数，并将其作为long long int类型的值返回。文章来源：https://www.toymoban.com/news/detail-428571.html
347：前k个高频元素文章来源地址https://www.toymoban.com/news/detail-428571.html
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 要统计元素出现频率
unordered_map<int, int> map; // map<nums[i],对应出现的次数>
for (int i = 0; i < nums.size(); i++) {
map[nums[i]]++;
}
// 对频率排序
// 定义一个小顶堆，大小为k
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 用固定大小为k的小顶堆，扫面所有频率的数值
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();
}
}
// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};到了这里，关于算法训练day4：栈与队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
