Welcome to Week 3 - Lesson 5!
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 write a Queue class
1. 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 the next lesson will focus on Stacks.
2. Queues 2.1. 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:
- isEmpty: returns true if the Queue is empty and false otherwise.
- enqueue: adds an element to the back of the Queue, like the addLast List method
- dequeue: removes the element from the front of the Queue, like the removeFirst method
- getFront: returns the value of the element at the front of the Queue
- getLength: returns the number of elements in the Queue
- equals: determines whether two Queues are equal.
- toString: specifies how to print elements in the Queue
- constructor: instantiates a new Queue object with default values
- copy constructor: instantiates a new Queue object by making a copy of another Queue
- There is no iterator for a Queue. Why do you think this might be?
2.2. 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?
2.3. Group Activity: Drawing a Queue - Take out a sheet of paper.
- Draw the following Nodes on your paper:
- A Node containing the data "Alam". This Node is front of the Queue. It points to the Node containing the data "Arturo".
- A Node containing the data "Arturo." This Node points to the Node containing "Parveneh."
- A Node containing the data "Parveneh." This Node points to the Node containing "Weishi"
- A Node containing the data "Weishi." This is the end 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 methods.
3. Writing Our Own Queue Class 3.1. The Queue Class
- Open a new Java project in Eclipse called Lab3, then create a class called Queue.java (note the capitalization)
- Copy and paste the following code into Queue.java
- Also, create a test file by adding a second class named Lab3Test.java (notice the capitalization)
- The code below should look familiar now that you have written your own list class.
- What looks different? What looks the same?
/**
* Queue.java
* @author
* @author
*/
import java.util.NoSuchElementException;
public class Queue<T> {
private class Node {
private T data;
private Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
private int length;
private Node front;
private Node end;
/****CONSTRUCTORS****/
/**
* Default constructor for the Queue class
* @postcondition a new Queue object with all fields
* assigned default values
*/
public Queue() {}
/**
* Copy constructor for the Queue class
* @param original the Queue to copy
* @postcondition a new Queue object which is
* an identical, but distinct, copy of original
*/
public Queue(Queue<T> original) {}
/****ACCESSORS****/
/**
* Returns the value stored at the front
* of the Queue
* @return the value at the front of the queue
* @precondition !isEmpty()
* @throws NoSuchElementException when the
* precondition is violated
*/
public T getFront() throws NoSuchElementException {
return null;
}
/**
* Returns the length of the Queue
* @return the length from 0 to n
*/
public int getLength() {
return -1;
}
/**
* Determines whether a Queue is empty
* @return whether the Queue is emtpy
*/
public boolean isEmpty() {
return false;
}
/**
* Determines whether two Queues contain
* the same values in the same order
* @param o the Object to compare to this
* @return whether o and this are equal
*/
@Override public boolean equals(Object o) {
return false;
}
/****MUTATORS****/
/**
* Inserts a new value at the end of
* the Queue
* @param data the new data to insert
* @postcondition a new node at the end
* of the Queue
*/
public void enqueue(T data) {}
/**
* Removes the front element in the Queue
* @precondition !isEmpty()
* @throws NoSuchElementException when
* the precondition is violated
* @postcondition the front element has
* been removed
*/
public void dequeue() throws NoSuchElementException {}
/****ADDITONAL OPERATIONS****/
/**
* Returns the values stored in the Queue
* as a String, separated by a blank space
* with a new line character at the end
* @return a String of Queue values
*/
@Override public String toString() {
String result = "";
result += "\n";
return result;
}
}
3.2. Group Activity: Drawing Enqueue and Dequeue - Take out your diagrams.
- First step: We are going to enqueue the data "Zara" 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. Which name will be removed?
- Now try to write these two methods. Be sure to test them after you write each one!
Wrap Up
- Answer the review questions on Canvas for today's lesson
|
|
