Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Stack class with Iterator
- *
- */
- template <class T>
- class Stack {
- private:
- // Define elements/nodes in the stack (unidirectional linked list)
- class StackElement {
- protected:
- T value;
- StackElement* next;
- public:
- StackElement(T value, StackElement* next) : value(value), next(next) { }
- ~StackElement() { ; } // nothing to be done
- friend Stack<T>;
- };
- // Pointer to the top of the stack
- StackElement* top;
- // height of the stack
- int size;
- StackElement* recursiveCopy(StackElement* current) {
- if ( current->next == 0 ) {
- return new StackElement(current->value, 0);
- }
- return new StackElement(current, recursiveCopy(current->next) );
- }
- public:
- // Define Iterator for the stack
- // The iterator allows the following code to traverse Stack s
- // for (Stack::Iterator si = s.begin() ; si != s.end() ; si++ ) {
- // si.value().do_stuff();
- // }
- class Iterator {
- private:
- StackElement* current;
- Stack<T>* my_stack;
- public:
- Iterator( Stack<T>* my_stack )
- : current(my_stack->top)
- , my_stack(my_stack)
- {}
- Iterator( const Iterator &that )
- : current(that.current)
- , my_stack(that.my_stack)
- {}
- // Constructor for Iterator at end
- Iterator( Stack<T>* my_stack, bool end )
- : current(0)
- , my_stack(my_stack)
- {}
- ~Iterator() { ; } // nothing to do, does not own pointers
- // Overload operators
- // Equality ==
- inline bool operator==(const Iterator &rhs) {
- if ( this->my_stack == rhs.my_stack && this->current == rhs.current ) {
- return true;
- }
- else {
- return false;
- }
- }
- // Inequlaity !=
- inline bool operator!=(const Iterator &rhs) { return !(*this == rhs); }
- // Increment ++
- inline Iterator &operator++(int) {
- current = current->next;
- return *this;
- }
- // Move the iterator to the top of the stack
- void begin() { current = my_stack->top; }
- // Move the iterator forward
- void advance() { current = current->next; }
- // Get the value of the element the iterator is pointing at
- T value() { return current->value; }
- };
- public:
- // Constructor: empty stack
- Stack<T>() : top(0), size(0) { }
- // Constructor: copy constructor
- Stack<T>(const Stack<T> &that) {
- if ( that.top == 0 ) {
- top = 0;
- size = 0;
- }
- else {
- top = recursiveCopy(that.top);
- size = that.size();
- }
- }
- // Destructor
- ~Stack<T>() {
- while(top != 0) {
- StackElement* temp = top;
- top = top->next;
- delete temp;
- }
- }
- // Push an element onto the stack
- void push(T value) {
- StackElement* element = new StackElement(value,top);
- top = element;
- size++;
- }
- // Pop an element off the stack
- // Assert: stack not empty
- T pop() {
- StackElement* popped = top;
- T return_value = popped->value;
- top = top->next;
- size--;
- delete popped;
- return return_value;
- }
- // Peek at the top element without popping it
- T peek() {
- return top->value;
- }
- // return true if stack size = 0
- bool empty() {
- if ( size == 0 ) { return true; }
- return false;
- }
- // return the height of the stack
- int height() { return size; }
- // return an Iterator to the top of the stack
- Iterator begin() { return Iterator(this); }
- // return an Iterator to the element past the end of the stack (null)
- Iterator end() { return Iterator(this, true); }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement