# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1435080483 18000
# Node ID 1198fe3684a6ec74b5a65d7165b828c27d3ec28b
# Parent  c2cbfdf528f6db84ea8e1a46476547e49f06ce0c
1.3.38 Stack based implementation.  Code not tested.

diff -r c2cbfdf528f6 -r 1198fe3684a6 algs4-c++/1.3.38
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/1.3.38	Tue Jun 23 12:28:03 2015 -0500
@@ -0,0 +1,1 @@
+src/GeneralizedQueue.hpp
\ No newline at end of file
diff -r c2cbfdf528f6 -r 1198fe3684a6 algs4-c++/src/GeneralizedQueue.hpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/algs4-c++/src/GeneralizedQueue.hpp	Tue Jun 23 12:28:03 2015 -0500
@@ -0,0 +1,88 @@
+// 1.3.38 Stack based implementation
+
+#ifndef GENERALIZEDQUEUE_HPP
+#define GENERALIZEDQUEUE_HPP
+
+#include <cassert>
+#include <cstddef>
+
+template <typename T>
+class GeneralizedQueue {
+
+private:
+
+    ////////////////////////////////////
+    class Node {
+    public:
+        T item;
+        Node *next;
+        };
+
+    ////////////////////////////////////
+
+public:
+    GeneralizedQueue( void );
+    bool is_empty( void );
+    void insert( T item );
+    T remove( size_t k );
+
+private:
+    Node *data;
+
+    };
+
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+GeneralizedQueue<T>::GeneralizedQueue( void ) :
+    data (nullptr)
+    {
+    }
+
+template <typename T>
+bool GeneralizedQueue<T>::is_empty( void ) {
+    return ! ( data == nullptr );
+    }
+
+template <typename T>
+void GeneralizedQueue<T>::insert( T item ) {
+    Node *node = new Node();
+    node.item = item;
+    node.next = nullptr;
+
+    if ( data == nullptr ) {
+        data = node;
+        }
+    else {
+        Node *curr = data;
+        while ( curr->next )
+            curr = curr->next;
+        curr->next = node;
+        }
+    }
+
+template <typename T>
+T GeneralizedQueue<T>::remove( size_t k ) {
+    assert( data != nullptr );
+
+    Node *prev = nullptr;
+    Node *curr = data;
+    size_t i = 0;
+    T item;
+    while ( i < k ) {
+        assert( curr->next );
+        prev = curr;
+        curr = curr->next;
+        }
+
+    if ( prev )
+        prev->next = curr->next;
+    else
+        data = curr->next;
+    item = curr->item;
+    delete curr;
+
+    return item;
+    }
+
+#endif