这篇文章记录了我在edX上Data Structures and Algorithms学习栈的笔记.
栈(Stack)
1.实现
(1)可直接派生(derive)向量(Vector)/列表(List)
template <typename T> class Stack: public Vector<T>{
public: //size(),empty()以及其它开放接口均可直接沿用
void push(T const & e) {insert(size(),e);} //入栈
T pop() {return remove(size()-1);} //出栈
T & top() {return (*this)[size()-1];} //取顶
};//所有都是O(1)
典型应用场合
1.逆序输出(conversion): 输出次序与处理过程点到;递归深度和输出长度不易预知
2.递归嵌套(stack permutation+parenthesis): 具有自相似性的问题可递归描述,但分支位置和嵌套深度不固定
3.延迟缓冲(evaluation): 线性扫描算法模式中, 在预读足够长之后,方能确定可处理的前缀(prefix)
4.栈式计算(RPN:Reverse Polish notation):基于栈结构的特定计算模式
栈应用:进制转换
- 逆序输出(conversion): 输出次序与处理过程点到;递归深度和输出长度不易预知
void convert(Stack<char> & S, __int64 n,int base){
static char digit[] = //新进制下的数位符号,可视base取值范围适当扩充
{'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
while(n>0){
S.push(digit[n%base]);
n /= base;
}
}
main(){
Stack<char> S;
convert(S,n,base);
while(!S.empty()) printf("%c",S.pop());
}