数据结构——链式栈模板类实现-蒲公英云

数据结构——链式栈模板类实现

向右看齐 2022-06-07 07:08 332阅读 0赞

数据结构笔记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;
}