简介

stack是配接器：

一种用来修饰容器（containers） 或仿函式（functors） 或迭代器（iterators）接口的东西

stack在源码中底层是deque，由于deque还没写，刚写了list，就用list来实现stack。 环境：VS2017

list迭代器

#pragma once #include <iostream> using std::cout; using std::cerr; using std::endl; namespace HN { template<typename T> struct hn_list_node;//下边要用到，所以先声明,仅声明模板使用extern报错，原因未知 template<class T> class hn_list;//下边要用到，所以先声明，仅声明模板使用extern报错，原因未知 //const迭代器 template<typename T> class const_iterator { public: friend class hn_list<T>;//设置友元以访问hn_list const_iterator() :current(NULL) { } const T& operator*() const { return current->node; } const_iterator & operator++(int) { const_iterator old = *this; ++(*this); return old; } const_iterator & operator++() { current = current->next; return *this; } bool operator == (const const_iterator & rhs) const { return current == rhs.current ? true : false; } bool operator != (const const_iterator & rhs) const { return !(current == rhs.current); } hn_list_node<T> * operator -> () { return current; } ~const_iterator() { } protected: hn_list_node<T> * current; T& retrieve() const//恢复，即得到节点 { return current->node; } private: }; //普通迭代器，继承自cosnt迭代器 template<typename T> class iterator : public const_iterator<T> { public: friend class hn_list<T>;//设置友元以访问hn_list iterator() { } //非const默认调用此版本 const T& operator * () { //cout << "调用非const版本operator *()" << endl; return const_iterator<T>::current->node; } //可以看到根据是否为const对象函数可以实现重载,const对象调用此版本 const T& operator * () const { //cout << "调用const版本operator *()" << endl; return const_iterator<T>::operator *(); } iterator& operator++()//前置自增 { const_iterator<T>::current = const_iterator<T>::current->next; return *this; } iterator& operator++(int)//后置自增 { iterator old = *this; ++(*this); return old; } ~iterator() { } }; }

list实现

#pragma once #include "hn_iterator.h" namespace HN { //template<typename T> class const_iterator; //template<typename T> class iterator; //链表节点 template<typename T> struct hn_list_node { hn_list_node<T> * pre; hn_list_node<T> * next; T node; hn_list_node() :pre(nullptr), next(nullptr) { } hn_list_node(const T & obj) :node(obj), pre(nullptr), next(nullptr) { } }; //链表 template<class T> class hn_list { public: typedef const_iterator<T> const_iterator;//简化 typedef iterator<T> iterator;//简化 hn_list() :head_node_ptr(new hn_list_node<T>()), tail_node_ptr(new hn_list_node<T>()), theSize(0) { cout << "进入hn_list无参构造" << endl; head_node_ptr->next = tail_node_ptr; tail_node_ptr->pre = head_node_ptr; } hn_list(int size) :head_node_ptr(new hn_list_node<T>()), tail_node_ptr(new hn_list_node<T>()), theSize(size) { cout << "进入hn_list指定大小构造" << endl; head_node_ptr->next = tail_node_ptr; tail_node_ptr->pre = head_node_ptr; for (int i = 0; i < theSize; i++) { hn_list_node<T> * tmp = new hn_list_node<T>(); tail_node_ptr->pre->next = tmp; tmp->pre = tail_node_ptr->pre; tmp->next = tail_node_ptr; tail_node_ptr->pre = tmp; } } const_iterator begin() const { const_iterator it; it.current = head_node_ptr->next; return it; } const_iterator end() const { const_iterator it; it.current = tail_node_ptr; return it; } iterator begin() { iterator it; it.current = head_node_ptr->next; return it; } //拷贝构造函数 hn_list(const hn_list<T> & rhs) :head_node_ptr(new hn_list_node<T>()), tail_node_ptr(new hn_list_node<T>()), theSize(rhs.theSize) { cout << "进入hn_list拷贝构造" << endl; head_node_ptr->next = tail_node_ptr; tail_node_ptr->pre = head_node_ptr; for (const_iterator it = rhs.begin(); it != rhs.end(); it++) { push_back(*it); } } void push_back(const hn_list_node<T>& rhs) { hn_list_node<T> *tmp = new hn_list_node<T>(rhs); tail_node_ptr->pre->next = tmp; tmp->pre = tail_node_ptr->pre; tmp->next = tail_node_ptr; tail_node_ptr->pre = tmp; ++theSize; } void push_front(const T& rhs) { hn_list_node<T> * tmp = new hn_list_node<T>(rhs); head_node_ptr->next->pre = tmp; tmp->next = head_node_ptr->next; head_node_ptr->next = tmp; tmp->pre = head_node_ptr; ++theSize; } void pop_front() { if (empty()) return; hn_list_node<T> * tmp = head_node_ptr->next; head_node_ptr->next = tmp->next; tmp->next->pre = head_node_ptr; delete tmp; --theSize; } void pop_back() { if (empty()) return; hn_list_node<T>* tmp = tail_node_ptr->pre; tmp->pre->next = tail_node_ptr; tail_node_ptr->pre = tmp->pre; delete tmp; --theSize; } bool empty() { return theSize == 0 ? true : false; } void clear() { while (!empty()) { pop_back(); } } void resize(int num) { if (num == theSize) { return; } else if (num > theSize) { int n = num - theSize; for (int i = 0; i < n; i++) { push_back(T()); } } else { int n = theSize - num; for (int i = 0; i < n; i++) { pop_back(); } } } T& front() { return head_node_ptr->next->node; } T& back() { return tail_node_ptr->pre->node; } int size()const { return theSize; } //应再实现一个iterator版本 void insert(const_iterator it, const T& rhs) { hn_list_node<T> * tmp = it.current; hn_list_node<T> * new_node = new hn_list_node<T>(rhs); tmp->pre->next = new_node; new_node->pre = tmp->pre; new_node->next = tmp; tmp->pre = new_node; ++theSize; } //只删除第一个相等的节点 void remove(const T& rhs) { if (empty()) return; else { for (iterator it = begin(); it != end(); it++) { if (*it == rhs) { cout << "remove " << *it << endl; hn_list_node<T> * tmp = it.current; tmp->next->pre = tmp->pre; tmp->pre->next = tmp->next; delete tmp; --theSize; return;//已经remove了，应当返回，因为迭代器已经失效了 } } } } //此处返回hn_list<T>&，用以支持连等，即ld = lc = lb; //也可以返回void const hn_list<T>& operator = (const hn_list<T>& rhs) { cout << "进入赋值运算符" << endl; if (this == &rhs) { return *this; } else { this->clear(); hn_list::const_iterator it = rhs.begin(); for (; it != rhs.end(); it++) { push_back(*it); } return *this; } } //仅仅为了测试写的，便于查看各个元素 void show() { hn_list_node<T> * tmp = head_node_ptr->next; while (tmp!=tail_node_ptr) { cout << tmp->node << " "; tmp = tmp->next; } cout << endl; } bool operator == (const hn_list<T> & rhs) { if (this == &rhs) { return true; } else if(theSize==rhs.theSize) { hn_list::const_iterator itl = begin(); hn_list::const_iterator itr = rhs.begin(); while (itl!=end() && itr!=rhs.end()) { if (itl.current->node != itr.current->node) { return false; } itl++; itr++; } return true; } else { return false; } } ~hn_list() { cout << "进入hn_list析构" << endl; if (head_node_ptr != NULL) delete head_node_ptr; if (tail_node_ptr != NULL) { delete tail_node_ptr; } } protected: hn_list_node<T> * head_node_ptr; hn_list_node<T> * tail_node_ptr; int theSize; }; }

