Queues in Python with two lists, a circular queue and collections.deque

Why it matters

These exercises test whether you understand how a queue works inside, not only which method names to call. A queue appears in breadth-first search, which finds the shortest route in a map, in network buffers that hold packets until they are sent, and in sliding-window problems that track a range of recent values. Interviewers use the two-list queue and the circular queue to see whether you can reason about order and about memory, not just recall an API.

This lesson has five parts. You will build a queue from two lists, then a fixed-size circular queue, then use collections.deque for palindrome checks, then use a queue for breadth-first search, and finally use a deque to find the maximum of every window in a list.

Python has a plain list that can hold a queue, but it is the wrong tool for the front of the queue. Removing the first item of a list with pop(0) moves every other item one place to the left, so the cost grows with the length of the list. The standard library module collections has a deque type that removes from the front in constant time. This lesson uses deque wherever the front of the queue is removed.

Words you will need

• Ring buffer: another name for a circular queue. It is a fixed block of memory used as if it were joined end to end.
• Wrap around: when an index passes the last slot of a list and comes back to slot 0.
• Remainder operator, %: the number left over after division. 7 % 3 is 1. Used with a list length, it wraps an index around the end.
• Amortized: the average cost per operation over a whole sequence. One expensive step can be paid for by many cheap ones.
• Graph: a set of points, called nodes, joined by links, called edges. A map of cities with roads between them is a graph.
• Breadth-first search (BFS): a search that visits all nodes at distance 1 before any at distance 2, then distance 3, and so on. It uses a queue.
• Window: a block of consecutive values in a list, such as the three values starting at index 2.
• Palindrome: a word that reads the same forwards and backwards, such as racecar.
• Module: a file of ready-made code. from collections import deque brings the deque type into your program.
• Class: a blueprint for an object that holds data and has methods. class StackQueue: starts one. A method is a function inside a class, and it takes self as its first parameter, which is the object itself.

The first principle: two reversals make one order

Start with a stack of plates. The plate you added last is on top. Now imagine you pour the whole stack onto a second pile, one plate at a time. The plate that was at the top is now at the bottom of the new pile, and the plate that was at the bottom is now at the top. The order has reversed.

Pour once more, and the order reverses back. Two reversals give you the original order. A queue needs the oldest item to come out first. If one stack takes items in, and a second stack gives them out, the second stack reverses the order that the first stack created. The oldest item is then on top of the second stack, and the queue rule holds.

That is the idea behind the two-stack queue. In Python, each stack is a plain list, and the top of a stack is the end of the list. The rest of this part is the careful version.

Queue from two lists

Use two lists. The _in list receives new items. The _out list gives items back. An item enters with append onto _in. To remove an item, the code checks _out. If _out is empty, it moves every item from _in into _out, one by one, with pop and append. Then it pops from _out.

The leading underscore in _in and _out is a convention. It tells other programmers that these names are for use inside the class. Python does not stop outside code from reading them. Other languages enforce this with a keyword called private. Python relies on the convention.

Here is the rule for moving items, stated with care. Move only when _out is empty. If _out still holds older items and you move more in on top of them, the newest items would come out first, and the queue order would break.

Here is a concrete case. Enqueue 1 and 2, then dequeue. The dequeue moves 2 and then 1 into _out, so _out holds 1 on top, and the dequeue returns 1. Now enqueue 3, which goes to _in, and dequeue again. _out still holds 2, so the correct answer is 2. A version that moves items on every dequeue would move 3 onto _out first. Its top would then be 3, and it would return 3, a newer item ahead of an older one. Moving only when _out is empty keeps 2 on top.

Trace the operations enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, peek, then three dequeues. The lists are written bottom to top, so the top is on the right.

At step 4, the dequeue moved 3, then 2, then 1 into _out. The moves put 3 at the bottom and 1 on the top, so the pop returned 1. Step 5 added 4 to _in, and _out was not empty, so nothing moved. Steps 7 to 9 read from _out until it was empty, and step 9 moved 4 across and then removed it.

Across the whole run, the queue gives back 1, 2, 3 and then 4, which is the queue order.

Here is the code. It has an extra peek and a way to ask whether the queue has items, which the trace above used. The method __len__ is a special name. When a class defines it, the built-in len function works on the object, and so does a plain while q: test, because Python treats an object with no items as false.

first out: 1
peek: 2
2 3 4

