顺序栈(ArrayStack)
template<class T, int MAXN>
class ArrayStack {
T data[MAXN];
int topIndex;
public:
ArrayStack(): topIndex(-1) {}
bool empty() const { return topIndex==-1; }
bool full() const { return topIndex==MAXN-1; }
int size() const { return topIndex+1; }
bool push(const T& x){
if(full()) return false;
data[++topIndex]=x;
return true;
}
bool pop(){
if(empty()) return false;
topIndex--;
return true;
}
T& top(){
if(empty()) throw underflow_error("ArrayStack::top on empty stack");
return data[topIndex];
}
void clear(){ topIndex=-1; }
};
工程细节
topIndex 表示栈顶元素下标,空栈为 -1,元素数为 topIndex + 1;不要与“栈顶指针指向下一空位”的约定混用。
- 入栈先递增下标,再写入元素;出栈只递减下标。空栈
pop() 和满栈 push() 返回 false。
- 空栈读取
top() 抛出 underflow_error;clear() 将 topIndex 恢复为 -1。
跳转
下一个:普通顺序队列
上一个:动长数组