Stacks & Queues: Abstract Data Types

After watching the video and/or reading the notes below, explore Djikstra's Two-Stack Algorithm for evaluating arithmetic expressions

• https://www.youtube.com/watch?v=7H56Bmk1jZQ
• https://introcs.cs.princeton.edu/java/43stack/Evaluate.java.html

Here is a video lecture for the material outlined below. If you prefer (or want supplemental) textbook readings, Bailey Chapter 10 covers this topic and the next topic.

The video contains sections on

1. Abstract Data Types (0:32)
2. Stack and Queue ADTs (3:16)
3. Real-world analogies (5:22)
4. Applications of queues and stacks in CS (7:47)
5. Stack and Queue APIs (13:56)
6. Example usage (17:43)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0bfc1ead-4a9a-4486-9e1f-acb0017f5b89

We have seen the difference between an interface and an implementation. For example, we had a Shape interface that declared a set of operations and then a Circle class that implemented those operations for a particular type of shape (a circle). When thinking about data structures, we often refer to the interface as the Abstract Data Type or ADT. The abstract data type of a List declares operations such as add, remove, contains and size. It is abstract because it only defines the external behavior of these operations—it specifies nothing about the internal implemenation. The implementation could be accomplished using an array, a linked list, or some other structure.

In computer science, two of the most fundamental ADTs are called stacks and queues. It is useful to study stacks and queues as a way to understand a minimal kind of data structure. We'll find, for example, that they are less powerful than the list structures we have been looking at. But we often find ourselves wanting to think in terms of the simplest possible solution to a problem, as in, "You could solve that with a stack."

Like lists, stacks and queues store an ordered sequence of values. A minimal set of operations for such a structure would require at least:

• We need some way to put values into the structure (an adding operation)
• We need a way to take values out (a removing operation)
• We need a way to test whether there is anything left in the structure

These three operations are the bare bones that you'd need for such a structure and in their purest form, stacks and queues have just these three operations. I have put together a version of these that also includes a size method that lets you ask for the number of elements in the structure. Stacks and queues are similar in that they each store a sequence of values in a particular order. But stacks are what we call LIFO structures while queues are FIFO structures:

stacks        queues

L-ast         F-irst
I-n           I-n
F-irst        F-irst
O-ut          O-ut

The analogy for stacks is to think of a cafeteria and how trays are stacked up. When you go to get a tray, you take the one on the top of the stack. You don't bother to try to get the one on the bottom, because you'd have to move a lot of trays to get to it. Similarly if someone brings clean trays to add to the stack, they are added on the top rather than on the bottom. The result is that stacks tend to reverse things. Each new value goes to the top of the stack, and when we take them back out, we draw from the top, so they come back out in reverse order.

The analogy for queues is to think about standing in line at the grocery store. As new people arrive, they are told to go to the back of the line. When the store is ready to help another customer, the person at the front of the line is helped. In fact, the British use the word "queue" the way we use the word "line" telling people to "queue up" or to "go to the back of the queue".

Applications for queues:

• First-come-first-served resource allocation.
  • "First 100 customers get 20% off!"
• Asynchronous data transfer
  • Computer systems use queues to manage various forms of input/output
  • For example, when your program prompts the user for input (say 3 numbers), it probably processes the numbers one at a time (e.g., scanner.nextInt())
  • Where does the rest of the text input exist while the first number is being processed? In a queue!
• Dispensing requests on a shared resource.
  • Certain number of rooms available in various dorms (the shared resource), fill them in some order (a queue)
• Simulations of the real world (e.g., oscillating sound waves, transportation, logistics)

Applications for stacks

• Basic mechanism in interpreters, compilers (used to manage memory and function calls)
  • Take 208 and/or 251 to learn a lot more about this
• "Back" button in a web browser
  • Visit a page.
  • Click a link to another page.
  • Click a link to another page.
  • Click a link to another page.
  • Click "back" button.
  • Click "back" button.
  • Click "back" button.
• Each use of "back" should return to the most recent previous page
  • Last-in-first-out behavior!
• PostScript (Warnock-Geschke, 1980s): the language used to communicate how to print/display a document (primarily used by laser printers)
  • Revolutionized publishing
  • The PDF format is based on PostScript

In the case of a stack, the adding operation is called "push" and the removing operation is called "pop". All operations occur at one end of the stack, at the top. We push values onto the top and we pop them off the top. There is also a method for testing whether the stack is empty and an operation for requesting the current size of the stack. So for a Stack<E>, the basic operations are:

public void push(E value);  // add value to the stack
public E pop();             // remove and return the value most recently pushed
public boolean isEmpty();   // is the stack empty?
public int size();          // number of objects on the stack

Notice that we are using Java generics to define the Stack in terms of an unspecified element type E. That way we'll be able to have a Stack<String> or Stack<Integer> or a Stack of any other kind of element type we are interested in.

