Skip to content

Instantly share code, notes, and snippets.

@trobrock
Created May 23, 2012 15:16
Show Gist options
  • Save trobrock/2775839 to your computer and use it in GitHub Desktop.
Save trobrock/2775839 to your computer and use it in GitHub Desktop.
Linked List Queue
class Queue
def initialize
@first = nil
@last = nil
@length = 0
end
def push(element)
node = Node.new
node.value = element
@length += 1
if @first.nil?
@first = node
else
@last.next = node
end
@last = node
end
def pop
node = @first
@length -= 1
@first = @first.next
node.value
end
def peek
@first.value
end
def size
@length
end
def empty?
@first.nil?
end
end
class Node
attr_accessor :next
attr_accessor :value
end
require File.join(File.dirname(__FILE__), 'queue')
describe Queue do
before(:each) do
@queue = Queue.new
end
it "should be able to push things on the queue" do
@queue.push(1)
@queue.size.should == 1
end
it "should pop of the first item on the queue" do
@queue.push(1)
@queue.push(2)
@queue.pop.should == 1
@queue.size.should == 1
end
it "should be able to get the next element without removing it" do
@queue.push(1)
@queue.peek.should == 1
@queue.size.should == 1
end
it "should know if it's empty" do
@queue.should be_empty
@queue.push(1)
@queue.pop
@queue.should be_empty
@queue.push(1)
@queue.should_not be_empty
end
it "should not adjust the length of the internal array if not needed" do
@queue.push(1)
@queue.push(2)
@queue.push(3)
@queue.push(4)
@queue.push(5)
@queue.elements.size.should == 5
@queue.pop.should == 1
@queue.pop.should == 2
@queue.elements.size.should == 3
@queue.push(6)
@queue.push(7)
@queue.push(8)
@queue.elements.size.should == 6
@queue.pop.should == 3
@queue.pop.should == 4
@queue.pop.should == 5
@queue.pop.should == 6
@queue.pop.should == 7
@queue.pop.should == 8
@queue.push(9)
@queue.pop.should == 9
@queue.elements.size.should == 0
end
end
@trobrock
Copy link
Author

Not sure if all these specs work for this, I may have changed them since this implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment