stack

Posted on July 12, 2013 data-structures

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