Stacks

In many applications we have collections of objects we want to maintain. The operations for these objects are simple.

We would want to:

• Add something to a collection
• Remove something from a collection
• Iterate through the objects in a collection and perform some operation on them
• Test if an object is empty

Where a Stack and a Queue fundamentally differ is in the way we remove objects, in a stack we take out the item that was most recently added (push (insert) and pop(remove)) where as with a queue we examine the item least recently added (enqueue (insert) and dequeue(remove)).

Stack Data Structure and Implementations

As mentioned in the introduction a stack would comprise of a collection of objects with various operations related to maintaining the collection. As an example a stack of strings could have the following operations associated.

//psuedo code
public class StackOfStrings()
  //create an empty stack
  StackOfStrings()
  //insert a new string into stack
  void push(String item)
  //remove and return the string most recently added
  String pop()
  // is the stack empty?
  boolean isEmpty()
  // number of strings in the stack
  int size()

Lets write a simple client that takes some simple strings on standard input and some pop commands which are indicated with -

public static void main(String[] args){
  StackOfStrings stack = new StackOfStrings();
  while(!StdIn.isEmpty()){
    String s = StdIn.readString();
    if(s.equals("-")) StdOut.print(stack.pop());
    else stack.push(s);
  }
}

Edge Cases

There are a few edge cases that need to be considered dependant on the type of stack (linked list or array) that is being implemented. Below are a list of those considerations.

• Underflow: throw exceptions if pop from an empty stack.
• Overflow: use resizing array for array implementations.
• Null Items: we allow null items to be inserted
• Loitering: Holding reference to an object when it is no longer needed.

In Java for example the below code would holding a reference to a pointer longer then required (loitering).

public String pop() { return s[--N]; }

To avoid this we can implement a pop as such where the garbage collector can reclaim memory.

public String pop()
{
  String item = s[--N];
  s[N] = null;
  return item;
}

Implementing an Array Stack

Another method we could explore for implementing a stack would be the array implementation, the decision between linked lists and arrays will be an important discussion point to consider when looking at requirements.

• Use array s[] to store N items on a stack
• push(): add new item at s[N]
• pop(): remove item from s[N-1]

s[]

to	be	or	not	to	be	null	null	null	null
0	1	2	3	4	5	6	7	8	9

Defect : Stack overflows when N exceeds capacity - Stack has a certain capacity that needs to be declared ahead of time. This is a fundamental problem of arrays.

Full Implementation using Array

public class FixedCapacityStackOfStrings{
  private String[] s;
  private int N = 0;

  public FixedCapacityStackOfStrings(int capacity)
  { s = new String[capacity]; }

  public boolean isEmpty()
  { return N == 0; }

  public void push(String item)
  { s[N++] = item; }

  public String pop()
  { return s[--N]; }
}

Resizing Array Approach

Problem: How do we grow and shrink the array to avoid underflow and overflow?

We could look at the first solution simply as:

• push() : Increases size of array s[] by 1.
• pop() : decreases size of array s[] by 1.

The issue with this solution is the operations can become too expensive we would need to copy all items to a new array and then inserting first N items can take time proportional to

$1+2+...+N \sim \frac{N^2}{2}$.

This would not be feasible for a large N as the algorithm is quadratic.

The challenge is to resize infrequently reducing operations and increasing the efficiency of our algorithms.

Growing our Array

Lets take the growth of our array as an example.

Repeated doubling

One method we could use is to create a new array twice the size, and copy items.

public ResizingArrayStackOfStrings(){
  s = new String[1];
}

public void push(String item){
  if (N == s.length) resize (2 * s.length);
  s[N++] = item;
}

private void resize(int capacity){
  String[] copy = new String[capacity];
  for (int i = 0; i < N; i++){
    copy[i] = s[i];
  }
  s = copy;
}

This method now makes inserting first N items take time proportional to N (Not $N^2$) . The reasoning behind this is we only create a new Array every time we double the length of our original array - However, we have already iterated enough operations to fill the array in the first place hence the doubling triggering after N operations have already been completed. Essentially our algorithm is now achieves amortized constant time.

We represent the total cost for N operations in tilde notation, considering the array doubling operations, giving us ~3N.

$N + (2+4+8+...+N) \sim 3N$. (this includes array accesses to double to size K)

Shrinking our Array

The first simple approach here would be to:

• push() : double size of array s[] when array is full.
• pop() : halve size of array s[] when array is one-half full.

Unfortunately this approach would be too expensive in it’s worst case due to a phenomenon called thrashing.*

