Linked Stack and Dynamic Queue

Requirements

In this project, you will implement four classes:

1. Singly linked list: SingleList, and
2. Singly linked nodes: SingleNode
3. Dynamic queue: DQueue.
4. Linked queue: LStack.

A skeleton header files for these classes is provided with the associated class. You may modify these files for the project, though you must add your own comments. Do not copy text from the specifications. Testing tools for some of the classes provided in the associated testing directory. Included is a simple exception header file which contains two classes, underflow and overflow which are thrown by some of the member functions.

Failure to satisfy the stated run times will result in a mark of 0.

You are required to submit within your zipped file the following header files:

• DQueue.h
• LStack.h
• SingleList.h
• SingleNode.h

Be sure to read the instructions on the Projects page with regard to the submission of projects.

Runtime

The run time of each member function is specified in parentheses at the end of the description. In some cases, the run-time requirements are expressed as amoritized run-time requirements.

Comments

You are expected to comment your code. At least 20% of your source code must be in the form of valid and informative comments. As you will use this class in future projects, it is advisable to comment it appropriately. You are also expected to comment the provided bare header files.

Testing

One test file is provided, however, it is by no means a complete.

Testing Strategies

In this case, there are multiple boundary conditions: when the list empties, when the array is 1/4 full, when it is empty, and when the array is full. Each function should be tested with function class which cause it to manipulate both an empty lists and arrays and non-empty list and arrays.

Look at each function which has an if statement. Try to create a sequence of instructions which cause the conditional statement to evaluate to true. Next, do the same thing, however, create a sequence of instructions which will cause the conditional to evaluate to false.

What are other possible scenarios which could cause your classes to fail?

Testing Example

Rather than immediately starting with the *Driver.cpp program, it is probably a lot easier to write a small int main() function which you can build up. Each time you implement a function, add a function which tests it.

A smaller routine like this would allow you to make full and effective use of the debugger: you can easily track what is occuring. Notice how I test some of the functions, but not all, based on the order in which I would implement them.

Singly linked list

Requirements

In this sub-project, you will implement and use two classes:

1. Singly linked lists: SingleList, and
2. Singly linked nodes: SingleNode.

A singly linked list with three nodes is shown in Figure 1. The empty list is shown in Figure 2.

Figure 1. A singly linked list three nodes. see image.

Figure 2. An empty singly linked list. see image.

Class Specification

UML Class Diagram: see image.

Description

This class stores a finite list of n (zero or more) elements stored in singly linked nodes. If there are zero elements in the list, the list is said to be empty. Each element is stored in an instance of the SingleNode< Type> class. If the list is empty, the head and tail pointers are assigned nullptr. Otherwise, the head pointer points to the first node, the tail pointer points to the nth node, the next pointer of the ith node (1 <= i < n) points to the (i + 1)st node, and the next pointer of the nth is assigned 0.

Member Variables

The three member variables are:

• Two pointers to SingleNode< Type> objects, referred to as the head pointer and tail pointer, respectively, and
• An integer referred to as the list size which equals the number of elements in the list.

Member Functions

Constructors

SingleList()

This constructor sets all member variables to 0 or nullptr, as appropriate. (O(1))

Destructor

The destructor must delete each of the nodes in the linked list. (O(n))

Copy Constructor

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

Accessors

This class has seven accessors:

int size() const;

Returns the number of items in the list. (O(1))

bool empty() const;

Returns true if the list is empty, false otherwise. (O(1))

Type front() const;

Retrieves the object stored in the node pointed to by the head pointer. This function throws a underflow if the list is empty. (O(1))

Type back() const;

Retrieves the object stored in the node pointed to by the tail pointer. This function throws a underflow if the list is empty. (O(1))

SingleNode< Type> *head() const;

Returns the head pointer. (O(1))

SingleNode< Type> *tail() const;

Returns the tail pointer. (O(1))

int count( Type const & ) const;

Returns the number of nodes in the linked list storing a value equal to the argument. (O(n))

Mutators

This class has six mutators:

void swap( SingleList & );

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

SingleList &operator=( SingleList & );

The assignment operator makes a copy of the argument and then swaps the member variables of this singly linked list with those of the copy. (O(n _lhs + n _rhs ))

void push_front( Type const & );

Creates a new SingleNode< Type> storing the argument, the next pointer of which is set to the current head pointer. The head pointer is set to this new node. If the list was originally empty, the tail pointer is set to point to the new node. (O(1))

void push_back( Type const & );

Similar to push_front, this places a new node at the back of the list. (O(1))

Type pop_front();

Delete the node at the front of the linked list and, as necessary, update the head and tail pointers. Return the object stored in the node being popped. Throw an underflow exception if the list is empty. (O(1))