The method _shift is the moving step. It has an if check so that the move happens only when _out is empty. Both dequeue and peek call _shift first, so they always see the front of the queue at the top of _out. The __len__ method counts both lists, because items can sit in either one.

The code has one more detail to notice. The while q: loop in the program checks the whole queue, not one list. An item in _in is still in the queue, even when _out is empty, and __len__ respects that.

The raise statement is how a function reports an error in Python. raise IndexError("queue is empty") stops the method and tells the caller what went wrong. The caller can catch it with try and except, as with any other exception.

Why the cost is amortized O(1)

Moving items is expensive when it happens. If _in holds a million items, one dequeue moves them all. Yet the average cost per operation is still small, and the argument is simple. Each item enters _in once, moves from _in to _out at most once, and leaves _out once. So each item causes at most three steps in its whole life. Spread over all the operations, the total work is a constant times the number of operations. That is amortized O(1): one operation may be slow, but the average stays constant.

Here is what the lists look like at the worst moment. Enqueue 1, 2, 3 and 4, then dequeue once. The four items sit in _in with 4 on top. The first dequeue moves them into _out, one pop at a time, so _out ends with 1 on top and 4 at the bottom. The dequeue pops 1 and returns it, and _in is empty. That one call cost four moves. Later dequeues cost one pop each, because _out still has items.

The same argument applies to the worst case, even when the pattern looks bad. Enqueue many, dequeue once, enqueue many, dequeue once: the move happens only when _out is empty, so each item still moves at most once.

Circular queue

A plain list can hold a queue, but it wastes room. Suppose the list has five slots, and you add three items, then remove two from the front. The two free slots at the front are now empty, but a simple list queue cannot reuse them, because new items go to the end. Eventually the queue is "full" even though it holds only one item.

A circular queue, also called a ring buffer, fixes this. It treats the list as if the last slot were joined to the first. The index for a new item wraps around with %. Two numbers track the state. front is the index of the oldest item. size is the number of items. The next free slot is (front + size) % capacity.

Trace a queue with capacity 3. Start with offer 1, offer 2, offer 3, then poll, then offer 4.

After the poll, the slot at index 0 is free, and the write for 4 goes there. The position front + size is 3, which is past the last slot, so the % wraps it back to 0. That is the whole trick.

Here is the code. It keeps size separate from front. That choice matters, which you will see in the debugging section.

True True True False
full: True
1
True
2 3 4
empty: True

The [None] * capacity expression makes a list with capacity slots, all set to None. None is Python's word for "no value".

The fourth offer returns False, because the queue already holds three items. It does not raise an exception. A full queue is a normal state, and the caller decides what to do: wait, drop the item, or report a problem. Returning False leaves that choice to the caller.

The method offer writes to (front + size) % len(self._data). The method poll reads self._data[front] and moves front forward with % len(self._data). Each operation changes at most one index and one count, and each is O(1).

The reason for size becomes clear when you compare the two possible ways to tell "full" from "empty". If you track only front and the position after the last item, an empty queue and a full queue can have the same two indexes. A size counter removes that doubt, at the cost of one more number to keep right. The other common fix is to leave one slot empty on purpose, but that wastes space. With size, the list uses all of its slots.

Deque: work at both ends

A deque, pronounced "deck", is a double-ended queue. It allows adding and removing at both ends. Python's collections.deque gives you these methods:

A deque used with append and pop is a stack, because both work at the right end. A deque used with append and popleft is a queue, because items join at the right and leave at the left. The names appendleft and popleft say which end is used. Many programs prefer them when they use both ends, because the code states the end it means.

Here is a small trace. Start with an empty deque and run append(2), appendleft(1), append(3). The deque is now [1, 2, 3], read from left to right. Then popleft() returns 1 and pop() returns 3. The deque is left as [2].

Both ends are O(1), because the deque keeps track of its two ends, and it does not move the other items.

A deque is not a list. It does not support slicing. The expression d[0:2] raises an error, which the mistakes section shows. A deque can be turned into a list with list(d) when you need slices.

A deque for the palindrome check

A palindrome reads the same from both ends. To check one, you compare the first and last characters, remove them, and repeat until one or no characters are left. The deque does this in a natural way: popleft and pop give you the two ends at each step.

Type racecar into the Input box. Then type stack in a second run.

YES

