数据结构——链式栈模板类实现
程序员文章站
2022-06-01 13:52:17
...
数据结构笔记3.1.3
链式栈和前面的顺序栈是栈的两种不同实现形式,其实就是顺序表与链式表,区别在于其实现的方式(数组和指针节点),顺序栈指的是其每个节点的物理存储是连续的,因为是使用数组实现的。而链式栈存储位置则是不连续的,需要指针来穿接。
但是因为栈的操作单调,相对于单链表更容易实现,单链表相当于是一个泛泛的存储表,其操作更加任意,而像栈、队列这种数据组织结构,其只能在整个表的端进行操作,这也从另一个方面体现出链式栈相对容易实现。
那为何有顺序表这种总领性的结构,还要建立栈、队列这些子数据结构呢?这就好比是“专门化”与“普遍化”的比较,一般专门化的东西,其在相应问题上的效率会比普遍使用的工具要高,所以,分化后的子结构其存在的意义绝不容小视!最后说一下顺序栈与链式栈的比较,他们都是一种数据组织与操纵方式(DRO),但是在解决不同问题的时候,不同的存储方式实现同样的功能,可能在效率、复杂度、空间利用率等方面都会千差万别,各有千秋!下面贴出代码:
模板类——链式栈
//数据结构——链式栈的模板类定义 By Zhu Xiuyu 17/10/13
#include <iostream>
#include <cassert>
using namespace std;
//节点定义
template<class T>
struct StackNode {
T data; //栈每个节点的数据域
StackNode<T> *next; //栈节点的指针域
StackNode(T x, StackNode<T> *Node = NULL) : data(x){}
};
//模板类定义
template<class T>
class LinkedStack {
public:
LinkedStack() : top(NULL){} //构造函数
~LinkedStack(); //析构函数
void Push(const T & x); //进栈
bool Pop(T & x); //出栈
bool getTop(T & x) const; //读取栈顶元素
bool isEmpty()const; //判断栈是否为NULL
int getSize() const; //求栈的元素的个数
void makeEmpty(); //清空栈
void output(ostream & out); //输出函数(此处由重载函数调用)
private:
StackNode<T> *top; //栈顶指针
};
//函数定义
template<class T>
void LinkedStack<T>::makeEmpty() {
//逐个删去链式栈中的元素,直至栈顶指针为空
StackNode<T> *p; //逐个节点释放
while (top != NULL) {
p = top;
top = top->next;
delete p;
}
}
template<class T>
LinkedStack<T>::~LinkedStack() {
//析构函数
makeEmpty();
}
template<class T>
bool LinkedStack<T>::isEmpty() const{
if (NULL == top) {
return true;
}
return false;
}
template<class T>
void LinkedStack<T>::Push(const T & x) {
//将元素x推入栈顶
StackNode<T> *newNode = new StackNode<T>(x);
assert(newNode != NULL); //内存分配错误的中断处理
newNode->next = top;
top = newNode;
}
template<class T>
bool LinkedStack<T>::Pop(T & x) {
//删除栈顶节点,删除的data返回到x当中
if (isEmpty()) {
return false; //栈为NULL出栈失败
}
StackNode<T> *p = top; //标记Top
top = top->next; //更新栈顶指针
x = p->data;
delete p; //释放栈顶元素
return true;
}
template<class T>
bool LinkedStack<T>::getTop(T & x) const {
//返回栈顶元素的值
if (isEmpty()) {
return false; //栈为NULL,读取栈顶失败
}
x = top->data;
return true;
}
template<class T>
int LinkedStack<T>::getSize()const {
StackNode<T> *p = top;
int len = 0;
while (p != NULL) {
p = p->next;
len++;
}
return len;
}
template<class T>
void LinkedStack<T>::output(ostream & out) {
//输出链式栈
StackNode<T> *p = top;
while (p != NULL) {
out << p->data << ' ';
p = p->next;
}
}
template<class T>
ostream & operator << (ostream & out, LinkedStack<T> & LS) {
//重载输出运算符
LS.output(out); //避免友元函数在模板class中出现的问题
cout << endl;
return out;
}
测试Main函数
int main()
{
//Push and Pop测试
LinkedStack<int> LS; //定义一个链式栈
LS.Push(1);
LS.Push(2);
LS.Push(3);
LS.Push(4);
LS.Push(5);
cout << LS; //用重载函数输出
int del1, del2;
LS.Pop(del1);
LS.Pop(del2);
cout << LS;
//getSize 和 getTop测试
int topVal = 0;
LS.getTop(topVal);
cout << topVal << endl;
cout << LS.getSize() << endl;
//判断是否为NULL测试
if (LS.isEmpty()) {
cout << "空栈" << endl;
}
else {
cout << "非空栈" << endl;
}
LS.makeEmpty();
if (LS.isEmpty()) {
cout << "空栈" << endl;
}
else {
cout << "非空栈" << endl;
}
system("pause");
return 0;
}
运行效果:
上一篇: Dubbo源码分析(六):Cluster
下一篇: Http请求连接池工具类