Requirements:

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

1. Dynamic dual stack: Dynamic_dual_stack.

A stack stores objects in an ordered list and allows insertions and deletions at one ends of the list in Θ(1) time. This class requires you to implement two stacks using a single array (one stack starting at each end) allowing pushes and pops from each stack. The stacks are identified by the integers 0 and 1.

The objects in these stacks are stored in a single array. The capacity of the array may be changed depending on the sum of number of objects stored in the two stacks according to the following two rules:

• If an object is being pushed onto a stack where the array is already full (the sum of the number of objects in both stacks equals the array capacity), the capacity of the array is doubled.
• If, after removing an object from a stack, the sum of the number of objects remaining in the two stacks is 1/4 the capacity of the array or less, then the capacity of the array is halved. The capacity of the array may not be reduced below the initially specified capacity.

Run Times:

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

Class Specifications:

---

Dynamic_dual_stack

Description

A class which implements two stacks using a single array. The capacity of the array may be changed dynamically after insertions or removals. For run-time requirements, the number of objects in both stack is n.

Member Variables

The class at least six member variables:

• A pointer to an instance of Type, Type *array, to be used as an array,
• Two size counters int stack_sizes[2],
• The initial capacity of the array, int initial_capacity, and
• The current capacity of the array, int array_capacity.

Member Functions

Constructors

Dynamic_dual_stack( int n = 10 )

The constructor takes as an argument the initial capacity of the array and allocates memory for that array. If the argument is either 0 or a negative integer, set the initial capacity of the array to 1. The default initial capacity of the array is 10. Other member variables are assigned as appropriate.

Destructor

~Dynamic_dual_stack()

The destructor deletes the memory allocated for the array.

Copy Constructor

Dynamic_dual_stack( Dynamic_dual_stack const & )

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

Accessors

This class has four accessors:

Type top( int m ) const

Return the object at the top of the m^th stack. If m is neither 0 nor 1, throw an illegal argument exception. It may throw a underflow exception. (Θ(1))

int size( int m ) const

Returns the number of objects currently stored in the m^th stack. If m is neither 0 nor 1, throw an illegal argument exception. (Θ(1))

bool empty( int m ) const

Returns true if the m^th stack is empty, false otherwise. If m is neither 0 nor 1, throw an illegal argument exception. (Θ(1))

int capacity() const

Returns the current capacity of the array. (Θ(1))

Mutators

This class has five mutators:

void swap( Dynamic_dual_stack & );

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

Dynamic_dual_stack &operator=( Dynamic_dual_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(n_lhs + n_rhs))

void push( int m, Type const & )

Insert the new object at the top of the m^th stack. If before the object is placed into the stack, the array is filled (the sum of the number of objects in the stacks equals the array capacity), the capacity of the array is doubled. If m is neither 0 nor 1, throw an illegal argument exception. (amortized Θ(1))

Type pop( int m )

Pop the object at the top of the m^th stack and return it. If after the object is popped off the stack, the array is less than or equal to a quarter full, the capacity of the array is halved, but not below the initial capacity. If m is neither 0 nor 1, throw an illegal argument exception. It may throw a underflow exception. (amortized Θ(1))

void clear()

Empties both stacks. If the array capacity has been increased, restore the capacity to the original size. (Θ(1))

Friends

The class has no friends.