stack

A stack is a Last In First Out (LIFO) data structure. Items are pushed on to the stack (add) and popped off the stack (remove). The last item added is the first item popped off.

There are a couple of ways to implement a stack. One way is to use a linked list data structure, and another is to use a dynamic array.

example

This is an example of building a stack using a linked list. The tail of the list is the first item popped off the stack. Most of the work happens at the tail.

# incomplete

This example uses a dynamic array. Thankfully ruby handles most of the grunt work here.

class DynamicArrayStack
  def initialize(items = [])
    @items = items
  end

  def pop
    @items.pop
  end

  def push(item)
    @items.push(item)
  end
end
comments powered by Disqus