Skip to content

Stack and Queue Applications

Most languages, including Java, often have fundamental data structures like arrays, linked lists, stacks, and queues already implemented as part of the language itself as an example Java has collection libraries that are implementations of resizing arrays (ArrayList) and doubly linked lists ( LinkedList).

The java.util.List interface defines an ordered sequence of elements, providing methods for operations like adding to the end or removing from a specific position.

boolean isEmpty() // is the list empty?
int size() // number of items
void add(Item item) //append to the end
Item get(int index) // return the item at given index
Item remove(int index) //remove and delete item at given index
boolean contains(Item item) //does the list contain the given item?
Iterator<Item> iterator() // iterate over all items in the list

While libraries are convenient, they’re often ‘Swiss army knife solutions’ with inherent overhead (‘bloat’) that can lead to performance degradation compared to a highly optimized, custom implementation. For extremely performance-critical applications or for learning the underlying mechanics, implementing simple data structures like Stack, Queue, or Bag yourself can be beneficial. However, for most general purposes, Java’s built-in collections are efficient and widely used.

The main takeaway is to not use a library until you understand the API and it’s performance characteristics.

Stacks are fundamental underlying computations as they implement recursion, we use stacks everyday! Below are a few examples.

  • Parsing in a compiler
  • Java Virtual machine
  • Undo in a word processor
  • Back button in a web browser
  • PostScript language for printers
  • Implementing function calls in a compiler

The two examples we will focus on in more detail will be compiling from a language to interpret into an actual computation and the PostScript language which is widely used for printing and publishing.

How a Compiler Implements a Function (Function Calls)

Section titled “How a Compiler Implements a Function (Function Calls)”
  • Function Call: push local environment and return address.
  • Return: pop return address and local environment.

There’s a stack that contains all the information above - whether the stack is recursive is not an issue and we can always use an explicit stack to eliminate recursion (by simulating the call stack),.

Lets take the greatest common denominator function.

static int gcd(int p, int q){
if (q == 0) return p;
else return gcd(q, p % q);
}

If we started with say p = 216 and q = 192

  1. p = 216, q = 192
  2. p = 192, q = 24
  3. p = 24, q = 0

The way the above is compiler implements the recursion is by saving the information on a stack.

Goal: Evaluating infix (arithmetic) expressions.

Example: (1+((2+3)(45)))(1 + ((2 + 3) * (4 * 5)))

In the above the value (operand) would be our numbers and our operator would be our symbols noting addition, subtraction, division etc.

Approach

  1. Maintain two stacks one for value and one for operator
  2. evaluate each position left to right
  3. If Value: push onto the value stack
  4. If Operator: push onto the operator stack.
  5. If Left Parenthesis: ignore.
  6. If Right Parenthesis: pop operator and two values; push the results of applying that operator to those values onto the operand stack.

Results

Operand Stack (Values)Operator StackRemaining Formula
nullnull(1+((2+3)(45)))(1 + ((2 + 3) * (4 * 5)))
1null+((2+3)(45)))+((2 + 3) * (4 * 5)))
1+((2+3)(45)))((2 + 3) * (4 * 5)))
1, 2++3)(45)))+ 3) * (4 * 5)))
1, 2+, +3)(45)))3) * (4 * 5)))
1, 2, 3+, +)(45))))* (4 * 5)))
1, 5+(45)))* (4 * 5)))
1, 5+, *(45)))(4 * 5)))
1, 5, 4+, *5)))* 5)))
1, 5, 4+, _, _5)))5)))
1, 5, 4, 5+, _, _))))))
1, 5, 20+, *))))
1, 100+))
101null

The Code that implements Dijkstra’s two stack algorithm

import java.util.Stack;
//Other imports here
public class Evaluate{
public static void main (String[] args){
Stack<String> ops = new Stack<String>();
Stack<Double> vals = new Stack<Double>();
while(!StdIn.isEmpty()){
String s = StdIn.readString();
if (s.equals("(")){};
else if ( s.equals("+") ) ops.push(s);
else if ( s.equals("*") ) ops.push(s);
else if ( s.equals(")") ){
String op = ops.pop();
double val2 = vals.pop();
double val1 = vals.pop();
if ( op.equals("+") ) vals.push( val1 + val2 );
else if ( op.equals("*") ) vals.push( val1 * val2 );
//Other operators here
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}

This code is easily extended by adding more operations, precedence order and associativity. This would be one of the earliest steps on the road to developing a compiler or a way to translate a program from a programming language to a computation.