Stack is a last-in-first-out data structure that can be easily implemented using Array. We can simply restrict our interface that wraps an Array to just two operations -- push and pop and some other useful methods to emulate stack like functionality. You can read more about stacks here.

We'll make some assumptions before we start the implementation.

array[0] would always be the bottom of our stack. array[n] will be the top of the stack.

size method will keep track of the size of our stack.

push should always return self. pop should always return the value of the popped element.

Because arrays in Ruby are dynamic, we'll be starting off with a simple implementation of building a stack that can be grown as we add elements to it.

Example Code:

class Stack def initialize @store = Array.new end def pop @store.pop end def push(element) @store.push(element) self end def size @store.size end end

[reset] Need a hint? See the Solution

Hint

Output Window

The Stack class maintains an unbound @store array and simply calls pop and push on them. size returns the length of the array.

Modify the above example to make the Stack class statically sized. push and pop should return nil if the stack is overflowing or underflowing respectively. Implement private predicate methods full? and empty? and public method size that returns the length of the stack, and look that returns the value on the top of the stack.

class Stack def initialize(size) end def pop end def push(element) end def size end def look end private def full? end def empty? end end

[reset] Need a hint? See the Solution

Hint

Implement a @top instance variable that tracks the top of the stack. Set it to -1 in initialize.

Output Window

Queue is a first-in-first-out data structure in which the two major operations are enqueue and dequeue. enqueue adds an element to the rear of the queue and dequeue removes an element from the front of the queue. You can read more about queues here.

array[0] will be the rear of our queue. array[n] will be the front of the queue.

In this example, we'll use unshift to insert elements and pop to remove an element. This is because our queue is again, unbounded and can be grown as we keep on adding elements. These methods also allow us to not store any front or rear state in the class.

Example Code:

class Queue def initialize @store = Array.new end def dequeue @store.pop end def enqueue(element) @store.unshift(element) self end def size @store.size end end

[reset] Need a hint? See the Solution

Hint

Output Window

Neat and simple.

Write your own implementation of a Queue that is also statically sized. Like in the stack exercise before, enqueue and dequeue should return nil for overflow or underflow.

class Queue def initialize(size) end def dequeue end def enqueue(element) end def size end private def full? end def empty? end end

[reset] Need a hint? See the Solution

Hint

Implement @head that points to -1, @tail that points to 0

Output Window