Mercurial > Algorithms__Sedgewick
view algs4-c++/src/GeneralizedQueue.hpp @ 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 | |
| children |
line source
1 // 1.3.38 Stack based implementation
3 #ifndef GENERALIZEDQUEUE_HPP
4 #define GENERALIZEDQUEUE_HPP
6 #include <cassert>
7 #include <cstddef>
9 template <typename T>
10 class GeneralizedQueue {
12 private:
14 ////////////////////////////////////
15 class Node {
16 public:
17 T item;
18 Node *next;
19 };
21 ////////////////////////////////////
23 public:
24 GeneralizedQueue( void );
25 bool is_empty( void );
26 void insert( T item );
27 T remove( size_t k );
29 private:
30 Node *data;
32 };
34 ////////////////////////////////////////////////////////////////////////////////
36 template <typename T>
37 GeneralizedQueue<T>::GeneralizedQueue( void ) :
38 data (nullptr)
39 {
40 }
42 template <typename T>
43 bool GeneralizedQueue<T>::is_empty( void ) {
44 return ! ( data == nullptr );
45 }
47 template <typename T>
48 void GeneralizedQueue<T>::insert( T item ) {
49 Node *node = new Node();
50 node.item = item;
51 node.next = nullptr;
53 if ( data == nullptr ) {
54 data = node;
55 }
56 else {
57 Node *curr = data;
58 while ( curr->next )
59 curr = curr->next;
60 curr->next = node;
61 }
62 }
64 template <typename T>
65 T GeneralizedQueue<T>::remove( size_t k ) {
66 assert( data != nullptr );
68 Node *prev = nullptr;
69 Node *curr = data;
70 size_t i = 0;
71 T item;
72 while ( i < k ) {
73 assert( curr->next );
74 prev = curr;
75 curr = curr->next;
76 }
78 if ( prev )
79 prev->next = curr->next;
80 else
81 data = curr->next;
82 item = curr->item;
83 delete curr;
85 return item;
86 }
88 #endif