fix: remove memory leak in queue

ShuN6211 · Jan 11, 2023 · effd74c · effd74c
1 parent e2bf654
commit effd74c
Show file tree

Hide file tree

Showing 6 changed files with 226 additions and 160 deletions.
diff --git a/data_structures/node.hpp b/data_structures/node.hpp
@@ -0,0 +1,48 @@
+/**
+ * @file
+ * @brief  Provides Node class and related utilities
+ **/
+#ifndef DATA_STRUCTURES_NODE_HPP_
+#define DATA_STRUCTURES_NODE_HPP_
+
+#include <iostream>  /// for std::cout
+#include <memory>    /// for std::shared_ptr
+#include <vector>    /// for std::vector
+
+/** Definition of the node as a linked-list
+ * \tparam ValueType type of data nodes of the linked list should contain
+ */
+template <class ValueType>
+struct Node {
+    using value_type = ValueType;
+    ValueType data = {};
+    std::shared_ptr<Node<ValueType>> next = {};
+};
+
+template <typename Node, typename Action>
+void traverse(const Node* const inNode, const Action& action) {
+    if (inNode) {
+        action(*inNode);
+        traverse(inNode->next.get(), action);
+    }
+}
+
+template <typename Node>
+void display_all(const Node* const inNode) {
+    traverse(inNode,
+             [](const Node& curNode) { std::cout << curNode.data << " "; });
+}
+
+template <typename Node>
+std::vector<typename Node::value_type> push_all_to_vector(
+    const Node* const inNode, const std::size_t expected_size=0) {
+    std::vector<typename Node::value_type> res;
+    if (expected_size != 0) {
+        res.reserve(expected_size);
+    }
+    traverse(inNode,
+             [&res](const Node& curNode) { res.push_back(curNode.data); });
+    return res;
+}
+
+#endif  // DATA_STRUCTURES_NODE_HPP_
diff --git a/data_structures/queue.h b/data_structures/queue.h
diff --git a/data_structures/queue.hpp b/data_structures/queue.hpp
@@ -0,0 +1,80 @@
+/* This class specifies the basic operation on a queue as a linked list */
+#ifndef DATA_STRUCTURES_QUEUE_HPP_
+#define DATA_STRUCTURES_QUEUE_HPP_
+
+#include "node.hpp"
+
+/** Definition of the queue class */
+template <class ValueType>
+class queue {
+    using node_type = Node<ValueType>;
+
+ public:
+    using value_type = ValueType;
+    /** Show queue */
+    void display() const {
+        std::cout << "Front --> ";
+        display_all(this->queueFront.get());
+        std::cout << '\n';
+        std::cout << "Size of queue: " << size << '\n';
+    }
+
+    std::vector<value_type> toVector() const {
+        return push_all_to_vector(this->queueFront.get(), this->size);
+    }
+
+ private:
+    void ensureNotEmpty() const {
+        if (isEmptyQueue()) {
+            throw std::invalid_argument("Stack is empty.");
+        }
+    }
+
+ public:
+    /** Determine whether the queue is empty */
+    bool isEmptyQueue() const { return (queueFront == nullptr); }
+
+    /** Add new item to the queue */
+    void enQueue(const value_type& item) {
+        auto newNode = std::make_shared<node_type>();
+        newNode->data = item;
+        newNode->next = nullptr;
+        if (isEmptyQueue()) {
+            queueFront = newNode;
+            queueRear = newNode;
+        } else {
+            queueRear->next = newNode;
+            queueRear = queueRear->next;
+        }
+        size++;
+    }
+
+    /** Return the first element of the queue */
+    ValueType front() const {
+        ensureNotEmpty();
+        return queueFront->data;
+    }
+
+    /** Remove the top element of the queue */
+    void deQueue() {
+        ensureNotEmpty();
+        queueFront = queueFront->next;
+        size--;
+    }
+
+    /** Clear queue */
+    void clear() {
+        queueFront = nullptr;
+        queueRear = nullptr;
+        size = 0;
+    }
+
+ private:
+    std::shared_ptr<node_type> queueFront =
+        {}; /**< Pointer to the front of the queue */
+    std::shared_ptr<node_type> queueRear =
+        {}; /**< Pointer to the rear of the queue  */
+    std::size_t size = 0;
+};
+
+#endif  // DATA_STRUCTURES_QUEUE_HPP_
diff --git a/data_structures/stack.hpp b/data_structures/stack.hpp
@@ -7,28 +7,9 @@
 #ifndef DATA_STRUCTURES_STACK_HPP_
 #define DATA_STRUCTURES_STACK_HPP_
 
-#include <iostream>   /// for IO operations
-#include <memory>     /// for std::shared_ptr
 #include <stdexcept>  /// for std::invalid_argument
-#include <vector>     /// for std::vector
 
-/** Definition of the node as a linked-list
- * \tparam ValueType type of data nodes of the linked list should contain
- */
-template <class ValueType>
-struct node {
-    ValueType data = {};  ///< data at current node
-    std::shared_ptr<node<ValueType>> next =
-        {};  ///< pointer to the next ::node instance
-};
-
-template <typename Node, typename Action>
-void traverse(const Node* const inNode, const Action& action) {
-    if (inNode) {
-        action(*inNode);
-        traverse(inNode->next.get(), action);
-    }
-}
+#include "node.hpp"  /// for Node
 
 /** Definition of the stack class
  * \tparam value_type type of data nodes of the linked list in the stack should
@@ -42,20 +23,13 @@ class stack {
     /** Show stack */
     void display() const {
         std::cout << "Top --> ";
-        traverse(stackTop.get(), [](const node<value_type>& inNode) {
-            std::cout << inNode.data << "  ";
-        });
-        std::cout << std::endl;
+        display_all(this->stackTop.get());
+        std::cout << '\n';
         std::cout << "Size of stack: " << size << std::endl;
     }
 
     std::vector<value_type> toVector() const {
-        std::vector<value_type> res;
-        res.reserve(this->size);
-        traverse(stackTop.get(), [&res](const node<value_type>& inNode) {
-            res.push_back(inNode.data);
-        });
-        return res;
+        return push_all_to_vector(this->stackTop.get(), this->size);
     }
 
  private:
@@ -71,7 +45,7 @@ class stack {
 
     /** Add new item to the stack */
     void push(const value_type& item) {
-        auto newNode = std::make_shared<node<value_type>>();
+        auto newNode = std::make_shared<Node<value_type>>();
         newNode->data = item;
         newNode->next = stackTop;
         stackTop = newNode;
@@ -98,7 +72,7 @@ class stack {
     }
 
  private:
-    std::shared_ptr<node<value_type>> stackTop =
+    std::shared_ptr<Node<value_type>> stackTop =
         {};                /**< Pointer to the stack */
     std::size_t size = 0;  ///< size of stack
 };