Under Construction!
(Content Subject to Change)

Lecture Covers

  • Queues
    • Stacks vs. Queues
    • Applications of Queues
    • STL Queue Class
    • Queue Implementation
  • Review
    • Writing Stubs
    • Overloading Operators
    • Exception Handling

Announcements

  • TBD


Review of Deep vs Shallow Copy

  • With a partner, answer the following questions (3 minutes):
    • What is a difference between a deep vs a shallow copy?
    • When writing a copy constructor, why do we need a deep copy?

Introducing Stacks and Queues

  • Stacks and Queues are important data structures.
  • Like Lists, Stacks and Queues (pronounced like the letter Q) are used to store data.
  • Their names are suggestive of their functionality.
  • A queue is the British word for a line. 
  • In other words, think: Waiting in a queue (waiting in line).
  • Like a queue at a a checkout, data inside Queues are organized according to the principle of first in, first out.
  • The first person in the Queue is the first person to be helped.
  • First in, first out is also known by the acronym FIFO.

A Queue


Concise Technologies, EFM fast broadbank reliable connection, cost effective leased line, one to one connection, same download and upload speed

Like this line of people, Queues are organized according to the principle of FIFO: first in, first out. Image source


  • In contrast, data in a stack are organized according to the principle of last in, first out.
  • Think of a stack of dishes at a cafeteria, where the first dish to be put in the stack is at the bottom and the last dish to be put in a stack is at the top. The dish placed at the top of the stack (the last one) will be the first one to be removed.
  • Last in, first out is also known by the acronym LIFO.

A Stack

A stack of dishes

Like this stack of dishes, Stacks are organized according to the principle of LIFO: last in, first out. Image Source

  • Today's lesson will focus on Queues, and Tuesday's will focus on Stacks.


Queues

Queue Basics

  • Data within the Queue are kept in the order in which they are added.
  • In fact, Queue operations are similar to those of the Linked List with some exceptions:
    • Unlike a linked list, only the data at the front of the Queue (the head) can be accessed.
    • Unlike a linked list, data can be added only at the back of the Queue.
    • Adding an element to the back of the Queue is called enqueuing the data.
    • Removing an element from the front of the Queue is called dequeuing the data.
    • These two operations are pronounced N-Q-ing and D-Q-ing, respectively.

Two important Queue operations: Enqueue and Dequeue. Image Source.


  • Similar Queue operations to those of the Linked List include:
    • empty: returns true if the Queue is empty and false otherwise.
    • clear: returns the Queue to the empty state
    • enqueue: adds an element to the back of the Queue
    • dequeue: removes the element from the front of the Queue
    • front: returns the value of the element at the front of the Queue
    • print: prints the elements in the Queue in a specified way
    • size: returns the number of elements in the Queue
    • equals: tests whether two Queues are equal. Note: we will go into some detail regarding this function.
    • constructor
    • copy constructor
    • destructor

Some Queue Applications

  • Operating systems use Queues to keep track of processes that are ready to execute or are waiting for a particular event to occur before they execute.
  • Requests for a shared resource such as the CPU or a printer are stored in a FIFO queue. Think of the documents in the queue for the printer at the computer lab. Who's document gets printed first?
  • Playlists on MP3 players.
  • Emails in your inbox.
  • Can you think of any others?

The Standard Template Library's Queue Class

  • The Standard Template Library offers other container classes, in addition to the List.
  • The STL also has a Queue and a Stack class.
  • The STL Queue operations are as follows:
constructor: Construct queue (public member function )
empty: Test whether container is empty (public member function )
size: Return size (public member function )
front: Access next element (public member function )
back: Access last element (public member function )
push: Insert element (public member function )
emplace: Construct and insert element (public member function )
pop: Remove next element (public member function )
swap: Swap contents (public member function)

Example Program Using STL Queue Class

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    //Declare a new queue.
    //Note the type of data to be stored in the queue goes in angled brackets
    queue<string> class_roster;
    cout << "Making class roster\n\n";
    class_roster.push("Lili");
    cout << "Inserting Lili" <<endl;
    class_roster.push("Marcos");
    cout << "Inserting Marcos\n";
    class_roster.push("Abdul");
    cout << "Inserting Abdul\n";
    cout << "First name on roster: ";
    cout << class_roster.front() << endl << "Calling pop function" << endl;

    class_roster.pop();
    cout << "First name on roster: ";
    cout << class_roster.front() << endl;
    cout << "Size of roster: ";
    cout << class_roster.size() << endl;

    return 0;
}


