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


~Have a Good Day!~