int erase( Type const & );

Delete the first node (from the front) in the linked list that contains the object equal to the argument (use == to to test for equality with the retrieved element). As necessary, update the head and tail pointers and the next pointer of any other node within the list. Return the number of nodes that were deleted. (O(n))

Singly linked node

Requirements

In this sub-project, you will implement the class SingleNode.

A singly linked node contains two member variables: an element and a pointer to another singly linked node. Figure 1 shows a singly linked list which contains three nodes.

Figure 1. A singly linked list three nodes. see image.

Class Specifications

UML Class Diagram: see image.

Description

A class which stores an object and a pointer to the next node in a linked list.

Member Variables

The two member variables are:

• An Type, referred to as the element of the node, and
• A pointer to a SingleNode object, referred to as the next pointer.

Member Functions

Constructors

SingleNode( Type const &, SingleNode * )

This constructor takes two arguments: a constant reference to an Type (by default, a new instance of the type Type) and a pointer to a SingleNode (by default nullptr). These are assigned to the member variables, respectively. (O(1))

Destructor

This class uses the default destructor.

Copy Constructor

This class uses the default copy constructor.

Accessors

This class has two accessors, one to get each of the two associated member variables:

Type retrieve() const

Returns the element of the node. (O(1))

SingleNode *next() const

Returns the next pointer. (O(1))

Mutators

This class has no member functions which modify the member variables.

Friends

The classes SingleList< Type>, is a friends of this class.

Dynamic queue

Requirements

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

1. Dynamic Queue: DQueue.

A queue stores objects in an ordered list and allows insertions at one end and deletions from the other end of the list in O(1) time.

The objects in this queue are stored in an array. The capacity of the array may be changed depending on the number of objects currently stored in the array, according to the following two rules:

• If an object is being inserted into a queue where the array is already full, the capacity of the array is doubled.
• If, after removing an object from a queue where the number of objects is one-quarter (1/4) the capacity of the array, then the capacity of the array is halved. The capacity of the array may not be reduced below the initially specified capacity.

Runtime:

The amortized run time of each member function is specified in parentheses at the end of the description. Projects which do not satisfy the run time requirements will be required to resubmit.

Class Specifications:

DQueue

Description

A class which implements a queue using an array. The capacity of the array may be changed dynamically after insertions or deletions. For run-time requirements, the number of objects in the queue is n.

Member Variables

The class at least six suggested member variables:

• A pointer to an instance of Type, Type *array, to be used as an array,
• A head index int ihead,
• A tail index int itail,
• A counter int entry_count,
• The initial capacity of the array, int initial_capacity, and
• The current capacity of the array, int array_capacity.

You may chose to use these or use whatever other member variables you want. You do not have to use all of these member variablesit is possible to implement this class using two of the three integer member variables; however, this requires more computation for the individual member functions.

Member Functions

Constructors

DQueue( 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

~DQueue()

The destructor deletes the memory allocated for the array.

Copy Constructor

DQueue( DQueue const & )

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

Accessors

This class has four accessors:

Type head() const

Return the object at the head of the queue (the object that would be removed by Type dequeue() ). It may throw a underflow exception). (O(1))

int size() const

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

bool empty() const

Returns true if the queue is empty, false otherwise. (O(1))

int capacity() const

Returns the current capacity of the queue. (O(1))

Mutators

This class has five mutators:

void swap( DQueue & );

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

DQueue &operator=( DQueue & );

The argument is a copy of the right-hand side of the operator. Swap the member variables of this with that copy.

void enqueue( Type const & )

Insert the argument at the tail of the queue. If the array is full before the argument is placed into the queue, the capacity of the array is first doubled. (O(1) on average)

Type dequeue()

Removes the object at the head of the queue. If, after the object is removed, the array is one-quarter (1/4) full and the array capacity is greater than the initial capacity, the capacity of the array is halved. This will throw the underflow exception if the queue is empty. (O(1) on average)

void clear()

Empties the queue by resetting the member variables. The array is resized to the initial capacity. (O(1))

Friends

The class has one friend: the operation cout << queue . Because the structure of the internal queue is unknown, nothing is implemented here; however, you could add an implementation which allows you to print the entries of your queue.

Linked stack

Requirements

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

1. A linked stack class: LStack.

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 friendonly 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:

LStack

Description

A class which implements a linked stack (in fact, two stacks) which has the specified behaviors. 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: SingleList< Type *> array_list
• 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. see image.

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. see image.

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 seven more pops, itop = 0, as shown in Figure 3.

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

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( LStack & );

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

LStack &operator=( LStack & );

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.