Consider a client doing push-pop-push-pop operations sequentially when the number of elements in the array hovers around the one-half full threshold, this would cause thrashing where the array will consistently double and half creating new arrays on every operations.

Since each doubling or halving operation requires copying all existing elements ( an $O(N)$) operation), these frequent resizes would lead to a total time complexity that is quadratic ($O(N^2)$) for a sequence of N such operations, this defeats the purpose of amortized constant time performance improvements.

Amortized Shrink Operations

An efficient approach is to amortize our shrink operations by moving our bounds that trigger a shrink to if the array is one quarter full. If the array is a quarter full we then resize it to half its original length repeating the operations only when the criterion of 1/4 full is met removing possible thrashing scenarios.

public String pop(){
  String item = s[--N];
  s[N] = null;
  if(N > 0 && N == s.length/4){
    resize(s.length/2);
  }
  return item;
}

Amortized Analysis

Amortizing operations will ensure:

• Client does not need to provide a maximum amount of memory for the stack
• Guaranteed that the amount of memory that we use is always a constant multiple of the number of items actually on the stack.

To analyse the results we would take the average running time per operation over a worst-case sequence of operations. At the point the stack doubles it takes time proportional to N the trade off is really fast pushes and pops.

Implementing a LinkedList Stack

The first implementation of a stack we will look at uses Linked Lists. The idea here is to keep a linked list which consists of a node with strings in them that keeps track of the next strings (singly linked list for stacks). A stack within this context would insert a new node at the beginning of the linked list when using a push operation and similarly would remove a node at the beginning of the linked list on a pop operation. This is achieved by maintaining a pointer to the head of the linked list as the target of our operation.

Inner class for linked data structures

An inner class is a way to describe that we will be manipulating node objects that each consist of a string and a reference to another node. Inner classes follow a Pascal case naming convention. Defining the encapsulation of an inner class will ensure its accessibility through out a program. As an example an inner class that is only meant to be used within the outer classes could be defined as private static.

Implementing Push and Pop

Assume the following inner class structure

private class Node{
  String item;
  Node next;
}

Pop

1. Save item to return

String item = first.item;

2. Delete first node

first = first.next;

3. Return saved item

return item;

Push

1. Save pointer to beginning of list

Node oldfirst = first;

2. Create a new node for the beginning

first = new Node();

3. Set the instance variables in the new node

first.item = "not";
first.next = oldfirst;

Full Code

public class LinkedStackOfStrings
{
  private Node first = null;

  private class Node
  {
    String item;
    Node next;
  }

  public boolean isEmpty()
  { return first == null; }

  public void push(String item)
  {
    Node oldfirst = first;
    first = new Node();
    first.item = item;
    first.next = oldfirst;
  }

  public String pop()
  {
    String item = first.item;
    first = first.next;
    return item;
  }

}

Resizing Array Stack vs LinkedList

So what are the trade-offs between using resizing-arrays vs. Linked Lists.

For linked list’s every operation takes constant time in the worst case. It also takes extra time and space to deal with the links. Resizing-arrays on the other hand take constant amortized time for every operation and there is less wasted space. An example of how these trade offs can be viewed.

A network switch needs to consistently deal with packets coming in at a standard speed with no peaks and troughs, as a resizing-array may have issues when doubling in size a linked list may be better suited as operation speed is easier to guarantee.

Or on the other hand…

A website with a file uploading service is catering it’s storage volume allocation based on the amount of files uploaded, it may periodically shrink or grow its volumes to help deal with capacity. The small delay in operation does not cause impact to the end user experience this implementation may be better suited for a resizing-array.

Stack 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).

java.util.list

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

Performance Considerations

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)

• 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.

Algorithms

Dijkstra’s Two-stack algorithm

Goal: Evaluating infix (arithmetic) expressions.

Example: $(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 Stack	Remaining Formula
null	null	$(1 + ((2 + 3) * (4 * 5)))$
1	null	$+((2 + 3) * (4 * 5)))$
1	+	$((2 + 3) * (4 * 5)))$
1, 2	+	$+ 3) * (4 * 5)))$
1, 2	+, +	$3) * (4 * 5)))$
1, 2, 3	+, +	$)* (4 * 5)))$
1, 5	+	$* (4 * 5)))$
1, 5	+, *	$(4 * 5)))$
1, 5, 4	+, *	$* 5)))$
1, 5, 4	+, _, _	$5)))$
1, 5, 4, 5	+, _, _	$)))$
1, 5, 20	+, *	$))$
1, 100	+	$)$
101	null

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.