For racecar, the deque starts as r a c e c a r. The loop removes the pairs r and r, then a and a, then c and c. One letter, e, is left, so the loop stops because the length is no longer greater than 1. The answer is YES. For stack, the first pair is s and k, which differ, so the answer is NO.

The loop stops when one letter is left, because a single middle letter always matches itself. An even-length word is fully paired, and the loop stops when the deque is empty. Both cases are handled by len(d) > 1.

Python gives a shorter way to check the same thing. A string can be reversed with a slice, s[::-1], and the two strings can be compared with ==. The one-line check is the right choice in a real program. The deque version is worth knowing, because it shows the two-ends pattern, and the same pattern appears in the sliding window below.

Two details matter in the code. First, deque(s) turns the string into a deque of one-character strings, and popleft returns one of them. Second, the comparison uses != on two strings, which compares their characters. Python compares the values of strings. In Python, == and != are the right tests for values, and is is not, as the mistakes section shows.

Queue for breadth-first search

Many problems can be drawn as a graph: a set of nodes with links between them. A map of cities is a graph, and so is a friendship network. Breadth-first search explores a graph in rings. It visits the start node, then every node one link away, then every node two links away, and so on. The queue is what keeps the rings in order. Nodes join the back when they are found, and the front is always the oldest unvisited node.

The rule for the search is short. Put the start node in the queue and mark it as seen. Take the front node, output it, and look at its neighbours. Each neighbour that has not been seen is marked and added to the back. Repeat until the queue is empty.

Type this into the Input box. The first line gives the number of nodes and the number of links. Each following line is one link between two nodes. The last line is the start node. Nodes are numbered from 0.

6 6
0 2
0 1
1 4
2 3
3 5
4 5
0

[0, 1, 2, 4, 3, 5]

The line adj = [[] for _ in range(n)] builds a list of n empty lists. The name adj is short for adjacency list: the neighbours of node i are in adj[i]. The underscore in for _ in range(n) means the loop variable is not used.

Trace the queue, written front on the left.

The order of visits is 0, 1, 2, 4, 3, 5. Node 4 was reached from node 1, which is one step after 0, so node 4 is two links from the start. Node 3 is also two links away, through node 2. Node 5 is three links away, reached through either 4 or 3. The order always lists the nearer nodes first, because the queue holds them in the order they were found.

BFS and depth-first search (DFS) differ in one choice. BFS takes the oldest found node from the front of a queue. DFS takes the newest found node from the top of a stack. Replace the popleft with pop in the program above, and the search goes as deep as it can along one branch before it backtracks. That is why recursion and depth-first search are closely related: the call stack is a stack.

The code sorts each neighbour list, so the output is the same on every run. Without the sort, the order depends on the order in which the links were typed. Sorting is not required for BFS to work, but it makes the answer repeatable for a grader.

Notice the seen list. It is what makes BFS finish. Without it, the search would bounce between nodes 0 and 1 forever. A node is marked seen when it joins the queue, not when it leaves, so each node enters the queue exactly once.

Sliding window maximum with a deque

A sliding window of size k moves across a list one step at a time. Suppose you want the largest value in each window. A plain approach looks at all k values for each window, which is O(n k) time. A deque makes it O(n).

The deque holds indexes of values, in a decreasing order from front to back. The front is always the index of the current window's largest value. Two cleanups happen at each step. First, remove the front index if it has slid out of the window. Second, remove from the back any index whose value is not bigger than the new value, because the new value is later and bigger, so the old one can never be the maximum again. Then add the new index at the back. Once the first window is complete, the front index is the answer for each window.

Type this into the Input box. The first line holds n and k. The second line holds the list.

8 3
1 3 -1 -3 5 3 6 7

from collections import deque
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
 
res = []
dq = deque()  # indexes; their values decrease from front to back
for i in range(n):
    while dq and dq[0] <= i - k:
        dq.popleft()  # the front index has left the window
    while dq and a[dq[-1]] <= a[i]:
        dq.pop()  # smaller values can never be a maximum again
    dq.append(i)
    if i >= k - 1:
        res.append(a[dq[0]])
print(" ".join(map(str, res)))

3 3 5 5 6 7

Trace the important steps. At i = 0, the value 1 goes in: the deque is [0]. At i = 1, the value 3 arrives. The back value 1 is not bigger than 3, so it is removed. The deque is [1]. At i = 2, the value -1 arrives. It is smaller than 3, so it goes to the back: [1, 2]. The first window 1 3 -1 is complete, and its front index 1 gives the answer 3.

