栈:链表实现
结构描述
#include <iostream>
#include <cstdlib>
typedef int DataType;
using namespace std;
typedef struct Node {
DataType A;
struct Node * Next;
}Node;
class StackLinked {
private:
Node * Top;
public:
void Push(DataType X);
void Pop();
DataType GetTop();
void MakeEmpty();
Node * BuyNode(DataType X);
void Init();
bool IsEmpty();
};
初始化
把 Top
置为空
void StackLinked::Init() {
Top = nullptr;
}
判空
若 Top
为空指针,则栈为空
bool StackLinked::IsEmpty() {
return Top == nullptr;
}
分配空间
把分配空间封装成一个一个一个方法
Node * StackLinked::BuyNode(DataType X) {
Node * NewNode = (Node *)malloc(sizeof(Node));
if (NewNode == nullptr) {
cout << "Malloc Failed!" << endl;
exit(-1);
}
NewNode->A = X;
NewNode->Next = nullptr;
return NewNode;
}
入栈
使用头插法入栈,无特殊情况
分配一个新的节点 NewNode
,并将 NewNode
指向 Top
,然后再将 Top
指向 NewNode
,对栈为空和非空都适用。
void StackLinked::Push(DataType X) {
Node * NewNode = BuyNode(X);
NewNode->Next = Top;
Top = NewNode;
}
出栈
- 栈空:报错
- 非空:头删法出栈
创建一个临时指针 Tmp
,用于保存当前 Top
指向的节点,把 Top
向后移动一位,即 Top = Top->Next
,然后把 Tmp
释放。
void StackLinked::Pop() {
if (IsEmpty()) {
cout << "Stack Is Empty!" << endl;
exit(-1);
}
Node * Tmp = Top;
Top = Top->Next;
free(Tmp);
Tmp = nullptr;
}
获取栈顶元素
- 栈空:报错
- 非空:返回
Top
指向的节点的元素
DataType StackLinked::GetTop() {
if (IsEmpty()) {
cout << "Stack Is Empty!" << endl;
exit(-1);
}
return Top->A;
}
摧毁栈
- 栈空:报错
- 非空:一直出栈,直至栈空
void StackLinked::MakeEmpty() {
if (IsEmpty()) {
cout << "Stack Is Empty!" << endl;
exit(-1);
}
while (!IsEmpty()) {
Pop();
}
}
标签:Node,实现,Top,链表,DataType,StackLinked,NewNode,void
From: https://www.cnblogs.com/codels/p/18309486