Exercise: The Coffee Shop Order Line
The coffee shop's order screen freezes at rush hour: make its line of orders fast without changing what it does, build the pile of clean mugs behind the counter, and serve a 400,000-order rush in under 2 seconds, each order in the mug on top.
Apprentice · Data Structures · Updated
Here's the ticket from the coffee shop's owner:
The order screen freezes every morning. From 8 to 9 a.m., orders arrive faster than we can make them, and the line on the screen gets long. The screen's line is a list: new orders go on the end, and the barista's screen takes the order at the front, index 0. It works on a quiet afternoon. At rush hour, each "next order" takes longer than the one before.
- First come, first served, always, however long the line.
- Joining and serving each take the same moment with 3 orders waiting or 400,000. A rush of 400,000 orders goes through in under 2 seconds.
- Each order goes in the clean mug on top of the pile behind the counter: the last one washed.
- No order is lost while it waits for a mug, and no mug while it waits for an order.
This time the starter isn't empty: the line of orders is the shop's real code, and it works. Your job is to make it fast without changing what it does, then build the pile of mugs and the one method that joins them. The tests check every edge (an empty line, an order with no mug, a mug with no order), then run the rush against the clock.
Before you start
You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.
Get the exercise code
Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-order-line, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:
git clone https://github.com/ask-codey/exercise-ds-order-line.git
Git makes a folder, exercise-ds-order-line, with the exercise code inside.
The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:
- your code: an
OrderQueue, aCupStackand aCoffeeShopclass (in one file, or three files in C# and Java; the repository'sREADME.mdnames them); - the tests that check your methods. You don't need to change them;
- a demo program that runs the shop through a short morning.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What's already there
OrderQueue is the line the shop runs today. Its three methods work: enqueue adds an order at the end of a list, dequeue takes the order at index 0, and peek reads it. Here is its dequeue in Python, as the starter has it (the other languages say the same in their own syntax):
def dequeue(self):
"""
Remove the order at the front of the line and return it, or return
None if no orders are waiting.
With oat latte, cold brew: dequeue() -> "oat latte", and the line is cold brew
Big-O: (write it here)
"""
if not self.orders:
return None
self.count -= 1
return self.orders.pop(0)
CupStack keeps the clean mugs in your language's list, and its methods do nothing or return null (None in Python) for now. CoffeeShop is done except serveNext (serve_next in Python).
What to do
- The pile of mugs. Finish
CupStack'spush,popandpeek(Push,PopandPeekin C#). The last mug washed is the first one used. - A faster line. Rewrite the inside of
OrderQueue'senqueue,dequeueandpeek, and keep itscountup to date, so that joining and serving each take the same moment however long the line is. Keep the method names and what they return: the tests andCoffeeShopcall them. Write it yourself: your language's ready-made line (Queue<T>,ArrayDeque,collections.deque) would do the work for you. - Serve the next order. Finish
serveNext: when there's an order and a clean mug, take the order at the front of the line and the mug on top, and return"<order> in the <mug>". When either is missing, change nothing and return null. - Name the costs. On each method's Big-O: line, write its Big-O and a few words on why, for your new code.
Check your work
Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).
| Language | Run the tests | Run the demo |
|---|---|---|
| C# | dotnet test |
dotnet run --project OrderLine |
| Java | ./mvnw test (.\mvnw test in PowerShell) |
java src/main/java/Demo.java |
| Python | python -m pytest |
python demo.py |
| JavaScript | npm test |
node demo.js |
| TypeScript | npm test |
node demo.ts |
At first 5 of the 8 tests fail. That's expected: the 3 that pass check the line of orders, which works today; it's only slow. Each method you finish turns more tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: the first order goes in the mug on top, the last one washed. The rush test stops once it passes 2 seconds and says how many orders were still waiting: with today's line, that's most of them.
<details> <summary>Stuck?</summary>
- Start with the mugs. Only one end of the pile is ever used, so the end of your language's list is the right place: push adds there, pop and peek read there. Check for an empty pile first. Undo the Last Thing First: Stacks builds one: a stack.
- Why today's line is slow: taking index 0 out of a list moves every order behind it one slot forward. The line only touches its back and its front. First Come, First Served at Rush Hour: Queues builds a line that's one step at both ends, a queue, on a linked list with a front and a back.
- For the line, make a small class for one order and the order behind it. Enqueue links a new one behind the back (or, on an empty line, makes it both the front and the back). Dequeue moves the front along to the next one.
- When the line empties, empty the back too. If the back still points at the last order served, the next order is linked behind one nobody can reach. One test checks exactly that.
serveNextchanges nothing when it can't serve. Check that there's an order and a mug before you dequeue or pop anything, so an order without a mug keeps its place in line.
</details>
When you're done
Every test is green, and the demo prints the same nine lines in every language:
Washed: red mug, blue mug, white mug
Orders: oat latte, cold brew, chai tea, mocha
Served: oat latte in the white mug
Served: cold brew in the blue mug
Served: chai tea in the red mug
No clean mug: 1 order waiting
Washed: green mug
Served: mocha in the green mug
Orders waiting: 0, mugs left: 0
The first order went into the last mug washed: a line and a pile, working together. Now look back at your Big-O: lines, and at the old dequeue. What did serving the 400,000-order rush cost before your change, and what does it cost now?
<details> <summary>Why Should I Choose This?</summary>
The rush is 400,000 orders placed, then 400,000 served.
- Today's list, served from index 0: each serve moves every order behind it, about 80 billion moves for the rush. On the test's clock it was stopped at 2 to 4.5 seconds, with 320,000 to 390,000 orders still waiting.
- The list turned around: new orders in at index 0, served from the end. Serving is quick, but every new order moves the whole line. The cost moves; it doesn't go away.
- Never removing anything, and keeping the number of the next order: both ends are O(1), but every order of the day stays in memory.
- A queue on linked orders with a front and a back: joining and serving change a reference or two each, O(1), and the rush takes 0.1 to 0.6 seconds. The mugs need only one end, so a stack on the end of a list is already right: O(1) push and pop.
</details>
Where else does this shape show up?
You've built two lines: one where the first in is the first out, and one where the last in is the first out. Before you open the answers, think of two places for each, in apps or in daily life.
<details> <summary>Some answers</summary>
- First in, first out: a printer's waiting jobs; a support chat's "you are number 4 in line"; a web server's waiting requests; messages sent in the order they were written; and, in Module 7, a search that explores a map ring by ring.
- Last in, first out: undo in every editor; a browser's back button; brackets and nested HTML tags, which close in the reverse order they opened; backing out of a maze the way you came; and, in Module 3, the call stack.
</details>
What Module 3 unlocks
You've now built every structure that keeps things in a line: arrays, growing arrays, linked lists, stacks and queues. Module 3, Recursion, turns to things inside things: folders inside folders, menus inside menus, replies to replies. A line can't hold that shape, and loops struggle to walk it. You'll write functions that call themselves, and you'll meet a stack you've been using all along without seeing it: the call stack, where your language keeps track of every function that's still running. It's last in, first out, exactly like the mugs.
Submit your exercise
The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.
On GitHub, click +, then New repository. Name it (for example
exercise-ds-order-line), choose Public, and click Create repository. Leave out the README: your folder already has one.In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:
git remote set-url origin https://github.com/your-name/exercise-ds-order-line.git git add . git commit -m "My solution" git push -u origin mainPaste your repo's address, such as
https://github.com/your-name/exercise-ds-order-line, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.
Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.
So what
A queue and a stack, built by you and working together at O(1) per order, is the shape of real systems: print spoolers, job runners and the order screens in actual coffee shops. You can now take a working but slow line, keep everything it does, and make it fast: the everyday job of replacing the right structure.