(第五步) STL: stl_stack容器实现

stack

stack的设计非常简单，本身是一种单向出口的FILO的数据结构

使用双向的数据结构都能实现，就如前面设计的list、deque

vector是尾部单向的，也可以作为实现原理

前面的deque需要改程序参数

list的 == 、!=存在问题，其他功能完好

vector没有问题，这里使用vector实现stack

stack设计

• 操作 比较和分配堆栈

• empty() 堆栈为空则返回真

• pop() 移除栈顶元素

• push() 在栈顶增加元素

• size() 返回栈中元素数目

• top() 返回栈顶元素

stl_stack.h

 #ifndef _STACK_H_
 #define _STACK_H_
 ​
 #include "../p2_STL_Source/stl_vector.h"
 //#include "../p2_STL_Source/stl_deque.h"
 #include "../p2_STL_Source/stl_list.h"
 ​
 namespace mySTL {
     // class of stack
     // 双向开口的数据结构都能实现，你这里换deque、list、vector
     // deque需要改程序参数，list的 == 、!=存在一些问题，其他修改完毕
     template<class T, class Container = mySTL::vector<T>>
     class stack {
     public:
         typedef typename Container::value_type  value_type; // 等同于 T value_type
         typedef typename Container::reference   reference;
         typedef typename Container::size_type   size_type;
         typedef Container                       container_type;
 ​
         
         //typedef typename Container::const_reference       const_reference;
         
 ​
     private:
         container_type container_;
 ​
     public:
         // 构造
         explicit stack(const container_type& ctnr = container_type()) :container_(ctnr) {}
 ​
         // 元素查看
         bool empty() const { return container_.empty(); }
         size_type size() const { return container_.size(); }
 ​
         reference top() { return (container_.back()); }
         const reference top() const { return (container_.back()); }
 ​
         // 元素操作
         void push(const value_type& val) { container_.push_back(val); }
         void pop() { container_.pop_back(); }
         void swap(stack& x) { mySTL::swap(container_, x.container_); }
 ​
         // 友元类内声明，类外定义
     public:
         template <class T, class Container>
         friend bool operator== (const stack<T, Container>& lhs, const stack<T, Container>& rhs);
         template <class T, class Container>
         friend bool operator!= (const stack<T, Container>& lhs, const stack<T, Container>& rhs);
         
         template <class T, class Container>
         friend void swap(stack<T, Container>& x, stack<T, Container>& y);
     };
 ​
     template <class T, class Container>
     bool operator== (const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
         return lhs.container_ == rhs.container_;
     }
     template <class T, class Container>
     bool operator!= (const stack<T, Container>& lhs, const stack<T, Container>& rhs) {
         return lhs.container_ != rhs.container_;
     }
     template <class T, class Container>
     void swap(stack<T, Container>& x, stack<T, Container>& y) {
         x.swap(y);
     }
     
 }
 #endif

stl_stack_test.h

#ifndef _STACK_TEST_H_
 #define _STACK_TEST_H_
 ​
 #include "../p2_STL_Source/stl_stack.h"
 #include <stack>
 ​
 #include <cassert>
 #include <string>
 ​
 namespace mySTL {
     namespace stackTest {
         template<class T>
         using stdStk = std::stack < T >;
         template<class T>
         using myStk = mySTL::stack < T >;
 ​
         void test01();
         void test02();
         void test03();
         void test04();
         
     }
 }
 ​
 #endif

stl_stack_test.cpp

#include "stl_stack_test.h"
 ​
 using namespace std;
 ​
 namespace mySTL 
 {
     namespace stackTest 
     {
         void test01()
         {
             stdStk<int> stk1;
             myStk<int> stk2;
 ​
             for (auto i = 0; i != 10; ++i) {
                 stk1.push(i);
                 stk2.push(i);
             }
             
             for (auto i = 0; i != 10; ++i) {
                 cout << stk1.top() << " \t";
                 cout << stk2.top() << endl;
                 stk1.pop();
                 stk2.pop();
             }
         }
         void test02()
         {
             myStk<std::string> stk;
             
             cout << "is empty: " << boolalpha << stk.empty() << endl;
             cout << "size : " << stk.size() << endl;
 ​
             stk.push("one");
             stk.push("two");
             stk.push("three");
 ​
             cout << "is empty: " << boolalpha << stk.empty() << endl;
             cout << "size : " << stk.size() << endl;
             cout << "top val : " << stk.top() << endl;
 ​
             stk.pop();
 ​
             cout << "is empty: " << boolalpha << stk.empty() << endl;
             cout << "size : " << stk.size() << endl;
             cout << "top val : " << stk.top() << endl;
 ​
         }
         void test03()
         {
             myStk<int> stk1;
             for (auto i = 0; i != 10; ++i)
                 stk1.push(i);
 ​
             cout << "size1 : " << stk1.size() << endl;
 ​
             auto stk2(stk1);
 ​
             cout << "size2 : " << stk1.size() << endl;
             cout << "is equal: " << boolalpha << (stk1 == stk2) << endl;
             cout << "is not equal: " << boolalpha << (stk1 != stk2) << endl;
         }
         void test04()
         {
             myStk<int> st1, st2;
             st1.push(1); st1.push(2); st1.push(3);
             st2.push(1); st2.push(2);
 ​
             cout << "size1 is 3 : " << st1.size() << endl;
             cout << "size2 is 2 : " << st2.size() << endl;
 ​
             st1.swap(st2);
             cout << "size1 is 2 : " << st1.size() << endl;
             cout << "size2 is 3 : " << st2.size() << endl;
 ​
             mySTL::swap(st1, st2);
             cout << "size1 is 3 : " << st1.size() << endl;
             cout << "size2 is 2 : " << st2.size() << endl;
         }
     }
 }