Mercurial > Algorithms__Sedgewick

annotate algs4-c++/src/Queue.cpp @ 8:b02533162b6e

find changesets by author, revision, files, or words in the commit message
Linked list based Queue class.
author Eris Caffee <discordia@eldalin.com>
date Fri, 29 May 2015 21:13:32 -0500
parents
children eb159ea69f33
rev   line source
discordia@8 1 // g++ -D QUEUE_MAIN -std=c++0x Queue.cpp
discordia@8 2 // g++ -D QUEUE_MAIN -std=c++11 Queue.cpp
discordia@8 3
discordia@8 4
discordia@8 5 #include "Queue.hpp"
discordia@8 6
discordia@8 7 #include <cassert>
discordia@8 8 #include <cstddef>
discordia@8 9
discordia@8 10 #include <iostream>
discordia@8 11
discordia@8 12 template <typename T>
discordia@8 13 Queue<T>::Queue( void ) :
discordia@8 14 N (0),
discordia@8 15 first (nullptr),
discordia@8 16 last (nullptr)
discordia@8 17 {
discordia@8 18 }
discordia@8 19
discordia@8 20 template <typename T>
discordia@8 21 Queue<T>::~Queue( void ) {
discordia@8 22 assert( N == 0 ); // Catch the potential memory leak.
discordia@8 23 while ( first ) {
discordia@8 24 Node *next = first->next;
discordia@8 25 delete first;
discordia@8 26 first = next;
discordia@8 27 }
discordia@8 28 }
discordia@8 29
discordia@8 30 template <typename T>
discordia@8 31 void Queue<T>::enqueue( T &item ) {
discordia@8 32 Node * node = new Node();
discordia@8 33 node->item = item;
discordia@8 34 node->next = nullptr;
discordia@8 35
discordia@8 36 if ( last ) {
discordia@8 37 last->next = node;
discordia@8 38 last = node;
discordia@8 39 }
discordia@8 40 else {
discordia@8 41 last = first = node;
discordia@8 42 }
discordia@8 43
discordia@8 44 N++;
discordia@8 45 }
discordia@8 46
discordia@8 47 template <typename T>
discordia@8 48 T Queue<T>::dequeue( void ) {
discordia@8 49 assert( N > 0 );
discordia@8 50
discordia@8 51 T item = first->item;
discordia@8 52
discordia@8 53 Node *old = first;
discordia@8 54 first = first->next;
discordia@8 55 delete old;
discordia@8 56 N--;
discordia@8 57
discordia@8 58 if ( ! first )
discordia@8 59 last = nullptr;
discordia@8 60
discordia@8 61 return item;
discordia@8 62 }
discordia@8 63
discordia@8 64 template <typename T>
discordia@8 65 bool Queue<T>::is_empty( void ) {
discordia@8 66 return N == 0;
discordia@8 67 }
discordia@8 68
discordia@8 69 template <typename T>
discordia@8 70 size_t Queue<T>::size( void ) {
discordia@8 71 return N;
discordia@8 72 }
discordia@8 73
discordia@8 74 template <typename T>
discordia@8 75 typename Queue<T>::iterator Queue<T>::begin( void ) {
discordia@8 76 return Queue<T>::iterator( first );
discordia@8 77 }
discordia@8 78
discordia@8 79 template <typename T>
discordia@8 80 typename Queue<T>::iterator Queue<T>::end( void ) {
discordia@8 81 return Queue<T>::iterator( nullptr );
discordia@8 82 }
discordia@8 83
discordia@8 84
discordia@8 85 ////////////////////////////////////////////////////////////////////////////////
discordia@8 86
discordia@8 87 template <typename T>
discordia@8 88 Queue<T>::iterator::iterator( Node *c ) :
discordia@8 89 curr (c)
discordia@8 90 {
discordia@8 91 }
discordia@8 92
discordia@8 93 template <typename T>
discordia@8 94 typename Queue<T>::iterator & Queue<T>::iterator::operator++() {
discordia@8 95 if ( this->curr != nullptr ) {
discordia@8 96 this->curr = this->curr->next;
discordia@8 97 }
discordia@8 98 return *this;
discordia@8 99 }
discordia@8 100
discordia@8 101 template <typename T>
discordia@8 102 typename Queue<T>::iterator Queue<T>::iterator::operator++( int ) {
discordia@8 103 auto t = Queue<T>::iterator( *this );
discordia@8 104
discordia@8 105 if ( this->curr != nullptr ) {
discordia@8 106 this->curr = this->curr->next;
discordia@8 107 }
discordia@8 108 return t;
discordia@8 109 }
discordia@8 110
discordia@8 111 template <typename T>
discordia@8 112 T Queue<T>::iterator::operator*() {
discordia@8 113 return this->curr->item;
discordia@8 114 }
discordia@8 115
discordia@8 116 template <typename T>
discordia@8 117 bool Queue<T>::iterator::operator!=( typename Queue<T>::iterator other ) {
discordia@8 118 return this->curr != other.curr;
discordia@8 119 }
discordia@8 120
discordia@8 121
discordia@8 122 ////////////////////////////////////////////////////////////////////////////////
discordia@8 123
discordia@8 124 #ifdef QUEUE_MAIN
discordia@8 125
discordia@8 126 #include <iostream>
discordia@8 127
discordia@8 128 int main ( int argc, char **argv ) {
discordia@8 129
discordia@8 130 Queue<long> queue;
discordia@8 131
discordia@8 132 long i;
discordia@8 133 while ( ! std::cin.eof() ) {
discordia@8 134 std::cin >> i;
discordia@8 135 if ( std::cin.good() )
discordia@8 136 if ( i >= 0 )
discordia@8 137 queue.enqueue(i);
discordia@8 138 else
discordia@8 139 queue.dequeue();
discordia@8 140 }
discordia@8 141
discordia@8 142 std::cout << "Queue has " << queue.size() << " entries." << std::endl;
discordia@8 143
discordia@8 144 for ( auto iter = queue.begin(); iter != queue.end(); ++iter ) {
discordia@8 145 std::cout << *iter << std::endl;
discordia@8 146 }
discordia@8 147
discordia@8 148 std::cout << "Dequeuing entries..." << std::endl;
discordia@8 149
discordia@8 150 while ( ! queue.is_empty() ) {
discordia@8 151 i = queue.dequeue();
discordia@8 152 std::cout << i << std::endl;
discordia@8 153 }
discordia@8 154
discordia@8 155 std::cout << "Queue has " << queue.size() << " entries." << std::endl;
discordia@8 156
discordia@8 157 }
discordia@8 158
discordia@8 159 #endif