数据结构之栈（二）：链式栈实现

马谦马谦马谦

615
文章

17
评论

2018 年 3 月 24 日 22:09:56数据结构和算法评论267字数 240阅读 0 分 48 秒阅读模式

链栈的原理和链表的原理一样，通过一个 next 指针把一个个的节点链起来：

初始时，栈底指针和栈顶指针都为空，每插入一个节点，栈顶指针改变，当前插入节点的 next 指针指向之前的栈顶元素。

同样，在使用 top()和 pop()两个方法时，也要先判断栈是否为空。

一、栈节点

#define uint unsigned int

template <typename T>
class CStackNode
{
public:
    CStackNode() : data(0), pre(0), next(0) {};
    CStackNode(T e, CStackNode* next = 0) : data(e), next(next) {};
    ~CStackNode() { next = 0; };

    T getData() const{ return data; };
    void setNext(CStackNode* e){ next = p; };
    CStackNode *getNext() const{ return next; };
private:
    T data;
    CStackNode *next;
};

#define uint unsigned int

template <typename T>

class CStackNode

{

public:

CStackNode() : data(0), pre(0), next(0) {};

CStackNode(T e, CStackNode* next = 0) : data(e), next(next) {};

~CStackNode() { next = 0; };

T getData() const{ return data; };

void setNext(CStackNode* e){ next = p; };

CStackNode *getNext() const{ return next; };

private:

T data;

CStackNode *next;

};

二、栈

2.1 类定义

#include "StackNode.h"

template <typename T>
class CMyStack {
public:
    CMyStack();
    ~CMyStack();

    void push(T t);
    T top() const;
    T pop();
    uint size() const;
    bool empty() const;
private:
    CStackNode<T>* bottom;
    CStackNode<T>* cur;
    uint len;
};

#include "StackNode.h"

template <typename T>

class CMyStack {

public:

CMyStack();

~CMyStack();

void push(T t);

T top() const;

T pop();

uint size() const;

bool empty() const;

private:

CStackNode<T>* bottom;

CStackNode<T>* cur;

uint len;

};

2.2 类实现

template<typename T>
inline CMyStack<T>::CMyStack()
{
    bottom = cur = 0;
    len = 0;
}

template<typename T>
inline CMyStack<T>::~CMyStack()
{
    if (!bottom) return;
    CStackNode<T>* p = cur, *q;
    while (p) {
        q = p->getNext();
        delete p;
        p = q;
    }
    bottom = cur = 0;
    len = 0;
}

// 压栈
template<typename T>
inline void CMyStack<T>::push(T t) {
    CStackNode<T> *pNode = new CStackNode<T>(t);
    pNode->setNext(cur);
    cur = pNode;
    // 如果栈为空，设置 bottom 的值
    if (!bottom)
        bottom = cur;
    len++;
}

// 获取栈顶元素
template<typename T>
inline T CMyStack<T>::top() const
{
    return cur->getData();
}

// 出栈
template<typename T>
inline T CMyStack<T>::pop()
{
    T tmp = cur->getData();
    CStackNode<T> *dNode = cur;
    cur = cur->getNext();
    // 删除节点
    delete dNode;
    len -= 1;
    // 当前结点是最后一个
    if (!cur) bottom = 0;
    return tmp;
}

// 返回栈大小
template<typename T>
inline uint CMyStack<T>::size() const
{
    return len;
}

// 判断栈是否为空
template<typename T>
inline bool CMyStack<T>::empty() const
{
    return len == 0;
}