stack实现

#pragma once #include <iostream> #include "hn_list.h" using std::cout; using std::cerr; using std::endl; using namespace HN; namespace HN { //此处默认传入我自己写的list，也可以传入std::list template<typename T,class hn_List=hn_list<T>> class hn_stack { public: hn_stack() { cout << "进入hn_stack无参构造函数" << endl; } ~hn_stack() { } void clear() { return list.clear(); } bool empty() { return list.empty(); } int size() const { return list.size(); } void push(T t) { list.push_back(t); } void pop() { if (list.empty()) { cerr << "栈已空！！！"; return; } else { list.pop_back(); } } T& top() { return list.back(); } void show() { list.show(); } bool operator == (const hn_stack<T, hn_List> & rhs) { return list == rhs.list; } protected: hn_List list; }; }

测试代码

#include "pch.h" #include "hn_stack.h" #include <stack> using namespace std; int main() { std::cout << "Hello World!\n"; hn_stack<int> sa; sa.push(1); sa.push(3); sa.push(5); cout << "sa.empty(): " << (true==sa.empty()?"true":"false") << endl; cout << "sa.size(): " << sa.size() << endl; sa.show(); sa.pop(); sa.pop(); sa.pop(); sa.pop(); sa.show(); sa.push(1); sa.push(3); sa.push(5); sa.push(1); sa.push(3); sa.push(5); sa.show(); cout<<"sa.top(): "<<sa.top() << endl; sa.top()++; cout << "sa.top(): " << sa.top() << endl; sa.clear(); cout << "after clear:-------------------------------------------------" << endl; cout << "sa.empty(): " << (true == sa.empty() ? "true" : "false") << endl; cout << "sa.size(): " << sa.size() << endl; sa.push(1); sa.push(3); sa.push(5); sa.push(1); sa.push(3); sa.push(5); cout << "sa.size(): " << sa.size() << endl; sa.show(); hn_stack<int> sb; sb.push(1); sb.push(3); sb.push(5); sb.push(1); sb.push(3); sb.push(5); cout << "sb.size(): " << sb.size() << endl; sb.show(); cout << "sa==sb? : " << (sa == sb?"true":"false") << endl; cout << "TEST END!!!" << endl; }

测试结果

总结

list的实现略有修改，所以此处再次贴出。 stack实现了基本功能，符合预期。