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
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.
- A 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
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
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:
- The queue is empty
- The queue has one element in it
- 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
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
- 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!~
|
|
