北邮22信通：（10）第三章 3.2栈的实现

北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

北邮22信通：（9）实验1 题目六：模拟内存管理（搬运官方代码）_青山如墨雨如画的博客-CSDN博客

下一篇文章：

目录

3.2.1顺序栈

代码部分：

运行结果：

遇到问题：

运行结果：

3.2.2链式栈：

代码部分：

运行结果：

---

***闲话***

老规矩，书上干净完整代码，拿去用！

最近一直在忙感冒忙修电脑忙期中考试（          有点断更（

顺序栈里边两个栈共用一个存储空间的代码正在更新中  敬请期待

下面就是实现顺序栈和链式栈的代码，其实原理都差不多，甚至主函数都一样（

对小编个人而言更喜欢用链表a 不想判断顺序栈可恶的开始终止位置

然后虚拟数据类型我写了一个student，比较简单的数据类型嘞，方便大家看

其他的想到啥再补充啥  有问题或者我写的有不对的地方欢迎评论区指正！

**********

3.2.1顺序栈

代码部分：

#include <iostream>
using namespace std;
struct student
{int ID;string name;
};
ostream& operator<<(ostream& output, student& stu)
{output << stu.ID << " " << stu.name;return output;
}
const int stacksize = 1024;
template <class temp>
class seqstack
{
public:seqstack() { top = -1; }void push(temp x);temp pop();temp gettop();bool empty() { return top == -1 ? true : false; }//判断栈空时的条件：top==-1?
private:temp data[stacksize];int top;
};template<class temp>
void seqstack<temp>::push(temp x)
{if (this->top > stacksize - 1)throw"上溢";this->top++;this->data[this->top] = x;
}template <class temp>
temp seqstack<temp>::pop()
{if (empty())throw"下溢";this->top--;return this->data[this->top + 1];
}template<class temp>
temp seqstack<temp>::gettop()
{if (empty())throw"下溢";return this->data[this->top];
}
int main()
{try{system("color 0A");student x[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"meng"} };seqstack<student> seq1;cout << "显示栈内是否为空？" << endl;cout << seq1.empty();cout << endl << endl;cout << "数据传输中……" << endl;for (int i = 0; i < 5; i++)seq1.push(x[i]);cout << "显示栈内是否为空？" << endl;cout << seq1.empty();cout << endl << endl;student stutemp;for (int i = 0; i < 5; i++){cout << "出栈元素的信息:" << endl;stutemp = seq1.pop();cout << stutemp;cout << endl;cout << "此时栈顶元素信息:" << endl;stutemp = seq1.gettop();cout << stutemp;cout << endl << endl;}cout << endl << "现在重新判断栈是否为空:" << endl;cout << seq1.empty();}catch (const char* a){cout << a << endl;}return 0;
}

运行结果：

遇到问题：

发现没有执行程序第79、80行

原因：catch到了const char*类型的异常，程序终止运行。

需要注意的是，一定要catch （const char*）！！！不要catch（string）否则你的程序跑不起来

我们把68行循环终止条件改成3：

运行结果：

 

3.2.2链式栈：

代码部分：

#include <iostream>
using namespace std;
struct student
{int ID;string name;
};
ostream& operator<<(ostream& output, student& stu)
{output << stu.ID << " " << stu.name;return output;
}
template <class temp>
struct node
{temp data;node<temp>* next;
};template <class temp>
class linkstack
{
public:linkstack() { top = NULL; }~linkstack();void push(temp x);temp pop();temp gettop();bool empty(){return top == NULL ? true : false;}
private:node<temp>* top;
};template <class temp>
void linkstack<temp>::push(temp x)
{node<temp>* p = new node<temp>;p->data = x;p->next = this->top;this->top = p;
}template<class temp>
temp linkstack<temp>::pop()
{if (empty())throw "下溢";temp x = this->top->data;node<temp>* p = this->top;this->top = this->top->next;delete p;return x;
}template<class temp>
linkstack<temp>::~linkstack()
{while (this->top != NULL){node<temp>* p = this->top;this->top = this->top->next;delete p;}
}template<class temp>
temp linkstack<temp>::gettop()
{if (empty())throw"下溢";return this->top->data;
}
int main()
{try{system("color 0A");student x[5] = { {1,"zhang"},{2,"wang"},{3,"li"},{4,"zhao"},{5,"meng"} };linkstack<student> linklist1;cout << "显示栈是否为空？" << endl;cout << linklist1.empty();cout << endl << endl;cout << "数据传输中……" << endl;for (int i = 0; i < 5; i++)linklist1.push(x[i]);cout << "显示栈是否为空？" << endl;cout << linklist1.empty();cout << endl << endl;student stutemp;for (int i = 0; i < 5; i++){cout << "出栈元素信息:" << endl;stutemp = linklist1.pop();cout << stutemp;cout << endl;cout << "此时栈顶元素信息:" << endl;stutemp = linklist1.gettop();cout << stutemp;cout << endl << endl;}cout << "现在重新判断栈是否为空:" << endl;cout << linklist1.empty();}catch (const char*a){cout << a << endl;}return 0;
}

运行结果：

（将pop循环改成循环到3，同理，会显示最后一行“现在重新判断栈是否为:”）