Review

Inheritance is the ability to define a new class based on an existing class with a hierarchy. The new class (derived class) inherits data members and member functions of the existing class (base class).

New members and functions are added to the derived class. The new class only has to implement the behavior that is extra to the base class, and the code of the base class can be re-used in the derived class. Inheritance enables code re-use.

Inheritance implements the is-a relationship. Suppose Student class inherits from UPerson class,

• A Student object can be treated like a UPerson object.
• All member functions of UPerson can be called by a Student object.

In other words, a Student object is a UPerson object. In general, an object of the derived class can be treated like an object of the base class under all circumstsances.

Polymorphic or Liskov Substitution Principle

Function Expecting an Argument of Type	Will Also Accept
UPerson	Student
pointer to UPerson	pointer to Student
UPerson reference	Student reference

Initialization of Base Class objects

Suppose we have 3 classes, A, B and C.
C inherits B and B inherits A.

• If class C is derived from class B which is in turn derived from class A, then C will contain data members of both B and A.
• Class C's constructor can only call class B's constructor, and class B's constructor can only call class A's constructor.
• It is the responsibility of each derived class to initialize its direct base class correctly.

Example:

#include <iostream>
using namespace std;

// Base class
class Shape {
  // protected members are accessible in member functions of Shape and
  // in all the derived classes, including Rectangle
  protected:
    int width;
    int height;

  public:
    Shape() : width(0), height(0) {
      cout << "Default contor of Shape" << endl;
    }
    Shape(int width, int height) : width(width), height(height) {
      cout << "Other contor of Shape" << endl;
    }
    int getWidth() const  { return width; }
    int getHeight() const { return height; }
    void setWidth(int w)  { width = w; }
    void setHeight(int h) { height = h; }
};

// Derived class
class Rectangle : public Shape {
  public:
    // If a Shape class constructor is not exlicitly called using member initialization list
    // of Rectangle class, C++ compiler will implicitly call the default constructor of Shape for us.
    // That is the constructor, Rectangle() {}, will be implicitly changed to:
    // Rectangle() : Shape() {}
    Rectangle() {
      cout << "Default contor of Rectangle" << endl;
    }

    // It's the responsibility of Rectangle class to initialize its direct base
    // class, i.e. Shape, through member initialization list.
    // In this case, we put : Shape(width, height)
    Rectangle(int width, int height) : Shape(width, height) {
      cout << "Other contor of Rectangle" << endl;
    }

    int getArea() {
      // Can access inherited protected data members width and height
      return width * height;
    }
};

int main() {
  Rectangle rect1;
  cout << "Total area: " << rect1.getArea() << endl;
  cout << endl;

  Rectangle rect2(10, 20);
  cout << "Total area: " << rect2.getArea() << endl;
}

Output of the program:

Default contor of Shape
Default contor of Rectangle
Total area: 0

Other contor of Shape
Other contor of Rectangle
Total area: 200

Introduction

In this lab, we will implement DynamicArray and Deque based on List , which is a Linked List. Then, we will implement Stack and Queue based on Deque. For simplicity, we will implement them to store an int. We store each list element as a simple struct Node, which contains two properties: the node value int data, and a pointer Node* next pointing towards the next node. The last node in the list have next == nullptr.

Since a lot of the code would be reusable, especially the code related to inserting and deleting a Linked List node, we will make use of inheritance to reuse parent class methods.

Dynamic Array

A Dynamic Array is an array that can contain a variable number of elements. Insertion, deletion, reading and writing are all possible at any index position.

Deque

A Deque, or double-ended queue, is a data structure that supports a variable number of elements similar to a Dynamic Array. However, insertion, deletion and reading are only possible at the front and the back. Elements cannot be modified.

Queue

A Queue is similar to a Deque, with the restrictions that insertion is only possible at the back, while deletion and reading are only possible at the front. As with Deques, elements cannot be modified. Queues are known as "FIFO (First In First Out)" data containers. We typically refer to the "front" and "back" of the Queue, where "front" means the oldest element, and "back" means the latest element. We insert new values from the back of the queue and retrieve them from the front.

Stack

A Stack is similar to a Queue, except that it is "LIFO" (Last In First Out). In other words, we process the most recent item first. Instead of "front and back", we usually refer to the "top" of the Stack, which is the latest element. The "local variable stack" and "function call stack" are examples of this type of LIFO data structure. This can be seen with the behavior of function calls; we process the most recently called function before returning to the previous function.

Lab Work

Task 1 - List

The print() function is already provided to you in the skeleton code. Implement all other member functions of the List class.

• List(const List& rhs): Initializes the list as a copy of rhs, by deep-copying every Node.
• ~List(): Deletes all Nodes in the list.
• List& assign(const List& rhs): Copy the content of rhs by deep-copying every Node. Delete the existing array / nodes. At the end, return the current object as a reference.
• bool empty() const: Returns whether the list is empty.
• int size() const: Return the no. of nodes in the list.
• void insertAt(int data, int index): Inserts a new node containing data such that it becomes the index-th node.
• void removeAt(int index): Removes the index-th node.
• int get(int index) const: Returns the value of the index-th node.
• void set(int index, int data): Sets the value of the index-th node to data.

