Module 1: Stacks and Queues

Queues

A Queue is a list of ordered objects similar to LinkedList or ArrayList, but it handles inserts and removes differently. Unlike either of the previous two lists, in which data can be accessed by any node, queues follow a First-In-First-Out (FIFO) order. Imagine a line at the bank, the first person in line is the first one to be helped and then leave the line. Queues work in the same way.

Queue usage

FIFO order is helpful when you need to address information in the order that it enters the system. However, if you needed to access information in random order, then Queues would be a bad choice for object organization. Returning to the line at the bank, if people randomly walked out of the line to be helped, then the line would serve no purpose. A Queue makes it so that only the first and last elements in the list can be affected as shown in Figure 1 illustrates. If you need more flexibility, an ArrayList allows elements anywhere in the list to be changed or accessed.

Figure 1: An overview of a Queue. New items are added to the End of the Queue. Items are removed from the front of the queue.

Example: Printer queues

Let's look at another example: printers handle jobs in the order they are sent, so printers also follow FIFO order. When you turn on a printer, it has a queue started. Each job sent to the printer gets added to the end of the queue. As the printer completes a job, it removes it from the front of the queue and moves to the next job waiting to be completed. With this format, whichever job was submitted first is completed first, and then the printer moves to the next job assigned. This is an example of FIFO order.

Creating a Queue

Java's Queue interface provides methods to access its elements in FIFO order. In order to instantiate a Queue, we need a class that implements Queue. We want a list data structure that provides fast removal from the front and fast additions to the end.

Before we re-invent the wheel, let's check with the list data structures we know about. What about ArrayList? It handles the addition of elements at the end of the list in constant time, O(1), but what about removing the first element of an ArrayList? This requires shifting all of the elements to the left, which leads to a linear time, O(n), operation.

What about LinkedList? Just like an ArrayList, adding to the end of the list is fast. We point the tail to a new element and update the tail reference to our new element. This can be done in constant time, O(1). Can we do better than ArrayList when we remove from the front? We update our head pointer to the second element in the list, and we've successfully removed the first element in constant time, O(1).

Because LinkedList offers constant time operations for FIFO access, it is used when we construct a Queue.

Queue<E> is a generic interface just like List<E>. When you declare one you have to tell Java what type of elements you will store in your queue. Below we have constructed a Queue of PrintJobs for our printer example.

Queue<PrintJob> printJobs = new LinkedList<>();

Queues have two jobs, adding to the end of the queue and removing from the front, so we will focus our learning on the interface's add and remove methods. Queues also offer a few other methods for convenience that you can read about in the Javadoc if you would like to learn more.

Adding a Job

For a printer to complete a job, it must first receive a job. As stated above, our printer is using a Queue to handle the printing jobs in order, and so it is constantly checking its Queue for jobs. In order to get something printed, the PrintJob will need to be added to the Queue. We do this by using the add method as illustrated in Figure 2. According to the FIFO structure, anything added to a Queue is put at the end. This means that as more things are added to the Queue, they will be addressed after the objects earlier in the line are completed. When you use add, make sure you include whatever object you intend to put in the Queue within the parentheses.

The code for creating PrintJobs and adding them to the queue looks like the following:

Queue<PrintJob> printJobs = new LinkedList<>();

PrintJob cat = new PrintJob("~/Photos/cat.png");
PrintJob dog = new PrintJob("~/Photos/dog.png");

printJobs.add(cat);
printJobs.add(dog);

Figure 2: The process of adding items to our PrintJob Queue.

Removing a Job

The printer's Queue now contains jobs. How does the printer know which job to pick so that it is working on the one submitted first? In our example, cat is submitted first. The printer does not need to worry about selection order because it's Queue will always provide the jobs in the correct order. It just needs to call remove on the Queue to get the first job as shown in Figure 3. The element at the front of the queue will often be referred to as the head. This will return a PrintJob and remove it from the Queue. Since remove always takes from the front of the queue and cannot remove just any job, no arguments need to be specified within the parentheses.

The code for removing a job from the Queue looks like the following:

PrintJob catPrintJob = printJobs.remove();
PrintJob dogPrintJob = printJobs.remove();

Figure 3: The process of removing items from our PrintJob Queue.

If remove is called when the queue is empty, it will throw a NoSuchElementException. Queue's poll method also removes the head or returns null if the queue is empty.

Iterating over Jobs and more

