栈的应用——进制转换

　　前几篇英文写作，虽然充分表现了初二水平，但作为英渣已经尽力了。接下来换回中文，来写一些有趣的事——栈的典型应用。对比向量与列表，栈的外部接口更加简化和紧凑（不是摸鱼）。因此相较于部分接口的实现，我们更关注栈ＬＩＦＯ特性在实际应用中的发挥。

　　栈所擅长解决的典型问题，往往具有以下共同特征： 　　

• 解答以线性序列给出
• 该序列依逆序计算输出
• 输入输出规模未定，难以事先确定容器大小

应用一

任意给定十进制数，将其转换为进制的表示。

设
若
则可得关系式


因此可以首先计算出最低位，然后压入栈中，成为栈底，同时计算。
重复上述过程，直至被压入栈中，成为栈顶。
输出时，后进先出，最高位向下依次出栈，排列为的形式，符合要求。
出于效率考虑，将迭代改为递归：

void convert ( stack<char>& S, _int64 n, int base)   //转换为base进制
{
    static char digit[]  //新进制下的数位符号，可视需求扩充
    = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
    while(0<n)
    {
        S.push( digit[n%base] );  //入栈
        n/=base;                  //更新n
    }
}
//输出  
while( !S.empty() ) cout<<S.pop();  //得益于类的继承，直接沿用vector的接口