For queues, we have a corresponding set of operations but they have different names. The operations for a Queue<E> are:

public void add(E value);  // add value to queue
public E remove();         // remove and return the value least recently added
public boolean isEmpty();  // is the queue empty?
public int size();         // number of objects in the queue

The Java collections framework (the part of Java that provides data structures like ArrayList) does the right thing in terms of Queue<E> by making it an interface. One implementation of this interface is LinkedList<E>. The stack version is much older and was not done as well. In particular, Stack<E> is a class, not an interface. Even though we are using the standard Java stack and queue classes, we'll limit the operations we use with them to those listed above.

Consider this program that does some simple manipulations on a stack and queue:

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

public class SimpleStackQueue {
    public static void main(String[] args) {
        String[] data = {"four", "score", "and", "seven", "years", "ago"};
        Queue<String> q = new LinkedList<>();
        Stack<String> s = new Stack<>();

        for (String str : data) {
            q.add(str);
            s.push(str);
        }

        System.out.println("initial queue = " + q);
        while (!q.isEmpty()) {
            String str = q.remove();
            System.out.println("removing " + str + ", now queue = " + q);
        }
        System.out.println();

        System.out.println("initial stack = " + s);
        while (!s.isEmpty()) {
            String str = s.pop();
            System.out.println("removing " + str + ", now stack = " + s);
        }
    }
}

It produces the following output:

initial queue = [four, score, and, seven, years, ago]
removing four, now queue = [score, and, seven, years, ago]
removing score, now queue = [and, seven, years, ago]
removing and, now queue = [seven, years, ago]
removing seven, now queue = [years, ago]
removing years, now queue = [ago]
removing ago, now queue = []

initial stack = [four, score, and, seven, years, ago]
removing ago, now stack = [four, score, and, seven, years]
removing years, now stack = [four, score, and, seven]
removing seven, now stack = [four, score, and]
removing and, now stack = [four, score]
removing score, now stack = [four]
removing four, now stack = []

As we expected, the queue values came out in the same order as the array but the stack values came out in reverse order.

1. Which of the following statements about stacks and queues is true?
   1. Stacks and queues can store only integers as their data.
   2. A stack returns elements in the same order as they were added (first-in, first-out).
   3. A queue’s remove method removes and returns the element at the front of the queue.
   4. Stacks and queues are similar to lists, but less efficient.
2. If you create a new empty stack and push the values 1, 2, and 3 in that order, and call pop on the stack once, what value will be returned?
3. If you create a new empty queue and add the values 1, 2, and 3 in that order, and call remove on the queue once, what value will be returned?
4. Stacks and queues do not have index-based methods such as get from ArrayList. How can you access elements in the middle of a stack or queue?
5. Stacks and queues have less functionality than other similar collections like lists. Why are they still useful despite lacking functionality? What possible advantages are there of using a less powerful collection?
6. What is the output of the following code?

   Stack<String> s = new Stack<>();
   Queue<String> q = new LinkedList<>();
   s.push("how");
   s.push("are");
   s.push("you");
   while (!s.isEmpty()) {
       q.add(s.pop());
   }
   System.out.println(q);
   

7. The following piece of code incorrectly attempts to compute the sum of all positive values in a queue of integers. What is wrong with the code, and how would you fix it?

   int sum = 0;
   while (!q.isEmpty()) {
       if (q.remove() > 0) {
           sum += q.remove();
       }
   }
   

8. Write a piece of code that finds and prints the longest string in a stack of strings. For example, in the stack [hello, hi, goodbye, howdy], the longest string is ="goodbye"=. When your code is done running, the stack should still contain the same contents as it had at the start. In other words, if you destroy the stack as you examine it, restore its state afterward. If you like, put your code into a method called printLongest that accepts the stack as a parameter.

• Questions? (Hold lab questions until later)
• My reflections on the lab
  • Seems like a lot of people waited until Friday or later to start working on the lab
  • Doing this will make the labs harder than they need to be
  • Maybe you weren't sure how to get started
  • That's okay, this is new ideas, a new programming language—it's not easy
  • The important thing is to do in this case is to ask for help
  • If you've done the preparatory exercises and read the lab writeup, and you're not sure where to begin, "how should I get started on the lab" is a great question to ask (in class, on the check-in forum, on discord)
  • But this question will be more helpful to you the earlier you can ask it: more lab assistant hours you can go to, more opportunities to ask me questions, more time to discover other tricky parts of the assignment and get help or review relevant topics
  • I will try to make the lab writeups clearer
• Form questions
• Practice
  • write method to generate a queue of multiples of 3
  • write a method to tranfer values from a queue to a stack
  • write a method to reverse a stack
• Work on lab in pods?