Mercurial > Algorithms__Sedgewick
changeset 23:1198fe3684a6
1.3.38 Stack based implementation. Code not tested.
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Tue, 23 Jun 2015 12:28:03 -0500 |
parents | c2cbfdf528f6 |
children | 028689700a47 |
files | algs4-c++/1.3.38 algs4-c++/src/GeneralizedQueue.hpp |
diffstat | 2 files changed, 89 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/1.3.38 Tue Jun 23 12:28:03 2015 -0500 1.3 @@ -0,0 +1,1 @@ 1.4 +src/GeneralizedQueue.hpp 1.5 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/GeneralizedQueue.hpp Tue Jun 23 12:28:03 2015 -0500 2.3 @@ -0,0 +1,88 @@ 2.4 +// 1.3.38 Stack based implementation 2.5 + 2.6 +#ifndef GENERALIZEDQUEUE_HPP 2.7 +#define GENERALIZEDQUEUE_HPP 2.8 + 2.9 +#include <cassert> 2.10 +#include <cstddef> 2.11 + 2.12 +template <typename T> 2.13 +class GeneralizedQueue { 2.14 + 2.15 +private: 2.16 + 2.17 + //////////////////////////////////// 2.18 + class Node { 2.19 + public: 2.20 + T item; 2.21 + Node *next; 2.22 + }; 2.23 + 2.24 + //////////////////////////////////// 2.25 + 2.26 +public: 2.27 + GeneralizedQueue( void ); 2.28 + bool is_empty( void ); 2.29 + void insert( T item ); 2.30 + T remove( size_t k ); 2.31 + 2.32 +private: 2.33 + Node *data; 2.34 + 2.35 + }; 2.36 + 2.37 +//////////////////////////////////////////////////////////////////////////////// 2.38 + 2.39 +template <typename T> 2.40 +GeneralizedQueue<T>::GeneralizedQueue( void ) : 2.41 + data (nullptr) 2.42 + { 2.43 + } 2.44 + 2.45 +template <typename T> 2.46 +bool GeneralizedQueue<T>::is_empty( void ) { 2.47 + return ! ( data == nullptr ); 2.48 + } 2.49 + 2.50 +template <typename T> 2.51 +void GeneralizedQueue<T>::insert( T item ) { 2.52 + Node *node = new Node(); 2.53 + node.item = item; 2.54 + node.next = nullptr; 2.55 + 2.56 + if ( data == nullptr ) { 2.57 + data = node; 2.58 + } 2.59 + else { 2.60 + Node *curr = data; 2.61 + while ( curr->next ) 2.62 + curr = curr->next; 2.63 + curr->next = node; 2.64 + } 2.65 + } 2.66 + 2.67 +template <typename T> 2.68 +T GeneralizedQueue<T>::remove( size_t k ) { 2.69 + assert( data != nullptr ); 2.70 + 2.71 + Node *prev = nullptr; 2.72 + Node *curr = data; 2.73 + size_t i = 0; 2.74 + T item; 2.75 + while ( i < k ) { 2.76 + assert( curr->next ); 2.77 + prev = curr; 2.78 + curr = curr->next; 2.79 + } 2.80 + 2.81 + if ( prev ) 2.82 + prev->next = curr->next; 2.83 + else 2.84 + data = curr->next; 2.85 + item = curr->item; 2.86 + delete curr; 2.87 + 2.88 + return item; 2.89 + } 2.90 + 2.91 +#endif