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 QueueTest.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
|
|