At i = 4, the value 5 arrives. The front index 1 has left the window, because the window now starts at index 2, so index 1 is removed. Then the back values -3 and -1 are removed, because 5 is bigger than both. The deque becomes [4], and the answer for this window is 5. Each index enters the deque once and leaves at most once, so the whole method is O(n).

Count the cost of one index to see why. It is pushed once at the back. It leaves the deque either from the front, when it slides out of the window, or from the back, when a bigger value arrives. Either way it is removed at most once, and each removal costs O(1). Over n indexes, the total work is a fixed multiple of n.

The front is the maximum because the deque is kept in decreasing order of value, so the largest value still inside the window sits at the front.

The reason the deque stays sorted is the same as the reason the monotonic stack works in the previous lesson. A value that is smaller than a newer value can never again be a window's maximum, because it leaves the window before the newer value does.

Common mistakes

Calling push on a deque. A deque has append and appendleft, not push. Here is the real error from a program that calls push:

AttributeError: 'collections.deque' object has no attribute 'push'

The error names the type and the missing method. Use append for the right end and appendleft for the left end, and say which one you mean in the code.

Removing from the front of a list. A list has pop(0), which removes the first item, but it moves every other item one place to the left. The cost grows with the length of the list. For a queue that handles many items, use collections.deque and popleft. The program still gives the right answer with pop(0), so this mistake is easy to miss. It shows up only as slowness on large inputs.

Slicing a deque. A deque does not accept slices. Here is the real error from d[0:2] on a deque:

TypeError: sequence index must be integer, not 'slice'

Use list(d)[0:2] when you need a slice, or read the items one at a time from the ends.

Pouring at the wrong time in the two-list queue. If you move items on every dequeue, newer items land on top of older ones in _out, and the order breaks. Move only when _out is empty.

Forgetting the modulo in the circular queue. If you write self._data[self._front + self._size] = x, the index can run past the end of the list. Python then reports the error below. The fix is % len(self._data). Here is the real output from a three-slot queue that was polled once and then offered to:

1
Traceback (most recent call last):
  File "main.py", line 26, in <module>
    print(q.offer(4))
          ~~~~~~~^^^
  File "main.py", line 10, in offer
    self._data[self._front + self._size] = x
    ~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^
IndexError: list assignment index out of range

The message names the problem, a list assignment at an index that is out of range. Here front was 1 and size was 2, so front + size is 3, one past the last valid index 2. The remainder operator would have turned it into 0. The file name and line numbers depend on your program.

Reading the front of an empty queue. popleft() on an empty deque raises IndexError: pop from an empty deque. pop() on an empty list raises IndexError: pop from empty list. Check the size before you read or remove.

Confusing peek on a queue with peek on a stack. Python has no peek method on a deque or a list. The code reads the front of a deque with d[0], and the top of a stack list with stack[-1]. The two expressions look alike, and they read different ends. Write a comment that names the end, so the next reader sees which one you mean.

Using is to compare characters. The is operator checks whether two names point to the same object. It does not compare values. Two equal strings may or may not be the same object. Here is a real run that shows the difference for two equal numbers. This output comes from CPython, the usual Python, and other versions may differ:

x = 1000
y = int("1000")
print(x == y, x is y)

True False

Use == to compare values in the palindrome check and everywhere else.

Forgetting the seen list in BFS. A node that is not marked seen joins the queue again and again. The queue never empties, and the program runs forever, or until it runs out of memory.

Off by one in the window count. The sliding window has n - k + 1 answers. For n = 8 and k = 3, that is 6 answers. Making the result list too short loses the last window. Making it too long leaves extra zeros at the end, and the output then has more numbers than the question asks for.

Debugging walkthrough

Suppose you wrote the circular queue and your output for the test above is True True True False, then full: True, then 1, but the next offer returns False instead of True. Something is wrong after the poll. Trace it.

After three offers, front is 0 and size is 3. The poll returns _data[0], which is 1. It moves front to (0 + 1) % 3 = 1, and size becomes 2. The next offer should write to (1 + 2) % 3 = 0, and size should become 3, so offer returns true. If it returned false, check is_full. A common bug is decreasing size in offer by mistake, or forgetting to decrease it in poll.

