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; } 老规矩,有用二连,感谢大家。 (编辑:威海站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |