C++数据结构之链表栈
发布时间：2023-12-20 12:33:52 所属栏目：大数据 来源：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; } 老规矩，有用二连，感谢大家。 （编辑：常州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |