Requirements:

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

1. A linked stack class: Linked_stack.

A linked stack may be implemented using the linked list from Project 1 which allows appropriate insertions and deletions in O(1) time. If your Project 1 did not work, you are welcome to use the implementation of a friend—only you must acknowledge that individual.

Runtime:

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

Class Specifications:

---

Linked_stack

Description

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

Member Variables

The class has four member variables:

• A linked list of pointers to arrays of Type: Single_list<Type *> array_list (or whatever linked list you created in Project 1),
• An integer storing the stack size, and
• One integer itop.

Each array in the linked list will have a capacity of eight. When the stack is empty, the linked list is empty. As objects are placed into the stack, they are placed into the arrays that will be stored in the linked list. As necessary, additional arrays are added to the linked list. For example, suppose we begin with an empty stack and then push five times and pop once. The result will appear as shown in Figure 1 where the member variables itop = 3.

Figure 1. The stack after five pushes and one pop.

Now, suppose that there is a sequence of fifteen pushes: when the array at the back of the linked list is filled, a new array is pushed onto the back of the linked list, and new entries are pushed into the array pointed to by that node. When this array also becomes filled, another array will be pushed onto the linked list. The member variable itop keeps track of the location in the top in the front array. As shown in Figure 2, itop = 2 and the linked list has three entries.

Figure 2. The stack in Figure 1 after another fifteen pushes.

Suppose next there is a sequence of ten pops. After the third pop, the node at the front of the linked list would be popped and the memory for the array it points to would be deallocated and itop would be reset to one less than the array capacity. After seve more pops, itop = 0, as shown in Figure 3.

Figure 3. The stack in Figure 2 after ten pops.

Member Functions

Constructors

The default constructor is used.

Copy constructor

Make a complete copy of the linked stack. For each array in the original linked list, a new array must be allocated and the entries copied over.

Destructor

The destructor will have to empty the linked list and deallocate the memory pointed to by the entries of the linked list.

Accessors

This class has three accessors:

bool empty() const

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

int size() const

Returns the number of objects currently in the stack. (O(1))

int list_size() const

Returns the number of nodes in the linked list data structure. This must be implemented as provided. (O(1))

Type top() const

Returns the object at the top of the stack. This member function may throw an underflow exception. (O(1))

Mutators

This class has four mutators:

void swap( Linked_stack & );

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

Linked_stack &operator=( Linked_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( Type const & )

Push the argument onto the back of the stack:

• If the stack is empty, allocate memory for a new array with the required capacity, push the address of that array onto the linked list, set both indices to zero and place the new argument at that location. The size of the stack is now one.
• If the back index already points to the last entry of the array, reset it to zero, allocate memory for a new array with the required capacity, push the address of that array onto the linked list, and insert the argument into the first location.
• Otherwise, increment the back index and place the argument at that location.

Increment the stack size. (O(1))

Type pop()

Pop the top of the stack and decrement the itop index. If the top index equals 0, reset it to the array capacity minus one and pop the top of the linked list while deallocating the memory allocated to that array. If the stack is emptied, also pop the front of the linked list while deallocated the memory allocated to that array. This member function may throw a underflow exception. (O(1))

Friends

The class has no friends.