Similar to Lists, you can iterate over items in a Queue using Iterators. You can also use for-each loops for iteration, as you would for Lists.

If you want to iterate over all elements in a Queue while removing elements, you can utilize the isEmpty method in a while loop, as follows:

while (!printJobs.isEmpty()) {
    PrintJob job = printJobs.remove();
    ...
}

Queue exposes other methods from Collection, such as clear, size, etc. To determine which methods are available via the Queue interface, check out the Queue Javadoc.

Runtime of Queue Operations

As discussed above, the linked list implementation of queues provide constant time, O(1), insertion and removal. Queues are not a good data structure choice if searches need to be performed on the data. To determine if an element is in a queue, you need to remove each element until you find the one you are seeking. In the worst case you are looking for an element near the back of the queue. This gives you linear time, O(n).

In reference to the printer, it does not need to search for the next job. The printer just needs to know the next job, and it looks at the head of the queue. Completed jobs are then removed and a new head comes available for the printer.

Putting it all together

Let's take a minute to look at our example of using queues. Here is the code for our PrintManager class that manages our print queue.

public class PrintManager {
    private Queue<PrintJob> printQueue;
    public PrintManager() {
        printQueue = new LinkedList<>();
    }

    public void addPrintJob(PrintJob toAdd) {
        printQueue.add(toAdd);
    }

    public PrintJob printNextJob(){
        return printQueue.remove();
    }

}

When an instance of our PrintManager is created, it makes a new instance of a LinkedList Queue that will be used to store the print jobs. The PrintJob class becomes a container to hold a reference to the file needing to be printed.

For the purposes of this example, we've simplified our PrintManager to have only two methods. The first method adds a PrintJob to our print Queue.

public void addPrintJob(PrintJob toAdd) {
    printQueue.add(toAdd);
}

The addPrintJob method accepts the PrintJob and uses the add method of the Queue to add the PrintJob to the end of the print queue. The add method always adds to the end of the Queue.

The second method in our PrintManager class is used when the printer is ready to print the next item. This printNextJob() method is designed to simply use the remove method from the Queue to remove the first item from the Queue and return it to the calling method.

public PrintJob printNextJob(){
    return printQueue.remove();
}

As soon as the printer is ready for a job and the PrintManager gives it to the printer (via printNextJob), there is no longer a need for that item to be in the queue anymore.

Adding to the back and removing from the front of the Queue are the primary use cases for the Queue interface. They are a great way to keep track of events, requests or other objects that need to be handled in the order they are received.

Queue Data Structure

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first item added to the queue is the first one to be removed.

Queue Operations

• Enqueue: Add an element to the end of the queue
• Dequeue: Remove and return the front element from the queue
• Peek/Front: Return the front element without removing it
• isEmpty: Check if the queue is empty
• Size: Return the number of elements in the queue

Common Applications

• Task scheduling in operating systems
• Print job queuing
• Breadth-first search algorithm
• Buffering in I/O operations

Java Implementation

// Linked list based queue implementation
public class LinkedQueue<T> {
    private static class Node<T> {
        T data;
        Node<T> next;
        
        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node<T> front;
    private Node<T> rear;
    private int size;
    
    public LinkedQueue() {
        front = rear = null;
        size = 0;
    }
    