Note: for the methods requiring an index value (i.e. insertAt, removeAt, get and set), you can assume the index supplied is always valid. The same applies to all methods in the following tasks that call these methods.

Task 2 - DynamicArray

The print() function is already provided to you in the skeleton code. Implement all other member functions of the DynamicArray class. From this point on, try to reuse the suitable parent class methods as much as possible.

• DynamicArray(int array[], int size): Initializes the dynamic array such that it contains the same contents as array.
• int get(int index) const: Returns the value of the index-th node.
• void set(int index, int data): Sets the value of the index-th node to data.
• void push_back(int data): Inserts new value data at the back.

Task 3 - Deque

The print() function is already provided to you in the skeleton code. Implement all other member functions of the Deque class.

• void push_front(int data): Inserts data at the front.
• void push_back(int data): Inserts data at the back.
• void pop_front(): Removes the first item at the front.
• void pop_back(): Removes the last item at the back.
• int peek_front() const: Returns the first item, without changing the queue. If the queue is empty already, prints Empty! and return 0.
• int peek_back() const: Returns the last item, without changing the queue. If the queue is empty already, prints Empty! and return 0.

Task 4 - Stack

The print() function is already provided to you in the skeleton code. Implement all other member functions of the Stack class.

• void push(int data): Inserts data at the front.
• void pop(): Removes the first item at the front.
• int top() const: Returns the first item, without changing the queue. If the queue is empty already, prints Empty! and return 0.

Task 5 - Queue

The print() function is already provided to you in the skeleton code. Implement all other member functions of the Queue class.

• void push(int data): Inserts data at the back.
• void pop(): Removes the first item at the front.
• int peek() const: Returns the first item, without changing the queue. If the queue is empty already, prints Empty! and return 0.

Resources & Sample I/O

• Skeleton code: lab6_skeleton.zip
• Demo program: (Available soon)

Sample I/O

Note that in the program output, the data structures are always displayed from front to back.

Dynamic Array | Empty: N | Size: 4 | {1, 2, 3, 4}
Nodes: 1 2 3 4
Dynamic Array | Empty: N | Size: 4 | {1, 2, 3, 4}
Dynamic Array | Empty: N | Size: 4 | {7, 2, 3, 4}
Dynamic Array | Empty: N | Size: 4 | {7, 8, 3, 4}
Dynamic Array | Empty: N | Size: 4 | {7, 8, 9, 4}
Dynamic Array | Empty: N | Size: 4 | {7, 8, 9, 10}
Dynamic Array | Empty: N | Size: 5 | {7, 8, 9, 10, 11}
Dynamic Array | Empty: N | Size: 6 | {7, 8, 9, 10, 11, 12}
Deque | Empty: N | Size: 6 | <1><2><3><4><5><6>
Deque | Empty: N | Size: 5 | <2><3><4><5><6>
Deque | Empty: N | Size: 4 | <2><3><4><5>
Peek front: 2
Peek back: 5
Stack | Empty: Y | Size: 0 |
Stack | Empty: N | Size: 1 | <0]
Stack | Empty: N | Size: 2 | <1]<0]
Stack | Empty: N | Size: 3 | <2]<1]<0]
Stack | Empty: N | Size: 4 | <3]<2]<1]<0]
Stack | Empty: N | Size: 5 | <4]<3]<2]<1]<0]
Stack | Empty: N | Size: 4 | <3]<2]<1]<0]
Stack | Empty: N | Size: 3 | <2]<1]<0]
Stack | Empty: N | Size: 2 | <1]<0]
Stack | Empty: N | Size: 1 | <0]
Stack | Empty: Y | Size: 0 |
Peek: Empty!
0
Queue | Empty: Y | Size: 0 |
Queue | Empty: N | Size: 1 | <0]
Queue | Empty: N | Size: 2 | <0]<1]
Queue | Empty: N | Size: 3 | <0]<1]<2]
Queue | Empty: N | Size: 4 | <0]<1]<2]<3]
Queue | Empty: N | Size: 5 | <0]<1]<2]<3]<4]
Queue | Empty: N | Size: 4 | <1]<2]<3]<4]
Queue | Empty: N | Size: 3 | <2]<3]<4]
Queue | Empty: N | Size: 2 | <3]<4]
Queue | Empty: N | Size: 1 | <4]
Queue | Empty: Y | Size: 0 |
Peek: Empty!
0
End

Submission & Grading

Deadline: 7 November 2021 Sunday 23:59 HKT.
You may earn 1% course grade for this lab via Automated Grading on the ZINC Online Submission System.
Please compress and submit List.cpp, DynamicArray.cpp, Deque.cpp, Queue.cpp and Stack.cpp as lab6.zip to ZINC.

There will be two test cases for this lab. One of them is the same as the sample output above (see code in main.cpp) and the other one a hidden test case. The public test case is available on ZINC already and the hidden test case will be available ASAP.