Mercurial > Algorithms__Sedgewick
changeset 11:846aeab17939
Added Steque (exercise 1.3.32)
author | Eris Caffee <discordia@eldalin.com> |
---|---|
date | Wed, 10 Jun 2015 13:21:26 -0500 |
parents | 8af1a61be7c1 |
children | 1e3c509b6ac4 |
files | algs4-c++/src/Steque.cpp algs4-c++/src/Steque.hpp |
diffstat | 2 files changed, 246 insertions(+), 0 deletions(-) [+] |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/algs4-c++/src/Steque.cpp Wed Jun 10 13:21:26 2015 -0500 1.3 @@ -0,0 +1,178 @@ 1.4 +// g++ -D STEQUE_MAIN -std=c++0x Steque.cpp 1.5 +// g++ -D STEQUE_MAIN -std=c++11 Steque.cpp 1.6 + 1.7 + 1.8 +#include "Steque.hpp" 1.9 + 1.10 +#include <cassert> 1.11 +#include <cstddef> 1.12 + 1.13 +#include <iostream> 1.14 + 1.15 +template <typename T> 1.16 +Steque<T>::Steque( void ) : 1.17 + N (0), 1.18 + list (nullptr) 1.19 + { 1.20 + } 1.21 + 1.22 +template <typename T> 1.23 +Steque<T>::~Steque( void ) { 1.24 + assert( N == 0 ); // Catch the potential memory leak. 1.25 + while ( list ) { 1.26 + Node * next = list->next; 1.27 + delete list; 1.28 + list = next; 1.29 + } 1.30 + } 1.31 + 1.32 +template <typename T> 1.33 +void Steque<T>::push( T &item ) { 1.34 + Node * node = new Node(); 1.35 + node->item = item; 1.36 + node->next = list; 1.37 + list = node; 1.38 + N++; 1.39 + } 1.40 + 1.41 +template <typename T> 1.42 +T Steque<T>::pop( void ) { 1.43 + assert( N > 0 ); 1.44 + 1.45 + T item = list->item; 1.46 + 1.47 + Node *old = list; 1.48 + list = list->next; 1.49 + delete old; 1.50 + N--; 1.51 + 1.52 + return item; 1.53 + } 1.54 + 1.55 +template <typename T> 1.56 +void Steque<T>::enqueue( T &item ) { 1.57 + Node *curr = list; 1.58 + 1.59 + Node *node = new Node(); 1.60 + node->item = item; 1.61 + node->next = nullptr; 1.62 + 1.63 + if ( ! curr ) { 1.64 + list = node; 1.65 + N++; 1.66 + return; 1.67 + } 1.68 + 1.69 + while ( curr->next ) { 1.70 + curr = curr->next; 1.71 + } 1.72 + 1.73 + curr->next = node; 1.74 + N++; 1.75 + 1.76 + return; 1.77 + } 1.78 + 1.79 +template <typename T> 1.80 +bool Steque<T>::is_empty( void ) { 1.81 + return N == 0; 1.82 + } 1.83 + 1.84 +template <typename T> 1.85 +size_t Steque<T>::size( void ) { 1.86 + return N; 1.87 + } 1.88 + 1.89 +template <typename T> 1.90 +typename Steque<T>::iterator Steque<T>::begin( void ) { 1.91 + return Steque<T>::iterator( list ); 1.92 + } 1.93 + 1.94 +template <typename T> 1.95 +typename Steque<T>::iterator Steque<T>::end( void ) { 1.96 + return Steque<T>::iterator( nullptr ); 1.97 + } 1.98 + 1.99 + 1.100 +//////////////////////////////////////////////////////////////////////////////// 1.101 + 1.102 +template <typename T> 1.103 +Steque<T>::iterator::iterator( Node *c ) : 1.104 + curr (c) 1.105 + { 1.106 + } 1.107 + 1.108 +template <typename T> 1.109 +typename Steque<T>::iterator & Steque<T>::iterator::operator++() { 1.110 + if ( this->curr != nullptr ) { 1.111 + this->curr = this->curr->next; 1.112 + } 1.113 + return *this; 1.114 + } 1.115 + 1.116 +template <typename T> 1.117 +typename Steque<T>::iterator Steque<T>::iterator::operator++( int ) { 1.118 + auto t = Steque<T>::iterator( *this ); 1.119 + 1.120 + if ( this->curr != nullptr ) { 1.121 + this->curr = this->curr->next; 1.122 + } 1.123 + return t; 1.124 + } 1.125 + 1.126 +template <typename T> 1.127 +T Steque<T>::iterator::operator*() { 1.128 + return this->curr->item; 1.129 + } 1.130 + 1.131 +template <typename T> 1.132 +bool Steque<T>::iterator::operator!=( typename Steque<T>::iterator other ) { 1.133 + return this->curr != other.curr; 1.134 + } 1.135 + 1.136 +//////////////////////////////////////////////////////////////////////////////// 1.137 + 1.138 + 1.139 + 1.140 +#ifdef STEQUE_MAIN 1.141 + 1.142 +#include <iostream> 1.143 + 1.144 +int main ( int argc, char **argv ) { 1.145 + 1.146 + Steque<long> steque; 1.147 + bool push_it = true; 1.148 + 1.149 + long i; 1.150 + while ( ! std::cin.eof() ) { 1.151 + std::cin >> i; 1.152 + if ( std::cin.good() ) { 1.153 + if ( push_it ) { 1.154 + steque.push( i ); 1.155 + push_it = false; 1.156 + } 1.157 + else { 1.158 + steque.enqueue( i ); 1.159 + push_it = true; 1.160 + } 1.161 + } 1.162 + } 1.163 + 1.164 + std::cout << "Steque has " << steque.size() << " entries." << std::endl; 1.165 + 1.166 + for ( auto iter = steque.begin(); iter != steque.end(); ++iter ) { 1.167 + std::cout << *iter << std::endl; 1.168 + } 1.169 + 1.170 + std::cout << "Popping entries..." << std::endl; 1.171 + 1.172 + while ( ! steque.is_empty() ) { 1.173 + i = steque.pop(); 1.174 + std::cout << i << std::endl; 1.175 + } 1.176 + 1.177 + std::cout << "Steque has " << steque.size() << " entries." << std::endl; 1.178 + 1.179 + } 1.180 + 1.181 +#endif
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 2.2 +++ b/algs4-c++/src/Steque.hpp Wed Jun 10 13:21:26 2015 -0500 2.3 @@ -0,0 +1,68 @@ 2.4 +#ifndef STEQUE_HPP 2.5 +#define STEQUE_HPP 2.6 + 2.7 +#include <cstddef> 2.8 + 2.9 +// Linked list based steque after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2 2.10 + 2.11 +template <typename T> 2.12 +class Steque { 2.13 + 2.14 +private: 2.15 + 2.16 + //////////////////////////////////// 2.17 + class Node { 2.18 + public: 2.19 + T item; 2.20 + Node *next; 2.21 + }; 2.22 + 2.23 + 2.24 +public: 2.25 + 2.26 + //////////////////////////////////// 2.27 + class iterator; 2.28 + friend class iterator; 2.29 + class iterator { 2.30 + 2.31 + public: 2.32 + 2.33 + iterator( Node *c ); 2.34 + 2.35 + iterator& operator++(); 2.36 + iterator operator++(int); 2.37 + 2.38 + T operator*(); 2.39 + bool operator!=( typename Steque<T>::iterator ); 2.40 + 2.41 + private: 2.42 + 2.43 + Node *curr; 2.44 + }; 2.45 + 2.46 + //////////////////////////////////// 2.47 + 2.48 + Steque( void ); 2.49 + ~Steque( void ); 2.50 + 2.51 + void push( T &item ); 2.52 + T pop( void ); 2.53 + void enqueue( T &item ); 2.54 + 2.55 + bool is_empty( void ); 2.56 + size_t size( void ); 2.57 + 2.58 + iterator begin( void ); 2.59 + iterator end( void ); 2.60 + 2.61 +private: 2.62 + 2.63 + size_t N; 2.64 + Node *list; 2.65 + 2.66 + }; 2.67 + 2.68 + 2.69 + 2.70 +#endif 2.71 +