欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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;
}

运行效果:
数据结构——链式栈模板类实现