前言

• 数据结构是计算机学科的基础，而类链表结构又是数据结构最基本的结构，包括List、stack、queue等；
• 然而，大部分同学甚至连一个可用的List都写不出来；
• 故，下面手打了一份栈实现，供参考；

注意点

• 逻辑正确； 这个也是最基本的
• 模板正确使用；
• 内存的正确申请与释放
• 参数与返回值类型的正确使用
• 高效

代码

#include <iostream>
#include <assert.h>

using namespace std;

// 栈是一种基本数据结构，特色是后进先出

// 模板使用方式
template <typename T>
class MyStack
{
    // 节点定义 这个可以定义在MyStack内部,因为不需要在外部调用
    struct Node
    {
        T value_;           // 存储数据的地方
        struct Node *up_;   // 后置节点指针
        struct Node *down_; // 前置节点指针
        Node(const T &value, Node *down = nullptr, Node *up = nullptr) : value_(value), down_(down), up_(up)
        {
        }
    };

private:
    // 这里使用了顶指针，因为都只是头部操作，所以就不需要底部指针了。
    Node *top_;
    // Node *bottom_;

    int32_t size_;

public:
    MyStack() : top_(nullptr), size_(0) {}

    // 拷贝构造 注意参数需要是引用,否则多一次拷贝
    MyStack(const MyStack<T> &other) : top_(nullptr), size_(0)
    {

        Node *cur = other.top_;
        Node *bottom = top_;
        while (cur)
        {
            Node *temp = new Node(cur->value_, nullptr, bottom);
            // 注释的代码是处理temp的上下指针, 因为通过Node new的时候传入了,所以注释掉
            // temp->down_ = nullptr;
            // temp->up_ = bottom;

            // 如果存在底部指针,底部的向下指针指向temp
            if (bottom)
            {
                bottom->down_ = temp;
            }
            // 如果top_不存在,这里设置一下
            if (!top_)
            {
                top_ = temp;
            }
            // 更新当前的底部指针
            bottom = temp;

            // 向下移动cur
            cur = cur->down_;

            //
            size_++;
        }
    }
    // 注意参数需要为const引用传入,不加const的话会无法传入const类型,不加引用会多一次对象拷贝
    void push(const T &value)
    {
        Node *temp = new Node(value, top_, nullptr);
        // 注释的代码是处理temp的上下指针, 因为通过Node new的时候传入了,所以注释掉
        // temp->down_ = top_;
        // temp->up_ = nullptr;

        // 如果top_存在,top_的向上指针指向temp
        if (top_)
        {
            top_->up_ = temp;
        }
        // 更新top_指针
        top_ = temp;

        //cout<<temp->down_<<" "<<temp->up_<<endl;
        size_++;
    }

    T pop()
    {
        assert(top_);
        // 因为返回的数值所在节点需要delete,所以只能通过值传递回去
        T ret = top_->value_;

        // 标记需要delete的节点指针,用于在下面delete,这里特别容易忘记
        auto to_delete = top_;

        // 移动top_指针
        top_ = top_->down_;
        if (top_)
        {
            // top_的向上指针置空
            top_->up_ = nullptr;
        }
        size_--;

        // 删除节点
        delete to_delete;
        return ret;
    }

    void reverse()
    {
        // 反转的话,先把top_另存,然后自上而下取节点,加在现在链顶部

        // 缓存并移除
        auto cur = top_;
        top_ = nullptr;

        while (cur)
        {
            // cur为待取节点指针
            // next为下一个节点指针
            auto next = cur->down_;
            // 处理取出的节点指针
            cur->up_ = nullptr;
            cur->down_ = nullptr;

            if (!top_)
            {
                // 如果top不存在,设置top为取出的节点指针
                top_ = cur;
            }
            else
            {
                // top_和cur互指
                top_->up_ = cur;
                cur->down_ = top_;
                // 移动top_指针
                top_ = cur;
            }
            // 移动待取指针
            cur = next;
        }
    }
    int32_t size()
    {
        return size_;
    }
};

int main()
{
    MyStack<int> test_stack;
    for (int32_t i = 0; i < 3; i++)
        test_stack.push(i);

    test_stack.reverse();
    while (test_stack.size())
    {
        cout << test_stack.pop() << endl;
    }

    for (int32_t i = 0; i < 3; i++)
        test_stack.push(i);

    MyStack<int> test_stack1 = test_stack;

    test_stack1.reverse();
    while (test_stack1.size())
    {
        cout << test_stack1.pop() << endl;
    }
}

后记

• 希望本篇能有所帮助；如果有其他数据结构不明，也可以留言区骚扰；