Stackosaurus Rex

stack_qa

# 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