To make the state visible, print the two numbers after each step: q._front and q._size. After the poll in this test, a correct program should show front as 1 and size as 2. Those two numbers tell you the next write goes to (1 + 2) % 3 = 0, which is index 0, the freed slot. If the printed front is 0 after the poll, the bug is in poll. If the printed size is still 3, size was not reduced. The printout turns a vague wrong answer into a specific, checkable number.

A second check is to print the index that offer will write to, before the write. Compare it with your trace. Most circular queue bugs appear as one wrong index, and this check finds it.

Variations and edge cases

Empty queue. poll on an empty CircularQueue raises an error, and popleft on an empty deque raises one too. Check which behaviour your code expects, and write a test for it.

Full queue. offer returns False on a full queue. Test what happens after a poll makes space, because that is where the wrap-around happens.

Window size 1. The sliding window maximum is the list itself. The deque removes every value that is not the current one, and the answers match the input.

Window size equal to n. There is exactly one window, so the output is one number, the maximum of the whole list.

Window with equal values. For [2, 2, 2], the deque removes the older equal value, so each window keeps the newest index. The answers are still right, because the value is the same.

Empty string in the palindrome. An empty string has length 0, so the loop does not run and the answer is YES. Decide whether that is what the problem wants, and say so in a comment.

Queue of one. A two-list queue with one item works the same way: the item moves from _in to _out and comes back out.

Interview view

The interview questions in this lesson follow a pattern. For a queue built from two stacks, the interviewer asks you to explain the amortized cost. Name the rule for moving items, say why each item moves at most once, and state the result as O(1) amortized. For the circular queue, the interviewer asks you to reason about full and empty. Name the two numbers you keep, and show the modulo step.

For BFS, say the words "shortest number of links" when you explain why the queue is used. A BFS from the start reaches each node the first time by the shortest route, because the rings are finished in order. For the sliding window, name the two cleanups, and say why each one keeps the deque correct. Interviewers listen for the reason, not only the code.

Follow-up questions often ask for the complexity of the whole program. For the sliding window, the answer is O(n) time and O(k) space, because the deque holds at most k indexes. For BFS, the answer is O(V + E) time, where V is the number of nodes and E is the number of links, and O(V) space for the queue and the seen list.

Real-world uses

Routing and maps. A navigation app uses BFS-like search on unweighted maps, such as counting the fewest stops in a transit network. Weighted maps need a different algorithm, which you will meet later.

Network buffers. A router keeps incoming packets in a fixed-size ring until it can send them. A full ring means the router must drop or delay packets, which is the offer returning False case.

Audio and video. Playback and recording use ring buffers to hold a few samples at a time. The writer and the reader move around the ring at their own speeds.

Rate and trend tracking. A dashboard that shows the highest value in the last ten minutes is a sliding window maximum. The deque keeps the cost low even as new readings arrive every second.

Complexity summary

The circular queue uses a fixed amount of memory, which is its strength and its limit. The sliding window deque never holds more than k indexes, so it uses memory in proportion to the window, not to the whole list.

Practice

Work through each exercise before you open its solution. Trace on paper first.

Exercise 1. Add an is_empty method to StackQueue that returns True when both lists are empty, and returns False otherwise.

Show the answer

def is_empty(self):
    return not self._in and not self._out

An empty list is false in an if test, and not turns it into True. The method returns True only when both lists are empty, because and requires both parts to be true.

Exercise 2. Add a peek_front() method to CircularQueue that returns the front item, or raises IndexError when the queue is empty.

Show the answer

def peek_front(self):
    if self._size == 0:
        raise IndexError("queue is empty")
    return self._data[self._front]

It reads the slot at front without moving front or changing size.

Exercise 3. Change the palindrome check so that it ignores case and spaces. For Never odd or even, the answer is YES.

Show the answer

from collections import deque
 
 
def is_palindrome_loose(s):
    d = deque(ch for ch in s.lower() if ch != " ")
    while len(d) > 1:
        first = d.popleft()
        last = d.pop()
        if first != last:
            return False
    return True

The string is lowered first, and spaces are skipped before anything goes into the deque. The generator expression inside deque(...) does both steps in one pass. For Hello World the answer is False.

Exercise 4. Build a stack from two queues. The push operation must put the new item in front, so that pop returns the newest item.

Show the answer

from collections import deque
 
 
class QueueStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()
 
    def push(self, x):
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1
 
    def pop(self):
        if not self.q1:
            raise IndexError("stack is empty")
        return self.q1.popleft()