Writing Our Own Queue Class

The Header File

  • Copy and paste the following header file into a new file called Queue.h.
  • Then, turn off your screens.
  • The code below should look familiar now that you have written your own list classes.
  • What looks different?
template <class queuedata>
class Queue
{
    public:
        /**constructors and destructors*/

        Queue();
        //initializes an empty queue
        //postcondition: an empty queue

        Queue(const Queue &queue);
        //initializes queue to have same elements as another queue
        //postcondition: a copy of queue

        ~Queue();
        //frees memory allocated to the queue
        //postcondition: memory for queue has been freed

        /**manipulation procedures*/
        void clear();
        //returns queue to the empty state
        //postcondition: an empty queue

        void dequeue();
        //removes an element from the front of the queue
        //postcondition: an element has been removed from the front of the queue

        void enqueue(queuedata data);
        //adds an element to the back of the queue
        //postcondition: an element added to the back of the queue

        /**accessors*/

        bool operator==(const Queue &queue);
        //returns whether this queue is equal to another queue

        queuedata front();
        //returns the element at the front of the queue
        //precondition: the queue is not empty

        int size();
        //returns the size of the queue

        /**additional queue operations*/
        void print();
        //prints the elements in the queue in a programmer-specified format to stdout


    private:
        struct Node
        {
            queuedata data;
            Node* link;

            Node(): link(NULL), data(NULL){}
            Node(queuedata data): link(NULL), data(data){}

        }
        typedef Node* Nodeptr;

        Nodeptr front;
        Nodeptr back;
        int size;

}

Stubbing Functions
  • A function stub or simply stub is a piece of code used to stand in for some other programming functionality.
  • A stub may simulate the behavior of existing code or be a temporary substitute for yet-to-be-developed code.
  • Creating function stubs is a useful intermediary step in software development that allows you to compile your code and look for errors before writing your full function definitions.
  • For example:
int List::getSize()
{
    return -1;
}
  • The above function fulfills the requirements of the compiler that the function return an integer.
  • Thus, you can compile the program containing this stubbed out function and the compiler will not complain.
  • Another example:
void List::print()
{
    return;
        }


  • It is a good idea to write stubs for all of your class member functions and then compile your program to look for syntax errors in your header file and .cpp file before writing more complex code.
  • Stubs can also help you isolate syntax errors, because they help you to write each member function one-by-one and then compile after each one.
  • We will practice writing stubs in the next activity.

Activity 4.1: Stubbing Our Queue (8 minutes)
  • Get into your assigned pairs. You will be working with your partner on writing the Queue ADT for the rest of the class.
  • For this activity, you will be building the scaffolding for your Queue.cpp file.
  • First, make sure that you have saved the Queue.h file.
  • Then, copy and paste the function prototypes from Queue.h into a new file called Queue.cpp
  • Make sure you end up with proper indentation for your functions inside Queue.cpp.
  • Next, template all of your functions, as we learned at the end of the last lesson on Lists.
  • Finally, you will need to stub out all of your functions.
  • Compile your code and fix any errors.
  • Then, submit the stubbed out version of Queue.cpp.

Activity 4.2: Writing Queue Constructors (15 minutes)
  • In pairs, you are going to write the queue constructor, copy constructor and destructor.
  • After you write each function, compile your code. This process should work well now that you have your stubs!
  • Then, write you main function and try creating a new Queue and making a copy of this (empty) Queue with your copy constructor.
  • When you are finished, submit this version of your code.


Activity 4.3: Writing Queue Functions (15 minutes)
  • Now, write the following functions:
  1. clear
  2. dequeue
  3. enqueue <--- Hint: write this one second
  4. getFront
  5. getSize
  6. print <--- Hint: write this one first
  • These functions should all resemble your list functions
  • We will write equals together later in the class, so you can skip this one for now
  • After you write each function, test it inside of main
  • When you are finished, submit your code, including all 6 functions and 2 tests for each function.


Overloading Operators

Introducing Operator Overloading

  • When we are writing our own classes in C++, and we would like to be able perform operations such as arithmetic, making comparisons, etc, we have two options:
    •  We can write our own functions to handle these operations
    • We can overload the C++ operators
  • However, for many software engineers, overloading the C++ operators provides more elegance and readability.
  • For example, which do you find easier to read and understand?