    public void enqueue(T item) {
        Node<T> newNode = new Node<>(item);
        
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        
        T data = front.data;
        front = front.next;
        
        if (front == null) {
            rear = null;
        }
        
        size--;
        return data;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int size() {
        return size;
    }
}

Stacks

Stacks are another way of keeping ordered lists, while providing a different access pattern than Queues, LinkedLists, or ArrayLists. It restricts access to its elements in a similar way to a Queue rather than to LinkedList or ArrayList. Stack follows a specific access pattern called Last-In-First-Out (LIFO). If you imagine a tower of blocks, the last block you add to the tower is the only one that you can remove without disturbing the other tower blocks. To reach the very first block in the tower, each block on top of it must be systematically removed one by one. Stack works in the same way.

Uses of a stack

LIFO order is helpful when you need the most recent item added to the system. Like Queue, Stack preserves a specific ordering of data. It is not designed for easy access or removal of any item in the list only the most recently entered. If we return to the block example, pulling random blocks from the middle of the tower would cause it to tumble down. A Stack makes it impossible to pull from the middle of the list and protects a list's sequential integrity. Only the top element in the list can be accessed as shown in Figure 1.

Figure 1: Overview of a Stack. We push() Object #2 onto the top of the stack and then can pop() it off again.

Example: Undoing a mistake

When you write code, you make a mistake occasionally and want to undo your work. If you hit the undo button, it removes the last letter you typed because the software keeps track of your actions and can undo them at your request. Each key you type is added to the Stack sequentially. When you click undo, it deletes your key presses in the reverse order you entered them. The last key you pressed, is the first keystroke that is undone, which is an excellent example of LIFO.

Creating a stack

In Java Stack is a class, not an interface. Stack is a generic class, which requires us to declare the type of elements we will store in it when we instantiate it. Below we have constructed a Stack of Strings for our undo example.

Stack<String> pastTyping = new Stack<>();

Similarly to Queues, Stacks have two jobs: adding and removing. However, all changes are from the top of the stack only. For this lesson, we will focus our attention on the push() and pop() methods, which are the adding and removing vocabulary for a Stack. There are other methods provided by Stack that you can read about in the JavaDoc if you would like to learn more.

Push to add elements

Just like adding a block to our tower, The push method adds elements to the top of the stack. When you type in coding software, it uses push to add your keystrokes onto a stack as shown in Figure 2. The stack builds a sequential history stacking each element on the previous as shown in Figure 3 and Figure 4. When you push, be sure to include the object you intend to put on the stack within the method's parentheses. The code for creating and adding keystrokes to the Stack looks like the following:

Stack<String> pastTyping = new Stack<>();

String keyPress1 = "c";
String keyPress2 = "a";
String keyPress3 = "t";

pastTyping.push(keyPress1);
pastTyping.push(keyPress2);
pastTyping.push(keyPress3);

Figure 2: Adding the last letter typed ("c") onto the top of the Stack by using the push() method.

Figure 3: As the next letter "a" is pushed onto the top of the stack, the "c" now becomes the bottom of the Stack.

Figure 4: With the addition of the letter "t" being pushed onto the stack, "a" and "c" both get pushed further down. "c" is still the bottom of the stack.

Pop to remove elements

Now that the typing history stack contains keystrokes, you can remove them using the pop method. Unlike Queue's remove method, which removes the element that has been around the longest, pop removes the most recently added element as shown in Figure 5. When you press the undo button in your coding software, the program looks at the stack it has built of your keystrokes and pops off the most recent change. Similar to remove, you do not have to specify any parameters for pop because it only removes the item at the top of the stack.

The code for popping the most recently added keystroke off the Stack looks like the following:

String lastKeyPress = pastTyping.pop();

Figure 5: Calling pop() on our stack returns the item most recently added to the stack.

Calling pop on our stack returns the keystroke most recently added to the stack, and so the String variable lastKeyPressed is set to "t". If you hit undo again, the next most recently added item, "a", would pop off the stack as shown in Figure 6.

Figure 6: Calling pop() again on our stack returns the next most recently added item to the stack.

Keep in mind, if pop is called when the stack is empty it will throw an EmptyStackException. Stack does provide an empty method to test if the stack is empty. Be sure to either catch the exception or check if it's empty before you try to pop an item off the stack.

Iterate over elements and more!

Because Stack is a subinterface of List, you can iterate over a Stack using ListIterators. You can also use for-each loops for iteration, as you would for Lists.

If you want to iterate over all elements in a Stack while removing elements, you can utilize the isEmpty() method in a while loop, as follows:

while (!pastTyping.isEmpty()) {
    String lastKeyPressed = pastTyping.pop();
    ...
}

Stack exposes other methods from List, like size, clear, etc. To determine which methods Stack exposes, check out the Stack javadoc.

Runtime of stack operations

While Java has already implemented the Stack class for us, let's think about how we might implement it while optimizing for pushing and popping. We can use a list data structure that we restrict access to, by only providing ways to add and remove from the same end of the list. This is a great example of using composition to expose a contract that differs from its contained class! We could do this with either ArrayList or a LinkedList, since both provide efficient ways of adding/removing from one end of the list.

Let's explore the case of using a LinkedList a little deeper. We'll treat the front of the list as the top of our stack. When a call to push is made, we can call LinkedList's addFirst method to add the element to the top of the stack (front of the list). After the three push calls from above, our stack's underlying LinkedList would look like this:

Figure 7: LinkedList with three items.

The runtime of push is equivalent to LinkedList's addFirst method, which is constant, O(1). Regardless of the size of our list, adding to the front only requires an update to the head pointer, and linking our new node to the previous head.

For the call to pop, we want to remove the most recently added element. This will be at the front of our list. We can remove the first element in the list by calling LinkedList's remove method. After a call to pop, our stack's underlying LinkedList would look like this:

Figure 8: Our LinkedList after removing the head.

The runtime of pop is equivalent to LinkedList's remove method. Removing from the front of a LinkedList requires updating our head pointer to the second element in the list. This is done in constant time, O(1).

Putting it all together

Let's review the full example outlined for Stacks. Here is the code for a ChangeTracker class that a typing software could use to track changes you made to a document.

public class ChangeTracker {
    private Stack<String> pastTyping;
    public ChangeTracker() {
        pastTyping = new Stack<>();
    }

