【C++11数据结构与算法】C++ 栈

C++ 栈(stack)

栈的基本介绍

CPP API: stack

• 一种先进后出（FILO）的数据结构

• 定义：stack <typedef> stack_name ;

• 我们在初始化一个stack时，其中的类型也可以为标准库类型以及自定义类型，如果想创建一个包含多元素的类型应该如下定义：

  // 括号中所用的就是
  stack<pair<TreeNode*, int>> treeStack;
  

函数	描述
(constructor)	该函数用于构造堆栈容器。
empty	该函数用于测试堆栈是否为空。如果堆栈为空，则该函数返回true，否则返回false。
size	该函数返回堆栈容器的大小，该大小是堆栈中存储的元素数量的度量。
top	该函数用于访问堆栈的顶部元素。该元素起着非常重要的作用，因为所有插入和删除操作都是在顶部元素上执行的。
push	该函数用于在堆栈顶部插入新元素。
pop	该函数用于删除元素，堆栈中的元素从顶部删除。
emplace	该函数用于在当前顶部元素上方的堆栈中插入新元素。
swap	该函数用于交换引用的两个容器的内容。
relational operators	非成员函数指定堆栈所需的关系运算符。
uses allocator	顾名思义，非成员函数将分配器用于堆栈。

#include <iostream>
#include <stack>
using namespace std;
void newstack(stack <int> ss)
{stack <int> sg = ss;while (!sg.empty()){cout << '\t' << sg.top();sg.pop();}cout << '\n';
}
int main ()
{stack <int> newst;newst.push(55);newst.push(44);newst.push(33);newst.push(22);newst.push(11);cout << "最新的堆栈是 : ";newstack(newst);cout << "\n newst.size() : " << newst.size();cout << "\n newst.top() : " << newst.top();cout << "\n newst.pop() : ";newst.pop();newstack(newst); return 0;
}

关于push()和emplace()：

• push()函数接受一个参数，该参数是要添加到栈顶的元素的副本。

• 当调用push()函数时，参数会被复制到栈中，即使元素是通过移动构造函数构造的也会发生复制。

• emplace()函数接受的参数是用于构造栈顶元素的参数列表。

• 当调用emplace()函数时，参数会被直接传递给栈顶元素的构造函数，避免了额外的复制操作。因此，emplace()通常比push()更高效。

• 因此主要区别在于push()接受的是元素的值，而emplace()接受的是元素构造函数的参数列表。emplace()通常更灵活和高效，特别是当元素是通过移动构造函数构造时。

栈的算法运用

单调栈

栈内排序通常满足“单调递增”、“单调递减”，即栈中元素具备“单调性”

实战题

LC例题：321. 拼接最大数

在这个题目中，我们寻找数组的最大子串时，运用了单调栈的特性。但并非完全单调，以下，仅提供寻找最大子串func部分：

注意：这里的最大子串，指的是数组截选出来的子数组中元素相对位置不改变

vector<int> MaxSubNums(vector<int>& nums, int n){// 如果为空，不用遍历if (n == 0) {return {};}stack<int> resStack;int pos = 0;while (pos < nums.size()) {// 余下+当前大小 > 目标大小if ((resStack.size() + nums.size() - pos) == n) break;// 如果栈为空if (resStack.empty()) {resStack.push(nums[pos]);pos++;continue;}// 如果栈满了 且大于栈顶if (resStack.size() == n) {if (nums[pos] > resStack.top()) {resStack.pop();continue;}else {pos++;}}if (resStack.size() < n) {// 小于等于，直接pushif (nums[pos] <= resStack.top()) {resStack.push(nums[pos]);pos++;}else {resStack.pop();}}}while (resStack.size() < n && pos < nums.size()) {resStack.push(nums[pos]);pos++;}vector<int> result;while (!resStack.empty()) {result.push_back(resStack.top());resStack.pop();}std::reverse(result.begin(), result.end());return result;}

LC例题：316. 去除重复字母

题目：给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

解法：因为要使结果为字典序最小，我们利用单调栈性质，使其从底至上为升序（非完全）

我们需要一个map（strCount）用于记录余下字符串中，某字符剩余多少

还需要一个set用于记录栈中已存在哪些元素

遍历字符串，入栈规则：

• 首先：strCount[cur]–

1、若当前字符cur已在栈中，略过，

2、若当前字符cur未在栈中：

1. cur > stack.top() || stack.empty() ，跳到第3步。
2. cur < stack.top()
   1. 如果栈顶元素之后还会出现，弹出
   2. 循环上述操作，直到 栈空 或者 cur > stack.top() 或者栈顶元素在之后不再出现，结束循环
3. 入栈，并在set中记录

遍历完字符串后，栈底到栈顶的元素拼起来就是最终答案。

class Solution
{
public:string removeDuplicateLetters(string s){// 判断该字符余下还有多少个unordered_map<char, int> strCount;// 判断栈中是否包含这个元素，如果有就不可以pushunordered_set<char> inStack;for (auto c : s){strCount[c]++;}// 单调栈，保持从栈底往上升序（非完全）stack<char> strStack;for (auto c : s){// 当前字符剩余个数减1strCount[c]--;// 栈中已有该元素，遍历下一个if (inStack.count(c) != 0)continue;// 如果当前栈不为空 且  当前元素大于栈顶元素，且栈顶元素在剩余字符中还会出现while (!strStack.empty() && c < strStack.top() && strCount[strStack.top()] > 0){inStack.erase(strStack.top());strStack.pop();}// 入栈strStack.push(c);// 记录该元素已经在栈中出现过inStack.insert(c);}string ans = "";while (!strStack.empty()){ans = strStack.top() + ans;strStack.pop();}return ans;}
};