Stacks

Stacks are an abstract data type with the following basic operations:

  • push that puts an element on the top of the stack,

  • top that returns the element at the top of the stack, and

  • pop that removes the topmost element of the stack.

Thus stacks are like queues (see Section Queues and Deques) but with “last in, first out” (LIFO) semantics. Stacks are relatively straightforward to implement with linked lists, resizable arrays or deques. Implementations of stacks in some standard libraries:

Example

The Scala code below shows a simple evaluator for expressions in the reverse Polish notation. The idea is that

  • ​ when a numeric value is read, it is pushed in the stack, and

  • ​ when a binary operator is read, two topmost elements of the stack are popped, the operator applied on then, and the result is pushed back in the stack.

def evaluate(input: String): Int =
  val stack = collection.mutable.Stack[Int]()
  input.trim.split(raw"\s+").foreach(_ match
    case "+" => stack.push(stack.pop() + stack.pop())
    case "*" => stack.push(stack.pop() * stack.pop())
    case x => stack.push(x.toInt)
  )
  stack.top

// evaluate("2 4 3 * 3 + * 12 +") results in 42 as 2*((4*3)+3)+12 = 42

The figure below shows how the stack contents evolve when the input symbols “2 4 3 * 3 + * 12 +” are read. The stacks are drawn such that the topmost element is, well, topmost.

_images/reverse-polish-ex.png