    public void addToStack(String textToAdd) {
        pastTyping.push(textToAdd);
    }

    public String undo() {
        return pastTyping.pop();
    }

}

When an instance of ChangeTracker is created, it generates a new instance of a Stack that will be used to store the keystrokes.

Remember, that Stacks are their own class and are initialized just like any other class.

For the purposes of this example, we simplified our ChangeTracker to have only two methods. In the first method, addToStack, the given String is pushed onto the Stack. In an actual program, these actions would likely be more complex, but for the sake of example we have simplified it to a single keystroke.

public void addToStack(String textToAdd) {
    pastTyping.push(textToAdd);
}

The other method in our ChangeTracker class is the method used to undo your last change. The undo() method is designed to simply use the pop() method from the Stack class to remove the most recently added item from the Stack and return it to the calling method.

public String undo() {
    return pastTyping.pop();
}

Pushing to and popping from the top of the Stack are the primary use cases for a stack. They are a great way to keep track of recent changes that need to be handled in the reverse order they are received.

Stack Data Structure

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last item added to the stack is the first one to be removed.

Stack Operations

• Push: Add an element to the top of the stack
• Pop: Remove and return the top element from the stack
• Peek: Return the top element without removing it
• isEmpty: Check if the stack is empty
• Size: Return the number of elements in the stack

Common Applications

• Function call stack in programming languages
• Undo functionality in applications
• Expression evaluation and syntax parsing
• Backtracking algorithms

Java Implementation

// Array-based stack implementation
public class ArrayStack<T> {
    private T[] array;
    private int top;
    private int capacity;
    
    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        array = (T[]) new Object[capacity];
        top = -1;
    }
    
    public void push(T item) {
        if (isFull()) {
            throw new StackOverflowError("Stack is full");
        }
        array[++top] = item;
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top--];
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public boolean isFull() {
        return top == capacity - 1;
    }
    
