加入收藏 | 设为首页 | 会员中心 | 我要投稿 威海站长网 (https://www.0631zz.cn/)- 科技、云服务器、分布式云、容器、中间件!
当前位置: 首页 > 大数据 > 正文

C++数据结构之链表栈

发布时间:2023-12-09 14:00:37 所属栏目:大数据 来源:DaWei
导读: 这里我们通过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;
 
}
 
老规矩,有用二连,感谢大家。
 
 

(编辑:威海站长网)

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

    推荐文章