Link Menu Search Expand Document
CSE 143

Stacks and queues

ed Lesson

Table of contents

Introduction

In your prior programming experience, we focused primarily on control abstraction, such as by introducing methods to help us build Java programs.

In CSE 143, we’re interested in the idea of data abstraction and, in particular, the study of abstract data types (ADTs). We’ve seen two examples of ADTs and several implementations for those ADTs.

List
In Java, there are two common implementations of the List interface: ArrayList and LinkedList.
Set
In Java, there are two common implementations of the Set interface: HashSet and TreeSet.

In this lesson, we’ll introduce two new ADTs called stacks and queues. Stacks and queues are very simple structures: in fact, a list can do everything that a stack can do and also everything that queue can do.

Why might we want to use or implement simpler ADTs?

In our introduction to sets, we saw how sets could be used to speed up text processing. Since lists associate elements with indices, ArrayList.contains needs to loop over potentially all of the elements in the list. Sets, on the other hand, don’t have this restriction so the HashSet implementation can be optimized for contains. This is the same idea for stacks and queues: by supporting fewer operations, our data structures can optimize for those operations.

Stacks

The stack abstract data type that 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.
  • isEmpty to return true if and only if the stack is empty.

Consider the following stack.

Client

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.

Which element will be removed by the next pop: "puppy" or "cat"?

The next element removed by stack.pop() will be “cat” since “cat” is on top of “puppy” in the stack.

There’s one weird detail about stacks in Java. Computer scientists consider the idea of a stack as an ADT, not an implementation. Like ArrayList and LinkedList, there are different ways of implementing stacks. 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 type, rather than using the interface type that we learned in the previous lesson.

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 don’t represent the idea of a stack. (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

If stacks are last-in, first-out (LIFO), queues are first-in, first-out (FIFO). Whereas a stack only makes changes to the top, a queue makes 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 stack.
  • isEmpty to return true if and only if the stack is empty.

Consider the following queue.

Client

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.