I have consumed several excellent written/video tutorials on Stacks and Queues, with their characteristics and limitations. However, I haven't seen many examples where these 2 data structures are implemented beyond defining their class and associated methods.
So I've created a Ruby tutorial that implements stacks and queues within an example where meals are served to a line of guests at a party!
In this tutorial, we will create a short program that takes two arrays (Stack of Meals, and Queue of Guests) and advances the queue based on whether the top meal matches the culinary preferences of the first guest in the queue.
Sound like fun? Let's dive in!
Let's build the MealStack class first. This class will accept an array of meals (meals_array
) identified by their type (such as 'vegetarian', 'regular', 'vegan').
class Stack
attr_accessor :meals
def initialize(meals_array)
self.meals = meals_array
end
end
We want to be able to do the following with a MealStack:
- See what meal is at the top of the stack (
top_meal
), which is the last item in the array:
def top_meal
meals.last
end
- Take the top meal off the stack (
take_meal
):
def take_meal
meals.pop
end
- Know if all meals are gone (
stack_empty?
):
def stack_empty?
meals.empty?
end
- View all remaining meals in the stack (
display_meals
). We call.reverse
onmeals
so that the last array entry appears first (as the top of the stack):
def display_meals
meals.reverse.inspect
end
- Know how many meals are in the stack (
size
):
def size
meals.length
end
Here is the complete MealStack class:
class MealStack
attr_accessor :meals
def initialize(meals_array)
meals = meals_array
end
def top_meal
meals.last
end
def take_meal
meals.pop
end
def stack_empty?
meals.empty?
end
def display_meals
meals.reverse.inspect
end
def size
meals.length
end
end
Now let's build the GuestQueue class, which accepts an array of guests identified by their meal preference. For simplicity's sake, guests' meal preferences are identified same as the meals array - 'vegetarian', 'vegan', etc.
class GuestQueue
attr_accessor :guests
def initialize(guest_array)
self.guests = guest_array
end
end
We want to be able to do the following with a QueueStack:
- Know who is at the front of the queue (
first_guest
):
def first_guest
guests.first
end
- Have guests able to join the queue (
join_queue(guest)
):
def join_queue(guest)
guests.push(guest)
end
- Have guests able to leave the queue (
leave_queue
):
def leave_queue
guests.shift
end
- Have guests able to rejoin the queue (
rejoin_queue
):
def rejoin_queue
join_queue(leave_queue)
end
- Know if all guests have been served (
queue_empty?
):
def queue_empty?
guests.empty?
end
- View all remaining guests in the queue (
display_queue
):
def display_queue
guests.inspect
end
- Know how many guests are in the queue (
size
):
def size
guests.length
end
Here is the complete GuestQueue class:
class GuestQueue
attr_accessor :guests
def initialize(guest_array)
self.guests = guest_array
end
def first_guest
guests.first
end
def join_queue(guest)
guests.push(guest)
end
def leave_queue
guests.shift
end
def rejoin_queue
join_queue(leave_queue)
end
def queue_empty?
guests.empty?
end
def display_queue
guests.inspect
end
def size
guests.length
end
end
Finally, let's make sure our MealStack and GuestQueue classes work:
my_meals = MealStack.new(%w[vegetarian vegan normal paleo vegan normal paleo])
puts my_meals.size # 7
puts my_meals.top_meal # paleo
puts my_meals.take_meal # paleo
puts my_meals.stack_empty? # false
puts my_meals.take_meal # normal
puts my_meals.take_meal # vegan
puts my_meals.size # 4
- - -
my_friends = GuestQueue.new(%w[normal paleo vegan vegetarian vegan normal paleo])
puts my_friends.size # 7
puts my_friends.first_guest # normal
puts my_friends.leave_queue # normal
puts my_friends.leave_queue # paleo
puts my_friends.size # 5
puts my_friends.rejoin_queue # vegan
puts my_friends.leave_queue # vegetarian
puts my_friends.first_guest # vegan
In the next part, things get interesting when we build our Party class!
Top comments (0)