queue.h
For this assignment you will be adding to the queue container from Homework #04. Specifically, you must add the ability to use the queue container with the STL functions requiring an iterator. This requires the addition of a queue iterator class, specifically designed to traverse the elements of the queue. For convenience, this iterator class is included within the queue class. The most basic form of iterator support requires the following. queue::begin() // constructs an iterator at the beginning of the queue queue::end() // constructs an iterator pointing "after" the end of the queue queue::iterator::operator++() // moves the iterator to the next location queue::iterator::operator*() // accesses the value that the iterator is currently pointing to In addition, a constructor for the iterator to be used with begin() and end() can be useful. I have provided the function queue::iterator::iterator(queue* q, int x) as one possible method of construction, if you think you require another post on Piazza. Note that the functions begin and end conflict with the variable names begin and end I used in Homework 4, and thus I have renamed those variables to front and back, which more clearly reference the line metaphor. Page 1 of 7 Once these functions have been implemented, you should be able to pass the following test case: int main() queue 93 q.push(10); q.push(20); q.push(30); for (int i :) std::cout #pragma once class queue private: int * arr; // begin and end were replaced by front and back, because begin and end are reserved by STL as function names int front; int back; int size; int capacity; public: // You'll need to add an iterator // I'm inheriting from std::iterator here to add the typedefs commented below so std::sort will compile, but it isn't strictly necessary. class iterator: public std::iterator<:random_access_iterator_tag int> public: // These typedefs are the things introduced by the inheritance from std::iterator, that std::sort fails to compile without //typedef iterator self_type; //typedef int value_type; //typedef int& reference; //typedef int* pointer; //typedef std::random_access_iterator_tag iterator_category; //typedef int difference_type; // location of the iterator in the queue int location; // reference to the queue so you have access to the current front, back, and size/capacity queue * obj; // You'll need to provide a constructor for begin() and end() iterator(queue* 9, int x); // operator++ is required to move the iterator to the next location iterator& operator++(); // operator-- required by std::sort, moving the iterator to the previous element iterator& operator--(); // operator* required to derefence the iterator and get at the value being referred to. int& operator*(); // required by std::sort, to tell whether two iterators point to the same location, and when end is reached bool operator==(const iterator other); // required by std::sort, to tell whether two iterators do not point to the same location bool operator !=(const iterator other); // required by std::sort, to traverse the structure more efficiently int operator-(const iterator & other) const; // required by std::sort, to traverse the structure more efficiently iterator operator-(int n); // required by std::sort, to traverse the structure more efficiently iterator operator+(int n); // required by std::sort, to identify which iterator is earlier in the structure, so smaller items can be swapped earlier bool operator #pragma once class queue private: int * arr; // begin and end were replaced by front and back, because begin and end are reserved by STL as function names int front; int back; int size; int capacity; public: // You'll need to add an iterator // I'm inheriting from std::iterator here to add the typedefs commented below so std::sort will compile, but it isn't strictly necessary. class iterator: public std::iterator<:random_access_iterator_tag int> public: // These typedefs are the things introduced by the inheritance from std::iterator, that std::sort fails to compile without //typedef iterator self_type; //typedef int value_type; //typedef int& reference; //typedef int* pointer; //typedef std::random_access_iterator_tag iterator_category; //typedef int difference_type; // location of the iterator in the queue int location; // reference to the queue so you have access to the current front, back, and size/capacity queue * obj; // You'll need to provide a constructor for begin() and end() iterator(queue* 9, int x); // operator++ is required to move the iterator to the next location iterator& operator++(); // operator-- required by std::sort, moving the iterator to the previous element iterator& operator--(); // operator* required to derefence the iterator and get at the value being referred to. int& operator*(); // required by std::sort, to tell whether two iterators point to the same location, and when end is reached bool operator==(const iterator other); // required by std::sort, to tell whether two iterators do not point to the same location bool operator !=(const iterator other); // required by std::sort, to traverse the structure more efficiently int operator-(const iterator & other) const; // required by std::sort, to traverse the structure more efficiently iterator operator-(int n); // required by std::sort, to traverse the structure more efficiently iterator operator+(int n); // required by std::sort, to identify which iterator is earlier in the structure, so smaller items can be swapped earlier bool operator
