NickAndNick

Stack<type>

Mar 20th, 2020
129
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. template<typename Type> struct Node {
  3.     Node() : prev(nullptr), next(nullptr) {}
  4.     Type value;
  5.     Node* prev;
  6.     Node* next;
  7. };
  8. template<typename Type>
  9. class Stack {
  10. public:
  11.     using size_type = size_t;
  12.     Stack(const Stack<Type>&) = delete;
  13.     Stack(Stack<Type>&&) = delete;
  14.     Stack<Type> operator=(const Stack<Type>&) = delete;
  15.     Stack<Type> operator=(Stack<Type>&&) = delete;
  16.     Stack() : head_(nullptr), tail_(nullptr), length_(0) {}
  17.     Stack(std::initializer_list<Type>& list) : head_(nullptr), tail_(nullptr), length_(0) {
  18.         for (auto& value : list) push(value);
  19.     }
  20.     Stack(std::initializer_list<Type> list) : head_(nullptr), tail_(nullptr), length_(0) {
  21.         for (auto& value : list) push(value);
  22.     }
  23.     ~Stack() {
  24.         if (tail_ != nullptr) {
  25.             while (!empty()) pop();
  26.         }
  27.     }
  28.     bool empty()const noexcept {
  29.         return tail_ == nullptr;
  30.     }
  31.     void push(const Type& value) {
  32.         Node<Type>* ptr = new Node<Type>;
  33.         if (empty()) {
  34.             head_ = tail_ = ptr;
  35.             tail_->value = value;
  36.         } else {
  37.             tail_->next = ptr;
  38.             ptr->prev = tail_;
  39.             tail_ = ptr;
  40.             tail_->value = value;
  41.         }
  42.         ++length_;
  43.     }
  44.     void pop() {
  45.         if (tail_ == head_) {
  46.             delete tail_;
  47.             tail_ = head_ = nullptr;
  48.         } else {
  49.             Node<Type>* tmp = tail_->prev;
  50.             tail_->prev = tail_->next = nullptr;
  51.             delete tail_;
  52.             tail_ = tmp;
  53.         }
  54.         --length_;
  55.     }
  56.     Type& top() {
  57.         return tail_->value;
  58.     }
  59.     size_type size()const {
  60.         return length_;
  61.     }
  62. private:
  63.     Node<Type>* head_;
  64.     Node<Type>* tail_;
  65.     size_type length_;
  66.     friend bool operator==(const Stack<Type>& a, const Stack<Type>& b) {
  67.         if (a.length_ == b.length_) {
  68.             auto ahead = a.head_;
  69.             auto bhead = b.head_;
  70.             const auto end = a.tail_->next;
  71.             while (ahead != end) {
  72.                 if (ahead->value != bhead->value) return false;
  73.                 ahead = ahead->next;
  74.                 bhead = bhead->next;
  75.             }
  76.             return true;
  77.         }
  78.         return false;
  79.     }
  80.     friend bool operator!=(const Stack<Type>& a, const Stack<Type>& b) {
  81.         return !(a == b);
  82.     }
  83.     friend bool operator<(const Stack<Type>& a, const Stack<Type>& b) {
  84.         const auto length = a.length_ < b.length_ ? a.length_ : b.length_;
  85.         auto ahead = a.head_;
  86.         auto bhead = b.head_;
  87.         for (auto i = 0U; i < length; ++i) {
  88.             if (ahead->value >= bhead->value) return false;
  89.             ahead = ahead->next;
  90.             bhead = bhead->next;
  91.         }
  92.         return a.length_ < b.length_;
  93.     }
  94.     friend bool operator<=(const Stack<Type>& a, const Stack<Type>& b) {
  95.         return a < b || a == b;
  96.     }
  97.     friend bool operator>(const Stack<Type>& a, const Stack<Type>& b) {
  98.         return !(a <= b);
  99.     }
  100.     friend bool operator>=(const Stack<Type>& a, const Stack<Type>& b) {
  101.         return a > b || a == b;
  102.     }
  103. };
  104. int main() {
  105.     Stack<int> stack({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
  106.     std::cout << "Stack size: " << stack.size() << '\n';
  107.     if (!stack.empty()) std::cout << "Top: " << stack.top() << '\n';
  108.     if (!stack.empty()) stack.top() = 15;
  109.     if (!stack.empty()) std::cout << "Top: " << stack.top() << '\n';
  110.     if (!stack.empty()) stack.pop();
  111.     if (!stack.empty()) std::cout << "Top: " << stack.top() << '\n';
  112.     while (!stack.empty()) stack.pop();
  113.     Stack<int> a({ 1, 2, 3, 4, 5 });
  114.     Stack<int> b({ 1, 2, 3, 4, 5 });
  115.     std::cout << "a == b " << std::boolalpha << (a == b) << '\n';
  116.     std::cout << "a < b " << std::boolalpha << (a < b) << '\n';
  117.     std::cout << "a <= b " << std::boolalpha << (a <= b) << '\n';
  118.     std::cout << "a >= b " << std::boolalpha << (a >= b) << '\n';
  119.     std::cout << "a > b " << std::boolalpha << (a > b) << '\n';
  120.     std::cout << "a != b " << std::boolalpha << (a != b) << '\n';
  121.     std::cin.get();
  122. }
RAW Paste Data