loading...
Cover image for Let's Party with Stacks and Queues! Pt 3

Let's Party with Stacks and Queues! Pt 3

msarit profile image Arit Amana ・4 min read

In Part 2, we had a full-blown party going! But things were convenient; since we had a meal for every guest, everyone eventually got served. Now we'll address a likely scenario - a top meal that no guest wants:

my_party = Party.new(
    %w[vegetarian vegan keto normal paleo],
    %w[normal paleo vegan vegetarian])

Console output:

Party Status:
 Meals: ["paleo", "normal", "keto", "vegan", "vegetarian"]
 Guests: ["normal", "paleo", "vegan", "vegetarian"]

No one was served the last round

Party Status:
 Meals: ["paleo", "normal", "keto", "vegan", "vegetarian"]
 Guests: ["paleo", "vegan", "vegetarian", "normal"]

Guest wanting a paleo meal has been served

Party Status:
 Meals: ["normal", "keto", "vegan", "vegetarian"]
 Guests: ["vegan", "vegetarian", "normal"]

No one was served the last round

Party Status:
 Meals: ["normal", "keto", "vegan", "vegetarian"]
 Guests: ["vegetarian", "normal", "vegan"]

No one was served the last round

Party Status:
 Meals: ["normal", "keto", "vegan", "vegetarian"]
 Guests: ["normal", "vegan", "vegetarian"]

Guest wanting a normal meal has been served

Party Status:
 Meals: ["keto", "vegan", "vegetarian"]
 Guests: ["vegan", "vegetarian"]

No one was served the last round

Party Status:
 Meals: ["keto", "vegan", "vegetarian"]
 Guests: ["vegetarian", "vegan"]

No one was served the last round

. . . . <hundreds of lines later> . . . . .

Party Status:
 Meals: ["keto", "normal", "vegetarian"]
 Guests: ["vegan", "vegetarian", "normal"]

No one was served the last round

Traceback (most recent call last):
    11913: from stacksandqueues2.rb:104:in `<main>'
    11912: from stacksandqueues2.rb:97:in `meal_service'
    11911: from stacksandqueues2.rb:91:in `move_queue'
    11910: from stacksandqueues2.rb:91:in `move_queue'
    11909: from stacksandqueues2.rb:91:in `move_queue'
    11908: from stacksandqueues2.rb:91:in `move_queue'
    11907: from stacksandqueues2.rb:91:in `move_queue'
    11906: from stacksandqueues2.rb:91:in `move_queue'
     ... 11901 levels...
        4: from stacksandqueues2.rb:91:in `move_queue'
        3: from stacksandqueues2.rb:82:in `move_queue'
        2: from stacksandqueues2.rb:74:in `view_party'
        1: from stacksandqueues2.rb:21:in `display_meals'
stacksandqueues2.rb:21:in `inspect': stack level too deep (SystemStackError)

Welp! What happened? Well, we got an error because the queue keeps cycling round and round, aligning different guests with the "keto" meal, but there is no match. We need a way to trash this unwanted meal, but only after making sure that there's no guest with a keto-meal preference.

We know that a top meal is unwanted if the entire queue has cycled once. So we need to keep track of how many guests have rejected the top meal; when this number equals the number of guests in the queue, we know that no one wants our top meal.

Let's introduce a rejected counter as an argument for the move_queue method. This counter is initially set to zero. For each meal-guest mismatch, rejected is incremented by 1. Then rejected is compared to the queue size; if both values are equal, the top meal is "trashed" and rejected is reset to 0:

def move_queue(rejected=0)
    view_party

    if match?
      meals.take_meal
      served = guests.leave_queue
      puts "Guest wanting a #{served} meal has been served\n\n"
    else
      rejected += 1
      guests.rejoin_queue
      puts "No one was served the last round\n"
      puts "Top Meal Rejections: #{rejected}\n\n"

      if rejected == guests.size
        rejected = 0
        trashed_meal = meals.take_meal

        puts "Unwanted #{trashed_meal} meal has been trashed!\n\n"
      end
      move_queue(rejected)
    end
end
Party Status:
 Meals: ["paleo", "keto", "normal", "vegetarian"]
 Guests: ["normal", "paleo", "vegan", "vegetarian"]

No one was served the last round
Top Meal Rejections: 1

Party Status:
 Meals: ["paleo", "keto", "normal", "vegetarian"]
 Guests: ["paleo", "vegan", "vegetarian", "normal"]

Guest wanting a paleo meal has been served

Party Status:
 Meals: ["keto", "normal", "vegetarian"]
 Guests: ["vegan", "vegetarian", "normal"]

No one was served the last round
Top Meal Rejections: 1

Party Status:
 Meals: ["keto", "normal", "vegetarian"]
 Guests: ["vegetarian", "normal", "vegan"]

No one was served the last round
Top Meal Rejections: 2

Party Status:
 Meals: ["keto", "normal", "vegetarian"]
 Guests: ["normal", "vegan", "vegetarian"]

No one was served the last round
Top Meal Rejections: 3

Unwanted keto meal has been trashed!

Party Status:
 Meals: ["normal", "vegetarian"]
 Guests: ["vegan", "vegetarian", "normal"]

Awesome! Our unwanted keto meal has been trashed, and the meal service can continue unhindered - hopefully!

Now, yes, yes, I hear all you time-complexity aficionados:

"This rejected counter approach may work for small get-togethers, but what if you have 500 guests or more? Are we really going to cycle through them all to trash one meal?"

You're right - that would feel like forever and irritate our guests to no end. So how about we (the delightful party hosts) stand next to the meal stack, and once a first guest rejects a meal, we yell out to everyone: "HEY! DO ANY OF YOU WANT THIS TYPE OF MEAL?" If no one answers, then we trash it. Let's create the necessary methods:

# Add this method to the GuestQueue class:
def include?(meal)
    guests.include?(meal)
end

# Add this method to the Party class:
def does_any_guest_want(meal)
    guests.include?(meal)
end

# Modify the 'Party#move_queue' method to the following:
def move_queue
    view_party

    if match?
      meals.take_meal
      served = guests.leave_queue
      puts "Guest wanting a #{served} meal has been served\n\n"
    else
        puts "No one was served the last round\n"

        if does_any_guest_want(meals.top_meal)
            guests.rejoin_queue
        else
            trashed_meal = meals.take_meal
            puts "Unwanted #{trashed_meal} meal has been trashed!\n\n"
        end
        move_queue
    end
end

Another scenario to explore is when the meals are gone but there are still guests waiting to be served. I'll leave that to you :) Like, perhaps a method that stacks additional meals to serve the remaining guests?


I truly hope that this tutorial has fleshed the concepts of Stacks and Queues out a little more! Please let me know what you think in the comments. Thank you so much for sticking with me this far.

Posted on by:

msarit profile

Arit Amana

@msarit

Software Engineer. Former Public Health Analyst. Coding Bootcamp Grad. Mentor to aspiring and early-career female devs.

Discussion

pic
Editor guide