Advertisement
Guest User

Untitled

a guest
Apr 25th, 2015
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.55 KB | None | 0 0
  1. class LinkedQueue < Queue
  2.  
  3. # Create a node class for making a linked list
  4. Node = Struct.new(:item, :next)
  5.  
  6. # @inv: @count == 0 if and only if @frontNode == @rearNode == nil
  7.  
  8. # Set the item count to 0 and the list references to nil
  9. def initialize
  10. @frontNode = @rearNode = nil
  11. @count = 0
  12. end
  13.  
  14. # Return the current size of the queue
  15. # @result: size
  16. def size
  17. @count
  18. end
  19.  
  20. # Remove all elements from the queue
  21. # @post: empty?
  22. def clear
  23. initialize
  24. end
  25.  
  26. # Add an item to the back of the queue
  27. # @post: size = old.size+1
  28. # if !old.empty? then front == old.front
  29. # if old.empty? then front == item
  30. # @result: size
  31. def enter(item)
  32. if empty?
  33. @frontNode = @rearNode = Node.new(item,nil)
  34. else
  35. @rearNode = @rearNode.next = Node.new(item,nil)
  36. end
  37. @count += 1
  38. end
  39.  
  40. # Remove and return the item at the front of the queue
  41. # @pre: !empty?
  42. # @post: size == old.size-1
  43. def leave
  44. raise UnderflowError, "leave" if empty?
  45. @count -= 1
  46. frontItem = @frontNode.item;
  47. @frontNode = @frontNode.next;
  48. @rearNode = nil if empty?
  49. return frontItem
  50. end
  51.  
  52. # Return the front item in the queue, but don't remove it
  53. # @pre: !empty?
  54. # @post: size == old.size
  55. def front
  56. raise UnderflowError, "front" if empty?
  57. return @frontNode.item
  58. end
  59.  
  60. # Transform to an array for testing purposes
  61. def to_a
  62. currentNode = @frontNode
  63. result = []
  64. while currentNode
  65. result << currentNode.item
  66. currentNode = currentNode.next
  67. end
  68. return result
  69. end
  70. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement