Stacks and Queues

Table of contents

1. Data abstraction
2. Lists
3. Stacks
4. Queues

Data abstraction

Last week, we saw how the Balance class represented an example of abstraction.

The Balance class defines public methods so that other programs written by anyone, anywhere, at anytime before or after it can rely on its functionality as long as they know how to interface with it.

The public methods of the Balance class represent a functional abstraction since they allow clients to use the Balance class without understanding its implementation details.

Earlier, we defined ArrayIntList as a collection that can be used to store a list (ordered sequence) of integer data and introduced the concept of a class invariant.

ArrayIntList class invariant

The i-the item in the list is always stored at elementData[i].

The wording is deliberate: the list concept is separate from the underlying elementData array. The other indices of the elementData may contain any values. An ArrayIntList implements the list concept with an int[]. ArrayIntList is an example of data abstraction.

ArrayIntList data abstraction

The separation of the list concept (client view) from the underlying array (implementer view).

Abstract data type (ADT)

The concept of a list as an ordered sequence with operations such as add, remove, and indexOf.

Data structure

The underlying array that the implementer must maintain so that the client can use ArrayIntList as a list.

ArrayIntList is a Java class that binds these two concepts: the list abstract data type that informs the client how to use the class and the array data structure that actually provides the behaviors for the class’s public methods. Next, we’ll introduce the idea of different abstract data types and see what happens. In the coming weeks, we’ll see how (and why) we might also want to switch out the data structure too.

Lists

The list abstract data type represents an ordered sequence of elements.

• add an element to any given index in the list (shifting right subsequent elements as necessary).
• get to return the element at any given index in the list.
• remove the element at any given index in the list (shifting left subsequent elements as necessary).
• size to return the number of elements in the list.

In this lesson, we’ll contrast lists with stacks and queues. Stacks and queues are simpler than lists: in fact, lists can do everything that stacks can do and also everything that queues can do too.

It might seem a bit unintuitive why programmers would prefer data types that do fewer things rather than data types that do more things.

Interface types

Java provides classes and interfaces for many different collections and abstract data types in the java.util package. To use them, add an import statement to the top of each Java file.

import java.util.*;

The java.util package represents abstract data types as interfaces and concrete implementations as classes. For example, instead of declaring ArrayIntList list = new ArrayIntList();, the better approach is to use the interface type List on the lefthand side of the assignment statement.

List<String> list = new ArrayList<String>();

This line of code creates a new ArrayList<String> (righthand side) and assigns it to a local variable of type List<String> (lefthand side). We’ll later see that there are other ways of implementing the List interface with different tradeoffs, so it’s useful to write client code using the general interface type where possible so that the implementation can be changed if necessary later on.

Wrapper classes

To store a list of integers using Java’s ArrayList class, we might write the following line of code.

List<int> list = new ArrayList<int>();

This doesn’t work because Java disallows primitive types such as int and double from being used as the specialized type. Instead, specialized types need to be classes such as String. Java provides wrapper classes to represent primitive values as objects. For example, the wrapper class for int is called Integer. We can declare a list of integers as follows.

List<Integer> list = new ArrayList<Integer>();

Java will conveniently convert between the primitive type and the wrapper class automatically most of the time, so we can use the primitive type everywhere else.

List<Integer> list = new ArrayList<Integer>();
list.add(1);
int first = list.get(0);

Stacks

The stack abstract data type allows adding and removing elements from the “top” of the stack. Imagine a stack of plates. The most common of way of interacting with the stack of plates is to add a plate to the top or remove a plate from the top.

• push an element to the top of the stack.
• pop to remove and return the top element from the stack.
• peek to return but not remove the top element from the stack.
• size to return the number of elements in the stack.

Consider the following code snippet.

Stack<String> stack = new Stack<String>();
stack.push("puppy");
stack.push("cat");
stack.push("dog");
System.out.println(stack.pop());

The first element removed by stack.pop() is “dog” since “dog” was at the top of the stack.

There’s one weird detail about stacks in Java. Stacks are an abstract data type, so they aren’t necessarily tied to one specific data structure implementation. Unfortunately, Java’s Stack class has a critical design flaw: it’s a class, not an interface. This means that the left hand side and right hand side of an assignment statement will both be declared with the Stack class, rather than using an interface type.

Note

The Java Stack class has many other methods beyond push, pop, peek, size, and isEmpty, but they’re off-limits for this course since they aren’t part of the stack ADT. (Poor design!)

Because stacks add to the top and remove from the top, we consider them last-in, first-out (LIFO) structures. In other words, the most recently-pushed element is the element that will be the first to be removed.

Queues

While stacks are last-in, first-out (LIFO), queues are first-in, first-out (FIFO). Whereas stack operations only allow changes to the top, queue operations allow changes to the “front” and the “back” of the queue. Imagine people waiting in the checkout line at the grocery store. When someone wants to checkout, they’re added to the back of the queue (which might be empty). The first person to checkout is the person at the front of the line.

• add an element to the back of the queue.
• remove and return the element at the front of the queue.
• peek to return but not remove the element at the front of the queue.
• size to return the number of elements in the queue.

Consider the following code snippet.

Queue<String> queue = new LinkedList<String>();
queue.add("puppy");
queue.add("cat");
queue.add("dog");
System.out.println(queue.remove());

The first element removed by queue.remove() is “puppy” since “puppy” was at the front of the queue.

This time, Java got the design right for queues. Queue is an interface in Java, which means that we can’t instantiate it directly. Instead, we need to use an implementation such as LinkedList—the same LinkedList that also implements the List interface.

This is the powerful idea behind ADTs. By declaring an object such as a LinkedList as the interface type Queue, we’re signalling to the human reading the program that we intend to use this object in queue-like ways, rather than all of the possible ways that we might use a list.