http://www.nowcoder.com/questionTerminal/4c776177d2c04c2494f2555c9fcc1e49 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
题目解读：实现一个支持push, pop, top, min的栈。
这题传统解决就是双栈 或者单栈但每个元素为{值,当前旧值}，但这种方案需要双倍空间 本人另辟蹊径，使用转义符思路，在单栈中，通过转义符存入额外控制数据，空间复杂度约等于O(N)，每个新的最小值，需要3倍空间进行存储，考虑到一般概率较低所以约等于无。 本方案优点是：数据结构很容易存储进文件，并且是顺序写入。双栈方案是无法顺序写入文件的。 首先该支持Min栈的数据结构由内栈、外栈嵌套而成， 内栈支持插入控制符，每个内栈元素为一个int或两个int。 外栈用1个内栈元素存储非min元素，或3个内栈元素存储新min元素。 我估摸着我可能是全网唯一用这个思路解的
class SpecialStack //支持转义符的栈，支持在一个数组中，插入普通值或控制符，并且读取时可以区分 { public: enum { SpecialMask = 0xFFFFFF00, SpecialFlag = 0x88888800 }; void push(int value) { raw_values.push_back(value); if ((value & SpecialMask) == SpecialFlag) //如果值恰好属于特殊字，那么在随后插入一个转义符 raw_values.push_back(SpecialFlag); } void push_code(int8_t control) { raw_values.push_back(SpecialFlag | (int)control); } struct Ret { int value; int8_t control; int8_t size; }; Ret peek(int pos) const { int v = raw_values[pos]; if ((v & SpecialMask) == SpecialFlag) { if ((v & 0xFF) == 0) return { raw_values[pos - 1], 0, 2}; else return { 0, int8_t(v & 0xFF), 1}; } else return { v, 0, 1}; } std::pair<int, int8_t> pop() { Ret ret = peek(raw_values.size() - 1); raw_values.resize(raw_values.size() - ret.size); return { ret.value, ret.control}; } bool empty() const { return raw_values.empty();} std::vector<int> raw_values; }; class Solution { enum { NewMin = 1}; public: void push(int value) { if (value < m_min || values.empty()) { //对于最小值，插入:旧min，新min，特殊控制符NewMin values.push(m_min); values.push(value); values.push_code(NewMin); m_min = value; } else { values.push(value); } } void pop() { std::pair<int, int8_t> item = values.pop(); if (item.second == NewMin) //弹出时，如果是“特殊控制符NewMin”，再弹出较新min，旧min，并将旧min赋值给当前m_min { values.pop(); m_min = values.pop().first; } } int top() const { auto item = values.peek(values.raw_values.size() - 1); if (item.control == NewMin) //读取栈顶，如果是特殊控制符NewMin，那么读取前一个值 return values.peek(values.raw_values.size() - 1 - item.size).value; else return item.value; } int min() const { return m_min; } private: SpecialStack values; int m_min = 0; };