Ring Buffer Deque
Problem
Design a double-ended queue whose capacity is fixed when it is created. push_front and push_back add a value and return True, or return False without adding anything when the queue is full; pop_front and pop_back remove and return a value, or return None when the queue is empty. Every operation must take O(1) time, so no stored value may ever be shifted.
Examples
Operations: RingDeque(3), push_back 1, push_back 2, push_front 0, push_back 9
Results: True, True, True, False
Why: the fourth push finds all three cells takenOperations: pop_back, pop_front, pop_front, pop_front (continuing)
Results: 2, 0, 1, None
Why: front to back the queue held 0, 1, 2Operations: RingDeque(1), push_front 5, pop_back
Results: True, 5
Why: edge case, with one cell the front and the back are the same slotHints
0 / 3
A plain list makes adding at the front cost O(n), because everything after it shifts. Instead, keep the values still and move the idea of where the front is.
Store the values in a fixed array together with a head index and a size. Any index that runs past either end wraps around using the modulo of the capacity.
Pushing at the front moves head one step back, wrapping, and writes there. Pushing at the back writes at head plus size, wrapped. Popping at the front reads at head and moves it forward; popping at the back shrinks size and reads the slot just past the new end. Check for full or empty first.
Solution
The values never move: a head index and a size describe where the live run sits inside a fixed array, and the modulo folds any index past either end back into range. Python's modulo returns a non-negative result for a negative left side, so (head - 1) % capacity steps back from index 0 to the last cell. The back value always sits at head + size - 1, wrapped, so both ends are reachable in constant time. Every operation is O(1) time, and space is O(capacity).
class RingDeque:
def __init__(self, capacity):
self.buf, self.head, self.size = [None] * capacity, 0, 0
def push_front(self, x):
if self.size == len(self.buf): return False
self.head = (self.head - 1) % len(self.buf) # step back, wrapping to the end
self.buf[self.head] = x
self.size += 1
return True
def push_back(self, x):
if self.size == len(self.buf): return False
self.buf[(self.head + self.size) % len(self.buf)] = x
self.size += 1
return True
def pop_front(self):
if not self.size: return None
x, self.head = self.buf[self.head], (self.head + 1) % len(self.buf)
self.size -= 1
return x
def pop_back(self):
if not self.size: return None
self.size -= 1 # the back slot is just past the new end
return self.buf[(self.head + self.size) % len(self.buf)]
d = RingDeque(3)
print(d.push_back(1), d.push_back(2), d.push_front(0), d.push_back(9)) # -> True True True False
print(d.pop_back(), d.pop_front(), d.pop_front(), d.pop_front()) # -> 2 0 1 None
one = RingDeque(1)
print(one.push_front(5), one.pop_back()) # -> True 5Stuck on the idea rather than the code? Circular Queue covers it.