Welcome to Week 3!


Learning Objectives
By the end of this class you should know...

  • What is a Queue?
  • What is a Stack?
  • FIFO and LIFO and how they apply to Queues and Stacks
  • The difference between a Queue and a Stack
  • Some applications of Queues
  • How to stub functions
  • How to write a Queue class


Announcements


Review Activity

  • With a partner, write removeIterator for a double linked list
    • Make sure your function handles precondition(s), edge case(s) and the general case.


Course Project


Introducing Stacks and Queues

  • Stacks and Queues are important ADTs.
  • Like Lists, Stacks and Queues (pronounced like the letter Q) are used to store data.
  • Their names are suggestive of their functionality.
  • queue is the British word for a line (like the line you wait in).
  • In Britain, people wait in queues rather than wait in lines.
  • Like a queue at the checkout in a super market, data inside Queues are organized according to the principle of first in, first out.
  • Customers insert themselves at the back of the queue.
  • 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

People standing in line

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

Stack of Dishes 2

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 Wednesday'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 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.
    • enqueue: adds an element to the back of the Queue, like the insert_last List function
    • dequeue: removes the element from the front of the Queue, like the remove_first function
    • getFront: returns the value of the element at the front of the Queue
    • print: prints the elements in the Queue in a specified way
    • getSize: returns the number of elements in the Queue
    • ==: tests whether two Queues are equal. 
    • constructor
    • copy constructor
    • destructor
  • There is no iterator for a Queue. Why do you think this might be?


Group Activity: Let's Act Out a Queue

  • We will need 4 volunteers who should organize themselves like the image below.
  • Then, we will need an additional volunteer or two to be enqueued.


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?


Group Activity: Drawing a Queue

  • Take out a sheet of paper.
  • Draw the following Nodes on your paper:
    • A Node containing the data "Sam". This Node is front of the Queue. It points to the Node containing the data "Chuck".
    • A Node containing the data "Chuck." This Node points to the Node containing "Arturo."
    • A Node containing the data "Arturo." This Node points to the Node containing "Liza."
    • A Node containing the data "Liza." This is the back of the Queue. It points to NULL. 
  • If you are unclear about how to draw this diagram, watch up front as the instructor will also draw it on the board.
  • Save this diagram as you will use it to help you write your Queue functions.

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 class.
  • What looks different?

#ifndef QUEUE_H_
#define QUEUE_H_

#include <iostream>
#include <cstddef>
#include <assert.h>
using namespace std;

template<class queuedata>
class Queue {
public:
    /**constructors and destructors*/

    Queue();
    //initializes an empty queue
    //post: an empty queue created with default values for all fields

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

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

    /**manipulation procedures*/

    void dequeue();
    //removes an element from the front of the queue
    //pre: size!=0
    //post: an element removed from the front of the queue

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

    /**accessors*/

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

    queuedata getFront() const;
    //returns the element at the front of the queue
    //pre: size != 0

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

    bool isEmpty() const;
    //returns whether the queue is empty

    /**additional queue operations*/
    void displayQueue(ostream& out) const;
    //prints the elements in the queue separated by a blank space

private:
    struct Node {

        queuedata data;
        Node* next;
        Node(queuedata d) {
            next = NULL;
            data = d;

        }
    };

    Node* front;
    Node* end;
    int size;

};

#endif /* QUEUE_H_ */




Group Activity: Drawing Enqueue and Dequeue

  • Take out your diagrams.
  • First step: We are going to enqueue the data "Sally" to our queue. Draw this process on your diagram, updating any necessary links.
  • Second step: We are going to dequeue. Draw this process on your diagram, also updating any necessary links.


Activity: Writing enqueue
  • Using the diagram as a guide, we are going to write the enqueue function.
  • Check yourself: Is this function an access function or manipulation procedure?
  • Also: Which of your List functions does this function resemble?
  • Try to write enqueue without looking at that List function.
  • Important: When you are finished, test your function inside of main.
  • You will want to test 3 situations:
  1. The queue is empty
  2. The queue has one element in it
  3. The queue has more than one element in it

Image source.




Pair Programming

What is Pair Programming?
  • Pair programming is a style of programming in which two people work together on one computer at the same time:
    • Exactly two people: not one nor three or more
    • Exactly one computer: not two or more
  • One person types the code and the other reviews each line of code as it is entered
  • The person using the mouse and keyboard is called the driver
  • The person reviewing is called the navigator
  • In addition to reviewing, the navigator:
    • Analyzes the design and code to prevent errors
    • Looks up reference materials like program syntax
  • Each person "drives" about half the time:
    • Physically get up and move positions when switching roles
  • At most 25% of your time is spent working alone:
    • Any work done alone is reviewed by the other person
  • The objective is to work together and to learn from each other
  • You cannot divide the work into two pieces with each partner working on a separate piece
  • If you are not both engaged in the process, you will not learn the material

For Lab 3 I will require you to pair program. Later, it will be optional (extra credit offered).


Why Pair Program?

  • Students who pair program report:
    • Higher confidence in a program solution
    • More satisfaction with programming
  • Instructors report higher completion and passing rates
  • Also: One of top attributes Google looking for in a job candidate is someone who works well on a team.

Video Explaining Pair Programming


Discuss Lab 3

  • For the rest of class: Work on Lab 3 with your partner.


Wrap Up
  • Answer the learning objective questions for this lesson.


Homework

Lab 3due one week from today!

  • Project Report 1 due in one week!
  • Quiz on Wednesday


~See You Wednesday!~