C++学习笔记（33）

三十五、栈
示例：
#include <iostream>
using namespace std;
typedef int ElemType; // 自定义链栈的数据元素为整数。
struct SNode // 链栈的结点。
{
ElemType data; // 存放结点的数据元素。
struct SNode* next; // 指向下一个结点的指针。
};
// 初始化链栈，返回值：失败返回 nullptr，成功返回头结点的地址。
SNode* InitStack()
{
SNode* head = new (std::nothrow) SNode; // 分配头结点。
if (head == nullptr) return nullptr; // 内存不足，返回失败。
head->next = nullptr; // 头结点的下一结点暂时不存在，置空。
return head; // 返回头结点。
}
// 销毁链栈。
void DestroyStack(SNode* head)
{
// 销毁链栈是指释放链栈全部的结点，包括头结点。
SNode* tmp;
while (head != nullptr)
{
tmp = head->next; // tmp 保存下一结点的地址。
delete head; // 释放当前结点。
head = tmp; // 指针移动到下一结点。
}
}
// 元素入栈，返回值：false-失败；true-成功。
bool Push(SNode* head, const ElemType& ee)
{
if (head == nullptr) { cout << "链栈不存在。\n"; return false; }
SNode* tmp = new (std::nothrow) SNode; // 分配一个新结点。
if (tmp == nullptr) return false;
tmp->data = ee; // 把元素的值存入新结点。
// 处理 next 指针。
tmp->next = head->next;
head->next = tmp;
return true;
}
// 显示链栈中全部的元素。
void PrintStack(const SNode* head)
{
if (head == nullptr) { cout << "链栈不存在。\n"; return; }
SNode* pp = head->next; // 从第 1 个结点开始。
while (pp != nullptr)
{
cout << pp->data << " "; // 如果元素为结构体，这行代码要修改。
pp = pp->next; // 指针往后移动一个结点。
}
cout << endl;
}
// 求链栈的长度，返回值：>=0-栈 SS 结点的个数。
size_t StackLength(SNode* head)
{
if (head == nullptr) { cout << "链栈不存在。\n"; return 0; }
SNode* pp = head->next; // 头结点不算，从第 1 个结点开始。
size_t length = 0;
while (pp != nullptr) { pp = pp->next; length++; }
return length;
}
// 元素出栈。
bool Pop(SNode* head,ElemType &ee)
{
if (head == nullptr) { cout << "链栈不存在。\n"; return false; }
if (head->next == nullptr) { cout << "链栈为空，没有结点。\n"; return false; }
SNode* pp = head->next; // pp 指向第一个节点。
head->next = head->next->next; // 修改头结点的 next 指针。
ee = pp->data;
delete pp; // 删除第一个节点。
return true;
}
int main()
{
SNode* SS = InitStack(); // 初始化链栈 SS。
cout << "入栈三个元素（1、2、3）。\n";
Push(SS, 1);
Push(SS, 2);
Push(SS, 3);
PrintStack(SS); // 把链栈中全部的元素显示出来。
cout << "链栈的长度：" << StackLength(SS) << endl;
// 元素出栈。
ElemType ee;
Pop(SS,ee);
cout << "出栈的元素的值是：" << ee << endl;
DestroyStack(SS); // 销毁链栈 SS。
}