object4 = object1 + object2 * object3;
OR
object4 = plus(object1, times(object2, object3);
  • Writing our own plus and times functions can make our code harder to read.
  • The + and * operators are easier to read.
  • In C++, the following 38 operators can be overloaded:

 +-
*
 /%
^
&
 |~
!
=
<
>
+=
 -=*=
/=
%=
^=
&=
 |=
 <<>>
<<=
 >>===
!=
<=
>=
&&
 ||++
--
 ->* ,
 ->[]
 ()new
new[]
delete
delete[]


How to Overload Operators

  • Operators can be overloaded in one of two ways:
  1. They can be defined as simple functions, separate from any class definition.
  2. They can be defined as member functions within the body of a class definition.
  • We are going to focus primarily on the second option for this lesson.
  • The following is a general formula for overloading operators:
return_type operatoroperator_symbol(parameters)
{
    //statements to redefine operator
}
  • Once we have redefined the operator, we can use it as normal.
  • For example:
class Line
{
    public:
        bool operator<(const Line &line);

    private:
        int length;
};

...

bool Line::operator<(const Line &line)
{
    if(length < line.length)
        return true;
    return false;
}


Example Program that Overloads the < Operator

/** Line.h file */

#ifndef LINE_H
#define LINE_H

#include<iostream>
using namespace std;

class Line
{
    public:
        Line();
        Line(int new_length);
        bool operator<(const Line &line);
    private:
        int length;

};

#endif // LINE_H


/** Line.cpp file */

#include "Line.h"

Line::Line():length(0){}
Line::Line(int new_length)
{
    length = new_length;
}

bool Line::operator<(const Line &line)
{
    if(length<line.length)
        return true;
    return false;
}

int main()
{
    Line line1(3);
    Line line2(4);
    if(line1 < line2)
    {
        cout << "It works!\n";
    }

    return 0;
}

Applying Operator Overloading to Our List Class

  • When we write our own classes, it is good practice to write an equals function so that we can compare two objects from the class.
  • We can use operator overloading to accomplish this task by overloading the == operator.
  • Let's look at an example using our List class from the last two lectures.
  • Let's add some code to override the == operator to compare two lists.
  • First, we will add a signature to our additional list operations in our List.h file:

        /**Additional List Operations*/

        bool operator==(const List &list);
        //Tests two lists to determine whether their contents are equal
        //Postcondition: returns true if lists are equal and false otherwise

  • Algorithm for testing for equality of two lists:
  1. Check if the sizes of the two lists are equal and, if not, return false
  2. Set the iterators to point to the head of each list
  3. While not offend of one of the lists
    1. Test whether the data at each node is equal
    2. If not, return false
    3. Move the iterators up by one node in each list
  4. Return true (you haven't return false yet, so the lists must be equal)
  • C++ code, overloading the equality operator for a linked list:


template <class listitem>
bool List<listitem>::operator==(const List& list)
{
    if(size != list.size)
        return false;
    iterator = head;
    NodeRef temp = list.head;
    while(iterator != NULL)
    {
        if(iterator->data !=temp->data)
            return false;
        temp = temp->next;
        iterator = iterator->next;
    }
    return true;
}

  • Then, in main, you could run tests like this one:
if(List1==List2)
      cout << "Lists are equal!\n";
else
      cout << "Lists are unequal!\n";


Activity 4.4: Overloading the Equality Operator for the Queue Class (5 minutes)
  • Now, it is your turn to overload the equality operator(==) for your Queue Class.
  • With you partner, add code to both your Queue.h and Queue.cpp classes to overload the equality operator.
  • Then, in your main function, test the operator for both an equal and unequal Queue to make sure your function is working properly.
  • Upload your code when you are finished.


C++ Exception Handling

Why Error Handling?

  • In programming, like in life, stuff happens!
  • An important part of any software engineer's job is handling error conditions and exceptional situations.
  • It is important to develop software that is tolerant of faults and able to recover gracefully when faced with errors.
  • There are various types of errors and exceptional situations:
  1. User input errors: the user enters input that does not follow the syntactic or semantic rules of the application. For example, the user enters a file name that does not exist or the user tries to access the first element in an empty list. (Sound familiar?)
  2. Device errors: A disk drive may be unavailable or a printer turned off or a device may fail in the middle of a task. For example, a printer may run out of paper during a printing job.
  3. Physical limitations: Disks can fill up or available memory may become exhausted.
  4. Component Failures: A function or class may perform incorrectly or use other functions or classes incorrectly.
  • Oftentimes, errors are out of a programmer's control. For example, programmers may have little control over how their software is ultimately used.
  • It is important to recognize that errors will occur and to plan ahead for them.
  • There are several techniques that programmers use to handle errors. We will look at them in the next section.

Some Techniques for Handling Errors

  • Printing an error message.  Below is an example of this technique:
void List::pop_front()
{
    if (head == NULL)
    {
        cout << "Cannot call pop_front on an empty list\n";
        return;
    }
    //rest of function
    }
   
   

This is a reasonable approach when debugging your own code or in smaller programs or course assignments. However, printing a message to standard out may not be sufficient in a large professional project where there may not be enough information about the cause of the problem to write an effective error message.
  • Special Return Values. Another approach is to have your function return a special value in the case of an error. For example, suppose we altered the above function to return a boolean rather than void. The function could return true if the function was able to delete the front value successfully and false otherwise:
bool List::pop_front()
{
    if (head == NULL)
    {
        cout << "Cannot call pop_front on an empty list\n";
        return false;
    }
    NodeRef temp = head;
    head = head->next;
    delete temp;
    return true; // head successfully deleted
    }

However, it will then be up to the programmer to check the return value (the source of another potential problem!) to see if it is true or false.

Additionally, it may not be possible to return a special value if your function is supposed to return an object such as a List. Or, the special value you return may be perfectly legal and valid. For example:

int List::front()
{
    if (head == NULL)
    {
        cout << "Cannot call front on an empty list\n";
        return -1;
    }
    //rest of function
    }

But, -1 could easily have been the value of the first element in the list.
  • Halting Execution with Assertions. We can call the assert() function to halt execution when we encounter an exceptional or error situation. For example:
#include <cassert>
...
int List::front()
{
    assert(head != NULL); //halts execution if head is NULL  
    return head->data;
    }

The assertion is a boolean expression that is evaluated at run time. If the expression evaluates to false, a diagnostic error message is printed and the program is halted. Typically this message is the text of the assertion that failed along with the file name and line number of the assertion.

However, the assertion mechanism can be turned off at the discretion of the the programmer, simply by setting a compiler switch. Also, halting execution of the program may be too radical of an approach to the problem encountered.

Exceptions
  • Since the exception mechanism was introduced into the C++ language, it has become the technique of choice when dealing with exceptional situations.

  • Exceptions provide a way to react to exceptional circumstances (like runtime errors) in programs by transferring control to special functions called handlers.
  • When a function detects an error, it can signal that there is an error condition to a handler by throwing an exception.
  • For example:
double divide(double num1, double num2)
{
    if (num2 == 0)
    {
        throw logic_error("Division by 0!");
    }
    return num1 / num2;
}
  • When the exception is thrown, the function executes immediately.
  • In this circumstance, the function does not return to its caller, but rather searches for a handler (an appropriate catch clause).
  • Once a handler is found, the code inside the handler is executed.

Catching Exceptions

  • The code under exception handling (e.g. the function that throws the exception) should be enclosed inside a try-catch block.
  • If any of the statements in the try block throws an exception, the exception should be caught and handled inside the catch block.
  • For example:

try
{
    double quotient = divide (2.3, 0);
}

catch(logic_error &error)
{
    cout << "Error occurred: " << error.what() << endl;
}

  • We must specify to the catch clause the type of exception to look for.
  • In our function, we threw a logic_error. Therefore, in our catch clause, we needed to catch a logic_error.
  • Note that logic_error here is an object. We will worry more about logic_error and other built-in exception classes in a few moments.
  • The what() function is a built-in function inside the C++ exception class. We will discuss it more in a few moments.
  • For now, just pay attention to the try-catch structure.
  • We can also catch multiple types of exceptions with multiple catch clauses in a single try-catch block. For example:

try
{
  // code here
}
catch (int param)
{
    cout << "int exception";
}
catch (char param)
{
    cout << "char exception";
}
catch (...)
{
    cout << "default exception";
}

  • In the code above, the exceptions are caught in the order of the catch blocks. The ellipsis ... indicates that this block should catch any exception.
  • Therefore, if you throw a type other than integer or character, it will be caught in the final catch block (default exception).

Values That Can Be Thrown

  • Why were we able to throw a c-string when we threw an exception in our functions of our list class?

int List::front()
{
    if (empty()) //using our newly-minted empty() function!
    {
        throw "List is empty! No first value!";
    }
   
    return head->data;
}

...

try
{
    int first_value = front();
    cout << first_value << endl;
}
catch (const char* msg)
{
    cout << msg << endl; //alert the user of the problem by printing the message
}

  • It turns out that we can throw many types of values as exceptions.
  • As another example, let's throw an integer inside our function:

double divide(double num1, double num2)
{
    if (num2 == 0)
    {
        throw -1;
    }
    return num1 / num2;
}

...

try
{
    double quotient = divide (2.3, 0);
}

catch(int a)
{
    cout << "Division by 0 error!" << endl;
}

  • However, if applicable, it is good practice to throw an object from one of C++'s built-in exception classes.
  •  C++ provides a list of standard exceptions defined in <exception> which we can use in our programs.
  • These are arranged in a parent-child class hierarchy shown below:

C++ Exceptions Hierarchy

  • You can read more about the type of exception for which each of these exception classes is designed in the C++ documentation.
  • We saw an example of throwing one of these predefined exception objects above.
  • Let's look at another example.

Standard Exception Example

  • Suppose we have the following function that allows us to access a particular item in our list via an index number.
  • For example, if we pass the function the value 5, it will give us back the data contained in the 5th node in our list.
  • Consider the following function. What could go wrong?

template <class listitem>
listitem getIndex(int index)
{
    iterator = head;
    for (int i = 0; i < index; i++)
    {
        iterator = iterator->next;
    }
    return iterator->data;
}

  • What will happen if our user wants to access the 5th index, but it doesn't exist yet?
  • Or, what if the user wants to access an impossible index, such as a negative index?
  • We need to throw an exception in anticipation of these problems.
  • Let's use one of the built-in exception classes.

template <class listitem>
listitem getIndex(int index)
{
    if (index > size || index < 1)
    {
        throw out_of_range("Index is off the end of the list.");
    }
    iterator = head;
    for (int i = 0; i < index; i++)
    {
        iterator = iterator->next;
    }
    return iterator->data;
}

  • Now, when the function is called, it needs to go inside of a try-catch block so we can catch the error.

#include<exception>

...

List<string> L;
L.push_back("Martians");
L.push_back("Minions");

try
{
    L.getIndex(5);
}
catch(out_of_range &offend)
{
    cout << offend.what() << endl;
}


Overriding the Standard Exception Classes

  • We can write our own exception classes by inheriting from the standard exception classes. 
  • Inheriting from standard exception allows us to customize our exceptions while still offering our users the ability to catch our exceptions using the plain vanilla std:exception.
  • Recall the diagram from above. Each of the built-in exception classes inherit from exception.

C++ Exceptions Hierarchy

  • We can write a custom exception class that also inherits from exception or any of the other exception classes
  • The key here is that we must override the exception::what() function.
  • The what() function has the following signature:

const char * what() const throw()

  • As an example, let's write our own exception class for our list called listexception that inherits from exception.
class listexception: public exception
{
    public:
        const char* what() const throw()
        {
            return "Illegal list operation";
        }

};

  • This is a very generalized exception class that can be thrown to handle any variety of list exception.
  • We can then provide a more specific error message about the source of the problem inside of our catch clause.
  • For example:

try
{
    int first_value = front();
    cout << first_value << endl;
}
catch (listexception &le)
{
    cout << le.what() << ": Unable to access first value of an empty list\n"; //custom message
}
  • To throw a listexception inside of our function, we will need to do the following:

template <class listitem>
listitem front()

{
    if (empty()) //using our newly-minted empty() function!
    {
        throw listexception();
    }
   
    return head->data;
}

Activity 4.5: Writing Your Own Queue Exception Class (15 minutes)

  • With you partner, write your own queueexception class that inherits from standard exception.
  • Don't forget to override the what() function.
  • Put your code inside of your Queue.h file.
  • Then, update any methods that are currently throwing an exception so that they throw a queueexception.
  • In your main function, update your try-catch blocks to print out the return value of the what() function as well as an appropriate message as in the example above.
  • Upload your code when you are finished.


More Information on Exceptions


Homework

  • Complete Lab 2
  • Assignment 1 Due Friday
  • Assignment 2