Skip to content

Instantly share code, notes, and snippets.

@hrp
Created February 10, 2015 22:57
Show Gist options
  • Save hrp/9cd5940ebf37373854b7 to your computer and use it in GitHub Desktop.
Save hrp/9cd5940ebf37373854b7 to your computer and use it in GitHub Desktop.
Stackosaurus Rex
# Design a data structure supporing the following:
# 1) Push an element
# 2) Pop an element
# 3) Find Minimum in the data structure
# Push(12)
# 12
# Min() ==> 12
# Push(8); Push(1); Push(24):
# 12 8 1 24
# Min() ==> 1
# Pop() ==> 24
# Pop() ==> 1
# Min() ==> 8
class Node
attr_accessor :next, :prev, :value
def initialize(value)
@next = nil
@prev = nil
@value = value
end
end
class Queue
attr_accessor :head, :tail
def initialize
@head = nil
@tail = nil
end
def push(val)
n = Node.new(val)
if @tail
@tail.next = n
n.prev = @tail
@tail = n
else
@head = @tail = n
end
end
def pop
return nil unless @tail
popped = @tail
if @tail.prev
# prev_tail = @tail.prev
@tail = popped.prev
@tail.next = nil
else
@head = @tail = nil
end
popped.value
end
def min
i = @head
j = @head.next
until j == nil do
if i.value < j.value
j = j.next
else
i = j
j = j.next
end
end
i.value
end
end
# 3) Find Minimum in the data structure
# Push(12)
# 12
# Min() ==> 12
# Push(8); Push(1); Push(24):
# 12 8 1 24
# Min() ==> 1
# Pop() ==> 24
# Pop() ==> 1
# Min() ==> 8
q = Queue.new
q.push(12)
p q.min
q.push(8)
q.push(1)
q.push(24)
p q.min
p q.pop
p q.pop
p q.min
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment