Build Queues and Stacks with deque
Choose FIFO or LIFO deliberately and serve queued items efficiently without changing the caller's list.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Build Queues and Stacks with deque
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
Imagine three support requests arriving in this order: Ada, Grace, and Linus. The promise is a queue, so Ada should be served first, then Grace, with Linus still waiting. That is first in, first out. It is easy to write code that stores all three names but quietly serves them in reverse order. The program still prints names and might pass a test with only one item, so we need a case where order is observable. Today we will run that bug, identify which end of the container we are using, and repair the queue with collections.deque. We will also contrast a queue with a stack, because a stack is not wrong; it solves a different ordering problem.
- 00:42
We will finish with a function that does not mutate its input and handles zero, too-large, and negative service counts. In the companion lesson, the browser console lets you try each snippet, then a checked task and quiz reinforce the rule. Before any code runs, say the expected first two names aloud. If you cannot state the order, the data structure has no clear contract. The output is Linus followed by Grace. The oldest request, Ada, has not been served at all. The loop is not off by one: it ran twice, as requested. The bug is the removal rule. list.pop with no index removes from the right end, where our newest arrival sits.
- 01:24
Repeating it implements last in, first out. That is exactly what we want for an undo stack, where the most recent action is reversed first, but it violates a customer queue. We copied arrivals, so the caller's list was protected, yet copying alone cannot repair a wrong order. We could write pop zero to remove the first list item, but every such removal shifts the rest of the list left. Over many requests that repeated shifting is unnecessary work. More important for a reader, a list does not make our two-ended intent obvious. We want append on the arrival side and a dedicated removal operation on the service side.
- 02:04
Keep the wrong output visible while choosing a fix. The symptom is not an exception; it is a plausible result with the wrong semantics. A deque, pronounced deck, allows efficient operations at both ends. popleft removes Ada, the oldest item on the left. pop removes Linus, the newest item on the right. Grace remains in between. That little run proves which operation matches our queue contract without asking us to trust a slide. If we add new arrivals with append, they join the right end; serving with popleft consumes the left end. For a stack, we could use append and pop on the same right end, whether the container is a deque or an ordinary list.
- 02:47
The key is the pair of operations, not the name of the variable. Notice that printing a deque directly would show a deque representation. Converting to list is convenient when the public function promises ordinary lists in its result. The deque is our internal processing tool. If the queue becomes empty, popleft raises IndexError, so a real service loop must check for remaining items before removing. The next function will also decide what zero and negative counts mean. Making those cases explicit helps a future caller understand whether the method stops, rejects, or silently does something else.
- 03:28
The first result now serves Ada and Grace, leaving Linus. The second request asks for five services when only Ada is waiting. The loop stops when waiting becomes empty, so there is no IndexError. Before constructing the deque, the function rejects a negative count with ValueError. That avoids treating a negative request as a mysterious special slice length. The function copies names into a new deque; every popleft changes that internal container, not the caller's list. We return two ordinary lists because that is what the task contract promises. The condition checks both facts that matter: someone remains in the queue and we have not reached the requested count.
- 04:11
The body removes exactly one oldest item and appends it to served. Those are the two ends to remember. This function is intentionally small, but the design scales conceptually: an event loop can receive new jobs on the right and serve old jobs on the left. A production queue shared across threads or processes needs additional coordination, persistence, and failure handling. This lesson focuses on deterministic in-memory ordering so we can prove the behavior before adding those complications. The checks cover the central FIFO promise, both count boundaries, and the caller's unchanged list.
- 04:51
Asking for zero serves nobody; asking for eight with only three names serves those three and stops. The negative case must raise ValueError. We catch that expected exception and fail the check if it never arrives, so success cannot hide a missing guard. The output is one confirmation line, but the assertions behind it are what make the claim meaningful. Now try the browser task yourself. Start with a deque copy of the names, choose popleft for serving, and return the remaining deque as a list. If a check fails, print one short queue before and after each removal and name the end you touched. Then answer the quiz: append plus popleft is a queue; append plus pop is a stack.
- 05:34
A list can be an excellent stack, and a deque can do either job. Use the operation that matches the promise. The most common mistake is to focus on the container name while overlooking the order people or jobs actually leave it. A three-item example makes that mistake visible immediately.
Understand the concept
A queue serves the oldest item first: first in, first out. A stack removes the newest item first: last in, first out. Both can hold the same values, so a program may appear correct until the order matters. A list's pop() removes from the right and therefore implements stack behavior. collections.deque supports append() on the right and popleft() on the left, which makes queue intent explicit.
A deque is designed for efficient additions and removals at either end. Removing the first element of a list with pop(0) shifts the remaining elements, which becomes expensive when repeated for a large queue. Deque indexing in the middle is not its strength; use a list when random access is the main requirement. Choose the container from the operations the program actually performs.
In the task, names arrive in order. serve_queue(names, count) returns two lists: the first count names served in FIFO order and the names still waiting. It copies the input into a deque so the caller's original list remains unchanged. A count of zero serves nobody, and a count larger than the queue length serves everyone. A negative count is rejected rather than silently interpreted as a slice index.
A stack is still useful for undo, depth-first traversal, and nested parsing. A deque can implement a stack with append() and pop(), but a plain list is often enough for that pattern. The important skill is to state which end receives new items and which end removes them, then verify a case with at least three distinct values.
- Queue: append right and popleft left
- Stack: append and pop on the same end
- deque avoids repeated list shifting at the front
- Copy mutable input when the function promises not to change it
See it step by step
Read the code, predict the output, then compare it with the result.
01. Observe FIFO and LIFO on the same input
from collections import deque
queue = deque(['Ada', 'Grace', 'Linus'])
stack = ['Ada', 'Grace', 'Linus']
print(queue.popleft(), queue.popleft())
print(stack.pop(), stack.pop())Ada Grace
Linus Gracepopleft serves the oldest names; list.pop removes the newest names.
02. Keep the caller's list unchanged
from collections import deque
arrivals = ['red', 'blue', 'green']
waiting = deque(arrivals)
served = [waiting.popleft() for _ in range(2)]
print(served)
print(list(waiting))
print(arrivals)['red', 'blue']
['green']
['red', 'blue', 'green']deque(arrivals) makes a separate container, so serving does not remove elements from arrivals.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
Name the removal rule before choosing a container
A queue and a stack can begin with identical data, so choose by the promised removal order. New arrivals go to the right. For a queue, popleft removes the oldest arrival on the left. For a stack, pop removes the most recent addition on the right. Predict the two names below before running the program.
The example leaves Grace in the deque after serving Ada from the left and Linus from the right. Real systems might use only one of those policies at a time; mixing them here is a controlled way to make the ends visible. A list with append and pop is a reasonable stack, while deque makes both-end operations explicit.
from collections import deque
waiting = deque(['Ada', 'Grace', 'Linus'])
print(waiting.popleft())
print(waiting.pop())
print(list(waiting))Ada
Linus
['Grace']- Ada arrived first and leaves through popleft.
- Linus was newest and leaves through pop.
- Grace remains between the two ends.
Copy arrivals so service does not mutate input
When a function receives a list owned by its caller, mutating it can surprise code that wants to print or reuse the original arrivals. Constructing deque(arrivals) creates a separate container. The deque holds references to the same immutable strings, but removing from the deque does not remove entries from the original list.
Serve two people, display the remaining queue, then compare with the original arrivals. This is a small example of a useful API contract: the function returns its own result and leaves supplied data as it was. For mutable elements inside the list, a shallow copy does not clone those elements, so keep this promise scoped to the container.
from collections import deque
arrivals = ['Ada', 'Grace', 'Linus']
queue = deque(arrivals)
served = [queue.popleft() for _ in range(2)]
print(served)
print(list(queue))
print(arrivals)['Ada', 'Grace']
['Linus']
['Ada', 'Grace', 'Linus']- deque(arrivals) creates a separate container.
- Each popleft serves the oldest waiting person.
- The source list still has all three arrivals.
Make boundary behavior part of the queue contract
A practical queue method should define what happens when a request asks for no service, more service than available, or a negative number. We choose zero to return an empty served list, a large count to stop when the queue empties, and a negative count to raise ValueError. Those choices are explicit instead of accidental loop behavior.
The loop condition checks both the remaining count and the queue itself. A deque is false when empty, so it prevents popleft from raising IndexError. Returning lists makes the result easy to display and compare in the browser task checker. Add a fourth name and predict both returned lists before running the changed code.
from collections import deque
def serve_queue(names, count):
if count < 0:
raise ValueError('count must be nonnegative')
waiting = deque(names)
served = []
while waiting and len(served) < count:
served.append(waiting.popleft())
return served, list(waiting)
print(serve_queue(['Ada', 'Grace', 'Linus'], 2))
print(serve_queue(['Ada'], 5))(['Ada', 'Grace'], ['Linus'])
(['Ada'], [])- Reject negative requests before touching the queue.
- Stop when either the request is satisfied or the deque is empty.
- Return both served and waiting items without changing names.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Copy names into deque(names). Repeat popleft() while both the queue and the remaining count allow it. Convert the deque to a list for the waiting result. Check negative count before processing.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
Using stack removal for a queue
waiting = ['Ada', 'Grace', 'Linus']
next_name = waiting.pop()from collections import deque
waiting = deque(['Ada', 'Grace', 'Linus'])
next_name = waiting.popleft()What happens: Linus is served before Ada.
A FIFO queue removes from the opposite end from append.
Shifting a list for every request
while waiting:
served.append(waiting.pop(0))waiting = deque(waiting)
while waiting:
served.append(waiting.popleft())What happens: Each front removal shifts the remaining list items.
deque provides efficient operations at both ends.