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

初始时,栈底指针和栈顶指针都为空,每插入一个节点,栈顶指针改变,当前插入节点的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;
};

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;
}
最后修改:2018 年 12 月 16 日
喜欢就给我点赞吧