栈(Stack)

概念

栈中可操作的一端更多地称作栈顶（stack top），而另一无法直接操作的盲端则更多地称作栈底（stack bottom）,以后进先出(last-in-first-out, LIFO)为原则。

实现(继承向量接口)

public class Stack{
void push(T e){
insert(size(),e);
}//入栈
T pop(){
return remove(size()-1);
}//出栈
T top(){
return ((*this)[size() - 1]);
}//返回顶端元素值
}

栈操作都是在向量的末端进行操作,即操作的元素没有后继元素,所以上述操作都在常数时间复杂度O(1)内完成,试想若将向量的头端作为栈的顶端进行操作,则上述操作的时间复杂度为O(n),效率远不如之前.

栈的应用