Each push moves the older items behind the new one, so the front of q1 is always the newest item. The line self.q1, self.q2 = self.q2, self.q1 swaps the two names in one step. For the pushes 1, 2, 3 followed by three pops, the output is 3 2 1. The cost of push is O(n), and the cost of pop is O(1).

Exercise 5. Use BFS to print the distance from the start node to each node, in node order. For the test graph, the distances are 0 1 1 2 2 3.

Show the answer

Store a dist list alongside the seen list. When a neighbour is first seen, set its distance to the current node's distance plus 1. Use -1 to mean "not seen".

from collections import deque
 
 
def bfs_dist(n, edges, start):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    dist = [-1] * n
    queue = deque([start])
    dist[start] = 0
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist
 
 
print(bfs_dist(6, [(0, 2), (0, 1), (1, 4), (2, 3), (3, 5), (4, 5)], 0))

The output is [0, 1, 1, 2, 2, 3]. The -1 value stands for "not seen", so the dist list does the job of seen too.

Exercise 6. Predict the output of this code, then check it: d = deque(); d.appendleft(5); d.append(6); d.appendleft(7); print(d).

Show the answer

The output is deque([7, 5, 6]). appendleft(5) gives [5]. append(6) gives [5, 6]. appendleft(7) gives [7, 5, 6]. The printed form lists the items from left to right, and it names the type.

Exercise 7. Write a function that takes a list and a window size k, and returns the minimum of each window. Use a deque, and say which comparison changes from the maximum version.

Show the answer

Reverse the comparison in the back cleanup, so the deque keeps increasing values from front to back.

from collections import deque
 
 
def min_of_each_window(a, k):
    n = len(a)
    res = [0] * (n - k + 1)
    dq = deque()
    for i in range(n):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and a[dq[-1]] >= a[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            res[i - k + 1] = a[dq[0]]
    return res

The only change is >= in place of <=, so the front holds the smallest value in the window. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the answer is [-1, -3, -3, -3, 3, 3].

Exercise 8. Explain why the two-list queue dequeue is amortized O(1), not O(1) for every single call. Give an example where one call is slow.

Show the answer

When _out is empty and _in holds many items, one dequeue moves all of them, which takes O(n) time. That one call is slow. But each item moves from _in to _out only once in its life, so the total work across n operations is O(n). Averaged, each operation costs a constant amount.

Exercise 9. Write a function that returns the Josephus order for n people in a circle, removing every k-th person, using a queue. For n = 5 and k = 2, the order is 2 4 1 5 3.

Show the answer

from collections import deque
 
 
def josephus(n, k):
    q = deque(range(1, n + 1))
    order = []
    while q:
        for _ in range(k - 1):
            q.append(q.popleft())
        order.append(q.popleft())
    return order
 
 
print(josephus(5, 2))

[2, 4, 1, 5, 3]

Each person not removed goes to the back of the line. The k-th person is removed, and the loop continues. For n = 5, k = 2, the removals are 2, 4, 1, 5, 3.

Exercise 10. A teammate writes self._data[self._front + self._size] = x in offer and tests a queue with capacity 3, after one poll. What error do they see, and what is the fix?

Show the answer

After one poll, front is 1 and size is 2, so the index is 3. The list has indexes 0 to 2, so Python raises IndexError: list assignment index out of range. The fix is self._data[(self._front + self._size) % len(self._data)] = x, which wraps the index to 0.

What you now know

• A queue can be built from two lists. The second list reverses the order of the first, so the oldest item comes out first. Move items only when the output list is empty.
• The two-list queue has amortized O(1) operations, because each item moves at most once between the lists.
• A circular queue reuses space by wrapping indexes with % capacity. Keep a size count, so that full and empty are easy to tell apart.
• collections.deque works at both ends. append, appendleft, pop and popleft name the end they use, and popleft removes from the front in constant time, where pop(0) on a list does not.
• A palindrome check takes one end and the other end at each step, and stops when one or no letters are left.
• Breadth-first search uses a queue and a seen marker. It visits nodes in rings, nearest first.
• A sliding window maximum uses a deque of indexes. Each step removes indexes that left the window and indexes whose values are no longer useful, so the total cost is O(n).

The next lesson is a module assignment. It asks you to build one program that uses stacks and queues together, with a specification, a checklist, a grading rubric and a reference solution.