15 July 2013

Algorithmathon
<ul class = "posts-by-tag-list">      
  <li class="posts-by-tag-item Algorithm Algorithmathon"><a class = "posts-by-tag-item-title" href="/post/2013/algorithmathon-day-4-single-linked-list-remove-insert-after-insert-before.html">Next Article</a></li>
  <li class="posts-by-tag-item Algorithm Algorithmathon"><a class = "posts-by-tag-item-title" href="/post/2013/algorithmathon-day-2-single-linked-list-cycle.html">Previous Article</a></li>
</ul>

Today we will be looking into the Stack data structure and writing the push and pop methods to add and remove data from the stack. While we will need to change it quite a bit we will start with the Single Linked List (SLL) Base found here. If you haven’t already read them, rules for the Algorithmathon can be found here. The code can be found here on GitHub. First we write our failing tests.

single_linked_list_spec.rb

require ‘spec_helper’ require ‘single_linked_list_spec_helper’

describe SingleLinkedList do

describe “Class” do it “should have method ‘push’” do SingleLinkedList.method_defined?(:push).should be_true end

end

describe “Instance” do

before(:each) do
  @list = SingleLinkedList.new()
end

it "should return object when 'push' is called and successful" do
  first = SingleLinkedListElement.new("first")
  @list.push(first).eql?(first).should be_true
end

end

end

When we run RSpec we get failing (Red) results. To pass these failing tests we can add the method push to our SLL like so.

single_linked_list.rb

require ‘single_linked_list_element’

class SingleLinkedList attr_reader :head

def push(element) unless element.nil? @head=element end end end

Now when we run our test the results will be passing (Green). Writing your test before you write your code is Test Driven Development. Your goal is to write your test and then to write the minimal amount of code to satisfy the test. Now that the tests for our push method are passing we should write tests for our pop method.

single_linked_list_spec.rb

require ‘spec_helper’ require ‘single_linked_list_spec_helper’

describe SingleLinkedList do

describe “Class” do it “should have method ‘push’” do SingleLinkedList.method_defined?(:push).should be_true end

it "should have method 'pop'" do
  SingleLinkedList.method_defined?(:pop).should be_true
end

end

describe “Instance” do

before(:each) do
  @list = SingleLinkedList.new()
end

it "should return first object when 'push' is called and successful" do
  first = SingleLinkedListElement.new("first")
  @list.push(first).eql?(first).should be_true
end

it "should return first object when 'pop' is called" do
  first = SingleLinkedListElement.new("first")
  @list.push(first)
  @list.pop().eql?(first).should be_true
end    

end

end

Our test for pop will of course fail and thus we should update our code so that they pass.

single_linked_list.rb

require ‘single_linked_list_element’

class SingleLinkedList attr_reader :head

def push(element) unless element.nil? @head=element end end

def pop() element=@head @head=@head.next_node element end

end

We now have passing tests for both push and pop. Still we should add another test using multiple objects since a stack must handle multiple objects.

single_linked_list_spec.rb (exerpt)

...
it "should return all objects popped in the reverse order they where pushed" do
  first = SingleLinkedListElement.new("first")
  second = SingleLinkedListElement.new("second")
  third = SingleLinkedListElement.new("third")
  fourth = SingleLinkedListElement.new("fourth")
  fifth = SingleLinkedListElement.new("fifth")
  @list.push(first).eql?(first).should be_true
  @list.push(second).eql?(second).should be_true
  @list.push(third).eql?(third).should be_true
  @list.push(fourth).eql?(fourth).should be_true
  @list.push(fifth).eql?(fifth).should be_true
  @list.pop().eql?(fifth).should be_true
  @list.pop().eql?(fourth).should be_true
  @list.pop().eql?(third).should be_true
  @list.pop().eql?(second).should be_true
  @list.pop().eql?(first).should be_true
end    
...

Ooops our new test is failing! We need to go back and fix our push method to handle linking these objects. Which is simple enough as shown below.

single_linked_list.rb

require ‘single_linked_list_element’

class SingleLinkedList attr_reader :head

def push(element) unless element.nil? if @head.nil? @head=element else element.next_node=@head @head=element end end end

def pop() element=@head @head=@head.next_node element end

end

All our tests are now passing and we are done with our stack for today.


Less Is More ~ Older posts are available in the archive.