[fix/docs]: remove memory leak in queue (TheAlgorithms#2417)

* fix: remove memory leak in queue * updating DIRECTORY.md * clang-format and clang-tidy fixes for effd74c * style: simplify logic while using reserve * style: use value_type as return type in front * style: use proper error message * style: use pre-increment and pre-decrement * docs: use doxygen syntax * docs: improve wording Co-authored-by: github-actions[bot] <github-actions@users.noreply.github.com> Co-authored-by: David Leal <halfpacho@gmail.com>
ShuN6211 · Jan 26, 2023 · 7c09048 · 7c09048
1 parent 5b23872
commit 7c09048
Show file tree

Hide file tree

Showing 7 changed files with 250 additions and 161 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -57,7 +57,8 @@
   * [Linkedlist Implentation Usingarray](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/linkedlist_implentation_usingarray.cpp)
   * [List Array](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/list_array.cpp)
   * [Morrisinorder](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/morrisinorder.cpp)
-  * [Queue](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue.h)
+  * [Node](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/node.hpp)
+  * [Queue](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue.hpp)
   * [Queue Using Array](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue_using_array.cpp)
   * [Queue Using Array2](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue_using_array2.cpp)
   * [Queue Using Linked List](https://github.com/TheAlgorithms/C-Plus-Plus/blob/HEAD/data_structures/queue_using_linked_list.cpp)

diff --git a/data_structures/node.hpp b/data_structures/node.hpp
@@ -0,0 +1,46 @@
+/**
+ * @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;
+    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,104 @@
+/* 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;
+    /**
+     * @brief prints the queue into the std::cout
+     */
+    void display() const {
+        std::cout << "Front --> ";
+        display_all(this->queueFront.get());
+        std::cout << '\n';
+        std::cout << "Size of queue: " << size << '\n';
+    }
+
+    /**
+     * @brief converts the queue into the std::vector
+     * @return std::vector containning all of the elements of the queue in the
+     * same order
+     */
+    std::vector<value_type> toVector() const {
+        return push_all_to_vector(this->queueFront.get(), this->size);
+    }
+
+ private:
+    /**
+     * @brief throws an exception if queue is empty
+     * @exception std::invalid_argument if queue is empty
+     */
+    void ensureNotEmpty() const {
+        if (isEmptyQueue()) {
+            throw std::invalid_argument("Queue is empty.");
+        }
+    }
+
+ public:
+    /**
+     * @brief checks if the queue has no elements
+     * @return true if the queue is empty, false otherwise
+     */
+    bool isEmptyQueue() const { return (queueFront == nullptr); }
+
+    /**
+     * @brief inserts a new item into 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
+     * @exception std::invalid_argument if queue is empty
+     */
+    value_type front() const {
+        ensureNotEmpty();
+        return queueFront->data;
+    }
+
+    /**
+     * @brief removes the first element from the queue
+     * @exception std::invalid_argument if queue is empty
+     */
+    void deQueue() {
+        ensureNotEmpty();
+        queueFront = queueFront->next;
+        --size;
+    }
+
+    /**
+     * @brief removes all elements from the 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
 };