    public int size() {
        return top + 1;
    }
}

Java Collections Framework

Java provides built-in implementations for stacks and queues in the Collections Framework.

Stack Implementation

import java.util.Stack;

// Using Java's built-in Stack class
Stack<String> stack = new Stack<>();
stack.push("First");
stack.push("Second");
stack.push("Third");

// Outputs: Third
System.out.println(stack.pop());

// Outputs: Second
System.out.println(stack.peek());

Queue Implementation

import java.util.LinkedList;
import java.util.Queue;

// Using LinkedList as a Queue implementation
Queue<String> queue = new LinkedList<>();
queue.add("First");
queue.add("Second");
queue.add("Third");

// Outputs: First
System.out.println(queue.remove());

// Outputs: Second
System.out.println(queue.peek());

Performance Analysis

Understanding the time and space complexity of stack and queue operations is crucial for efficient algorithm design.

Stack Time Complexity

• Push: O(1)
• Pop: O(1)
• Peek: O(1)
• Search: O(n)

Queue Time Complexity

• Enqueue: O(1)
• Dequeue: O(1)
• Peek: O(1)
• Search: O(n)

Both data structures offer constant-time operations for their primary functions (adding and removing elements), making them highly efficient for their intended use cases.

Common Variations

Stack Variations

• Min/Max Stack: Keeps track of minimum/maximum values in stack
• Balanced Parentheses: Validates expression syntax
• Infix to Postfix Conversion: Converts human-readable expressions to machine-computable form

Queue Variations

• Double-ended Queue (Deque): Allows insertion and removal at both ends
• Priority Queue: Elements are dequeued based on priority rather than FIFO
• Circular Queue: Efficient use of fixed-size storage by wrapping around

Summary

Queues

Queues are great for any process where objects need to be addressed on a first-come-first-served basis. Adding to and removing values from a queue provide FIFO access to its elements. To create a queue in Java, we use the Queue<E> interface and the LinkedList<E> class. Access to the front of the queue is provided via the remove() method and the add() method allows addition to the end.

Stacks

Stacks, on the other hand, only have access to the last element added to the stack, providing the ability to access its objects in LIFO order. Stacks build a history as elements are added, which makes them valuable for processes that need to be able to undo or review previously seen items. In Java, Stack<E> is a class with two important methods: push() and pop(). These methods allow data to be added and removed only from the top of the stack.

Operation Runtimes

Queues	Stacks
add O(1)	push O(1)
remove O(1)	pop O(1)

Which is better?

Queues and stacks are both lists that have a specific way of inserting and removing objects. Due to the way they are set up, they have a constant access time since no searching needs to be done; there is only one way in and one way out. While this could lead one to believe they are essentially the same, they have very different uses. To focus on their use in programming, stacks lend themselves to working better with recursive logic since you peel away layer by layer off the stack. In contrast, queues work well with iterative logic by handling each object individually before moving on to the next.

Guided Project

"Stacks and Queues" is an instructor guided activity, so there is no README.

Mastery Task 2: Submit to the Process

We currently have an API to retrieve books, but we need a way to submit Kindle books for publishing so we can continue to grow our catalog!

Publishing a Kindle book is a long, multi-step process, so we can't complete the whole process within a single API call. To handle this, we've decided to save each book publish request into a class called BookPublishRequestManager that will allow requests to be processed later. That way the caller of SubmitBookForPublishing gets an immediate response with a publishingRecordId that they can use to check back on the status of their book publish request by calling GetPublishingStatus. This is similar to the workflow for orders on the Amazon retail website — you place an order and get an orderId back, which you can use later to check the current status of your order. This is known as asynchonous processing, since our service doesn't make the user wait until the entire publishing process completes.

The BookPublishRequestManager should manage a collection of book publish requests, ensuring that requests are processed in the same order that they are submitted.

You will need to do the following:

• Create the BookPublishRequestManager class in the com.amazon.ata.kindlepublishingservice.publishing package.
• The BookPublishRequest class has been provided to you in the com.amazon.ata.kindlepublishingservice.publishing package.
• Implement BookPublishRequestManager's addBookPublishRequest method which adds the given BookPublishRequest to the collection.
• Implement getBookPublishRequestToProcess which retrieves the next BookPublishRequest in line for publishing and returns it. If there are no requests to publish this should return null. This will be called in a later task when we implement processing the book publish requests.
• Since nothing is currently using the BookPublishRequestManager we don't need to update any Dagger classes yet. We can still set ourselves up with a more testable BookPublishRequestManager class by accepting any dependencies of our class into our constructor.

The SubmitBookForPublishingActivity currently only saves an item in the PublishingStatus table to record that we have received the book publish request to be processed. Now that you have the BookPublishRequestManager, finish the SubmitBookForPublishing operation by updating SubmitBookForPublishingActivity, to add BookPublishRequests to the manager for processing, based on the design doc's implementation notes and diagram.

We need to ensure we have added the correct Provider methods and annotated our constructors properly to make inject our BookPublishRequestManager. The service is already setup to use Dagger.

Finally, in order to make sure we only attempt to publish books in our catalog, you will need to add a new void method validateBookExists to the CatalogDao class, which the activity can call to check if the provided bookId exists in the catalog, and throws a BookNotFoundException if it doesn't. This is to meet the requirement in the design doc where the book's latest version in the catalog can be active or inactive, since we will allow users to publish a new version of an inactive book. Make sure to add additional unit tests for this case!

To test your new API, try submitting requests with a non-existant bookId, with an active bookId, and with an inactive bookId to ensure you are getting expected results back.

Run MasteryTaskTwoSubmitBookForPublishingTests to validate your changes.

Exit Checklist:

• You've built BookPublishRequestManager, which includes methods for adding and retrieving BookPublishRequests.
• You've updated SubmitBookForPublishingActivity according to the design doc, which allows books to be submitted for publishing and returns a response with a publishingRecordId.
• You added unit tests to cover your new code.
• MasteryTaskTwoSubmitBookForPublishingTests passes