Stacks & Queues
It turns out that lists are very useful data structures. In fact, people use lists for all sorts of behaviors. Two behaviors are so common that we have given them their own names.
We will discuss these behaviors again when we are implementing our own data structures but here we discuss these "archetypal" data structures.
Queues (FIFO)
Queues are type of list where you are always operating on opposite ends of a list. Imagine you're waiting in line for food at a dining hall or at a restaurant. You see a line of people, and so you add yourself to the back of the line. The dining hall serves people one at a time from the front of the line. You know that eventually you will reach the front.
Queue behavior is sometimes referred to as "First-Come First-Serve" (FCFS) or "First-In, First-Out" (FIFO).
Java has a Queue
class, and LinkedList
is a queue.
Queue<String> diningHall = new LinkedList<>();
diningHall.add("A");
diningHall.add("B");
System.out.println(diningHall.remove()); // prints: A
diningHall.add("C");
diningHall.add("D");
System.out.println(diningHall.remove()); // prints: B
System.out.println(diningHall.remove()); // prints: C
System.out.println(diningHall.remove()); // prints: D
Note that we could have written this program with diningHall.remove(0)
on a regular List<String>
. Choosing Queue
over List
typically means that you know exactly how you are going to use this data structure and it would help readers of your code to know that, too.
Stacks (LIFO)
Stacks are a type of list where you are always operating on the same side. Imagine you take all your textbooks and pile them up on top of your desk. You realize that your computer science book is on the bottom, and your Spanish Language textbook is on top. You decide to do your Spanish homework first, so as not to knock over your stack of books. Stacks allow you to pile up work for later, and get back to it in a "most-recent" first manner.
Stack behavior is sometimes referred to as "Last-In, First-Out" (LIFO) in symmetry to Queues which are FIFO.
Java has a Stack
class, but they don't recommend it. In fact they recommend the Deque
interface, which is more powerful and we will discuss briefly in the next section.
You can remove from the back of any list by doing: list.remove(list.size()-1)
.
List<String> books = new ArrayList<>();
books.add("CS");
books.add("Philosphy");
System.out.println(books.remove(books.size()-1)); // prints: Philosophy
books.add("Logic");
books.add("Spanish");
System.out.println(books.remove(books.size()-1)); // prints: Spanish
System.out.println(books.remove(books.size()-1)); // prints: Logic
System.out.println(books.remove(books.size()-1)); // prints: CS
If you really want a stack for your project, it may make sense to write a simple class to handle it:
/** Design push/pop for more clear stack-code */
public class StackOfBooks {
/** Using an arraylist to build a Stack. */
private List<String> books = new ArrayList<String>();
/** Add a book to the top of the stack */
public void push(String book) {
this.books.add(book);
}
/** Remove a book from the top of the stack */
public String pop() {
if (this.books.size() == 0) {
throw new IllegalStateException("Out of books!");
}
return this.books.remove(this.books.size() - 1);
}
public static void main(String[] args) {
StackOfBooks books = new StackOfBooks();
books.push("CS");
books.push("Philosphy");
System.out.println(books.pop()); // prints: Philosophy
books.push("Logic");
books.push("Spanish");
System.out.println(books.pop()); // prints: Spanish
System.out.println(books.pop()); // prints: Logic
System.out.println(books.pop()); // prints: CS
System.out.println(books.pop()); // throws: "Out of books!"
}
}
Then you get some control over what happens when you try to grab a book and it's not there; and you can add methods as your algorithm or data structure grows.
The Stack: Method Calls and Recursion
Note that computer architecture has the notion of a stack -- in fact, we normally call that notion The Stack. This is a stack in the data structure sense, but it is implemented in a special way and stores a whole bunch of mixed data.
In fact, when we call methods or functions, we are pushing that code onto The Stack. When we issue a return
statement, we are popping that code from the stack (and maybe pushing the return value!). Stacks are therefore fundamental to how most computer programming languages work -- and we couldn't have most recursive functions (functions that call themselves) without it.
Double-Ended Queues (Deques)
The Deque<T>
interface in Java wraps up data structures for which it is efficient to add or remove from the different sides of a list. LinkedList
not only implements Queue
but it also implements Deque
.
As a Deque<T>
you get to call the methods:
Front | Back | Returns |
---|---|---|
addFirst |
addLast |
void , nothing. |
removeFirst |
removeLast |
T , the item removed. |
getFirst |
getLast |
T , the first/last item. |
If you want a generic Queue
, you can either:
addLast
andremoveFirst
oraddFirst
andremoveLast
If you want a generic Stack
, you can either:
addLast
andremoveLast
oraddFirst
andremoveFirst
Fancier Queues
This section exists as a caveat in case you decide to google around for queue data structures. There are a large class of data structures that are all, broadly, queues and not all of them are relevant to our notion of a queue.
Priority Queues
Later in this course we will see so-called "Priority Queues" (typically implemented as a Heap), which allow you to maintain a queue with importances. For example, the queue to see a professor at office hours is likely to be maintained first by arrival time (FIFO) but students who need to go to another class may petition their classmates to cut in line. Therefore, some sense of urgency or importance is incorporated into the queue.
Even using a priority queue is slightly more difficult because you need to be able to sort the elements you put in; therefore, a priority queue is not quite a list.
Aside: Comparable for PriorityQueue
Another example of a Priority Queue in the real world is a hospital. To use Java's PriorityQueue<T>
we need to implement an interface called Comparable<T>
-- we haven't discussed interfaces in depth and we will return to Comparable
later when we get to sorting.
public class Patient implements Comparable<Patient> {
long arrivalTime;
boolean severe;
String name;
//... constructor and more methods ...
@Override
public int compareTo(Patient p) {
// severe=true then false
int cmp = -Boolean.compare(this.severe, p.severe);
if (cmp != 0) return cmp;
// earlier times better:
cmp = Long.compare(this.arrivalTime, p.arrivalTime);
if (cmp != 0) return cmp;
// by name if all else equal
return this.name.compareTo(p.name);
}
}
Concurrent or Threadsafe Queues
In a more advanced programming class or an operating systems class, more subtleties are added to queue design: what happens if two requests come in at the same time?
In the dining hall metaphor, the two students arriving at the same time will sort out for themselves which order they should be added to the queue. Elements in our lists are not so intelligent, but some queues are smarter and work to deal with such conflicts without causing the line to end up in disarray.
A computer uses an abstraction called threads to run code at the same time, and therefore queues that are safe to use in this environment are called concurrent or threadsafe queues. Java has some of these in its standard library but we will not dicuss them in this course.