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

C++ 栈(stack)

栈的基本介绍

CPP API: stack

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

• 定义：stack <typedef> stack_name ;

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

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

#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) {
				// 小于等于，直接push
				if (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;
        // 判断栈中是否包含这个元素，如果有就不可以push
        unordered_set<char> inStack;

        for (auto c : s)
        {
            strCount[c]++;
        }
        // 单调栈，保持从栈底往上升序（非完全）
        stack<char> strStack;
        for (auto c : s)
        {
            // 当前字符剩余个数减1
            strCount[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;
    }
};