Requirements:

In this sub-project, you will implement one class:

1. Navigation Stack: Navigation_stack.

A stack may be implemented using the linked list from Project 1 which allows appropriate insertions and deletions in O(1) time.

Runtime:

The run time of each member function is specified in parentheses at the end of the description.

Class Specifications:

Navigation_stack

Description

A class which implements an navigation stack (in fact, two stacks) which has the specified behaviours. For run-time requirements, the number of elements in the stacks is n.

Member Variables

The class has two members:

• Two singly-linked lists Single_list<Type> undo_stack and Single_list<Type> redo_stack.

Member Functions

Constructors

The default constructor is used.

Destructor

The default destructor is used.

Copy Constructor

Navigation_stack( Navigation_stack const & )

The copy constructor creates a new instance of the stack. (O(n))

Accessors

This class has two accessors:

bool can_undo() const

Returns true if the undo stack is not empty. (O(1))

bool can_redo() const

Returns true if the redo stack is not empty. (O(1))

Mutators

This class has six mutators:

void swap( Navigation_stack & );

The swap function swaps all the member variables of this stack with those of the argument. (O(1))

Navigation_stack &operator=( Navigation_stack & );

The assignment operator makes a copy of the argument and then swaps the member variables of this node with those of the copy. (O(max{n_lhs, n_rhs}))

void event( Type const & )

Push the element onto the top of the undo stack and empty the redo stack. (O(n))

Type undo()

Pop the top element off of the undo stack, push it onto the redo stack, and return the object. This may throw a underflow exception. (O(1))

Type redo()

Pop the top element off of the redo stack, push it onto the undo stack, and return the object. This may throw a underflow exception. (O(1))

void clear()

Removes all the elements in both stacks. (O(n))

Friends

The class has no friends.