基本概念
堆栈（stack）是一种特殊的线性数据结构，只能够在一端（即栈顶）进行，采用后进先出原则（LIFO, Last In First Out），基本操作有加入数据（push）和输出数据（pop）两种运算。
原型声明
除了构造和析构函数外，根据定义，最主要的即为Pop和Push两个操作，在此基础上加上返回栈顶元素（Top），判断是否为空栈（IsEmpty）和将栈置空（MakeEmpty）三个功能。 在本文中，每个栈都有一个表头，不记录数据，只用来记录栈顶位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Node
{
int dat;
Node *Next;
};
class Stack {
public:
Stack();
Stack(int i);
int IsEmpty();
void MakeEmpty();
void Push(int x);
int Top();
void Pop();
~Stack();
private:
Node *node;
};
压入数据 Push
整体思路为新申请一个节点，用于存储新数据，使其指向原栈顶元素，再将表头指向新元素即可。
1
2
3
4
5
6
7
void Stack::Push(int x)
{
Node *tmp = new Node;
tmp->dat = x;
tmp->Next = node->Next;
node->Next = tmp;
}
弹出数据 Pop
只需将栈顶元素删除，然后将表头指向原栈顶元素所指向的结点即可。在这要注意用一个新变量先记录栈顶元素否则会导致无法释放空间。而且要防止空栈的情况发生。
1
2
3
4
5
6
7
8
void Stack::Pop()
{
if (!this->IsEmpty()) {
Node *tmp = node->Next;
node->Next = node->Next->Next;
delete tmp;
}
}
返回栈顶元素 Top
返回表头所指结点数据即可。这里INF为一个不可能被使用到的数据，以用来提示空栈的情况。
1
2
3
4
5
6
7
8
int Stack::Top()
{
if(!this->IsEmpty()){
return node->Next->dat;
}else{
return INF;
}
}
判断是否为空栈 IsEmpty
判断表头是否为空指针即可。
1
2
3
4
5
6
7
8
int Stack::IsEmpty()
{
if (node->Next == nullptr) {
return 1;
}else{
return 0;
}
}
将栈置空 MakeEmpty
将元素不断弹出直至栈为空即可。
1
2
3
4
void Stack::MakeEmpty()
{
while (!this->IsEmpty()) this->Pop();
}