链式栈(LinkedStack)
template<class T>
class LinkedStack {
struct Node {
T data;
Node* next;
Node(const T& x,Node* p=nullptr){ data=x; next=p; }
};
Node* topPointer;
int n;
public:
LinkedStack(){ topPointer=nullptr; n=0; }
~LinkedStack(){ clear(); }
bool empty() const { return topPointer==nullptr; }
int size() const { return n; }
void push(const T& x){
topPointer=new Node(x,topPointer);
n++;
}
bool pop(){
if(empty()) return false;
Node* q=topPointer;
topPointer=topPointer->next;
delete q;
n--;
return true;
}
T& top(){
if(empty()) throw underflow_error("LinkedStack::top on empty stack");
return topPointer->data;
}
void clear(){
while(!empty()) pop();
}
};
工程细节
- 栈顶指针就是链首指针;入栈头插,出栈删首,两者均为
O(1)。
- 入栈时新结点先指向旧栈顶,再更新
topPointer。出栈先保存旧栈顶、更新指针,再释放旧结点。
- 空栈不能读取
top();pop() 在空栈返回 false。清空反复出栈,最后 topPointer == nullptr 且 n == 0。
跳转
下一个:链式队列
上一个:双向循环链表