Lecture Overview

First, I finished talking about DualArrayDeque, specifically the analysis of the running time.

I then talked about memory management in C++ using new and delete. This is covered at the start of Chapter 4 of Thinking in C++ book.

Exercises

• Step 1: Extract the StringArrayStack structure out into a header file so that it can be removed. To do so, just copy the structure definition without the main function into a file called arraystack.h. Also, I realized that the StringArrayStack I implemented does not have a size method, so implement it to return n.

• Step 2: Implement a DualArrayDeque using the implementation of arraystack. Here is a template to get you started. You should be able to directly translate the pseudocode from the book into the implementation.

 #include <string>
 #include <iostream>
 #include <cassert>
 using namespace std;

 #include "arraystack.h"

struct StringDualArrayDeque {
    private:
        StringArrayStack *front;
        StringArrayStack *back;

    public:
        StringDualArrayDeque() {
            front = new StringArrayStack();
            back = new StringArrayStack();
        }

        ~StringDualArrayDeque() {
            delete front;
            delete back;
        }

        int size() {
            //for this to work you will have to write a size method for StringArrayStack
            return front->size() + back->size();
        }

        string get(int i) {
            //you write this, remember you can use the syntax front->get(100) to access methods through a pointer.
        }

        string set(int i, string x) {
            //you write this
        }

        void add(int i, string x) {
            //you write this
        }

        string remove(int i) {
            //you write this
        }

        void balance() {
            if (front->size() * 3 < back->size() || back->size() * 3 < front->size()) {
                StringArrayStack *new_front = new StringArrayStack();
                StringArrayStack *new_back = new StringArrayStack();

                //you implement the rebalance here

                delete front;
                delete back;
                front = new_front;
                back = new_back;
            }
        }

        void print() {
            cout << "Front" << endl;
            front->print();
            cout << "Back" << endl;
            back->print();
            cout << "--------------" << endl;
        }
};

int main() {
    StringDualArrayDeque d;

    //add code here to test that the ArrayDeque works
}

• Step 3: Think about where elements are stored in memory and all the pointers that exist. That is, starting from the variable d inside the main function, try drawing a diagram of memory regions, listing what data each region stores and arrows for the pointers. It might help if you added some printing functions which print memory locations, similar to how you were printing memory locations for the TICPP exercises.