C++数据结构之链表栈

这里我们通过C++实现一个链表栈结构，内核是链表，但是需要遵循栈的规则，并包含初始化空栈，判断栈是否为空，判断栈是否已满，插入元素，删除元素，获取栈顶元素大数据堆栈，具体操作如下所示：

堆栈的基本操作

首先整体结构如下：

template <class T>
class Stack {
public:
    Stack();
    Stack(const Stack &list_head);
    ~Stack();
public:
    bool Empty();
    void Push(T &val);
    void Push(T &&val);
    void Pop();
    T Top();
public:
    int size() { return size_; }
private:
    typedef struct Node {
        T val;
        Node* next;
        Node(T x) :val(x), next(NULL) {};
    }ListHead;
    int size_;
    Node* top;
};

如上图所示，这里定义了默认构造和拷贝构造，没定义有参构造。

然后是堆栈基础操作，判空，判满，入栈，出栈以及获取栈顶元素等操作。

最后还加了size()，用于判断链表中的数据是否存在。

数据成员则有两个，分别是当前的元素个数、栈指针。

接下来，我们看各自的实现。

1.初始化

template <class T>
Stack<T>::Stack():top(NULL),size_(0){}
template <class T>
Stack<T>::Stack(const Stack& list_head) {
    Node* cur = list_head.top;  //得到指针
    this->size_ = list_head.size_;
    while (cur) {
        Node* temp = new Node(cur->val); // 拷贝数据
        temp->next = this->top;
        this->top = temp;
        cur = cur->next;
    }
}
template <class T>

Stack<T>::~Stack() {
    if (this->top != NULL) {
        while (this->top != NULL) {
            Node* temp = top->next;
            delete top;
            top = temp;
        }
   }
}

上面三个分别为默认构造，拷贝构造和析构函数。

其中析构函数，对链表还剩余的节点都进行了析构。

拷贝构造函数，则是采用的深拷贝，重新在堆区开辟了空间。

2.判空

template <class T>
bool Stack<T>::Empty() {
    return NULL==top;
}

判空实现比较简单，top指针等于NULL就可以了。

3.压栈

template <class T>
void Stack<T>::Push(T &val) {
    Node* cur = new Node(val);
    cur->next = this->top;
    this->top = cur;
    this->size_++;
}
template <class T>
void Stack<T>::Push(T&& val) {
    Node* cur = new Node(val);
    cur->next = this->top;
    this->top = cur;
    this->size_++;
}

这里压栈的值为自定义类型，虽然内部结构实现是指针，但是对外还是以正常数据类型进行压栈。

之所以还需要重载一个Push函数，是因为不能对右值取引用

4.出栈

template <class T>
void Stack<T>::Pop() {
    if (Empty()) {
        cout << "stack is empty" << endl;
    }
    else {
        size_--;
        Node* temp = top->next;  //移动一格
        delete top; //析构
        top = temp;
    }
}

除了将top指针向前进一步之外，还需要进行节点的析构。

5.获取首部元素

template <class T>
T Stack<T>::Top() {
    if (Empty()) {
        cout << "stack is empty" << endl;
    }
    else {
        return this->top->val;
    }
}

直接通过首部的指针进行访问即可。

最后是测试代码：

测试了int和string两种数据类型，均可以实现。

int main()
{
    Stack<string> s;
    cout << s.Empty() << endl;
    s.Push("nihao");
    s.Push("wohao");
    s.Push("tahao");
    s.Push("dajiahao");
    s.Push("buhao");
    s.Pop();
    cout << s.size() << endl;
    Stack<string> test(s);  //测试拷贝构造函数
    while (!test.Empty()) {
        cout << test.Top() << "\t";
        test.Pop();
    }  cout << endl;
    /***************int****************/
    Stack<int> s_int;
    cout << s.Empty() << endl;
    s_int.Push(4);
    s_int.Push(5);
    s_int.Push(6);
    s_int.Push(8);
    s_int.Push(9);
    s_int.Pop();
    while (!s_int.Empty()) {
        cout << s_int.Top() << "\t";
        s_int.Pop();
    }  cout << endl;
    return 0;
}

老规矩，有用二连，感谢大家。

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!