Two-stack window aggregation: keep FIFO order under a monoid

Operational case

Three calibrations arrive: (2,19), (3,7), and (5,11). The combined transform is (30,40). Removing the oldest returns (2,19); adding (7,23) yields a new combined transform of (8,54). If the program swapped the front and back aggregate order, additions and multiplications of the shifts would produce a different result even though a simple sum test might pass. The queue rejects a removal from an empty window. It does not support removing an arbitrary middle calibration or changing an existing entry.

Working Python program

MODULUS = 97


def compose(first, second):
    """Apply first, then second, to a reading modulo MODULUS."""
    first_scale, first_shift = first
    second_scale, second_shift = second
    return (first_scale * second_scale % MODULUS,
            (first_shift * second_scale + second_shift) % MODULUS)


IDENTITY = (1, 0)


class CalibrationWindow:
    def __init__(self):
        self.front = []
        self.back = []

    def append(self, calibration):
        prior = self.back[-1][1] if self.back else IDENTITY
        self.back.append((calibration, compose(prior, calibration)))

    def remove_oldest(self):
        if not self.front:
            while self.back:
                calibration, _ = self.back.pop()
                prior = self.front[-1][1] if self.front else IDENTITY
                self.front.append((calibration, compose(calibration, prior)))
        if not self.front:
            raise IndexError("calibration window is empty")
        return self.front.pop()[0]

    def combined(self):
        left = self.front[-1][1] if self.front else IDENTITY
        right = self.back[-1][1] if self.back else IDENTITY
        return compose(left, right)


if __name__ == "__main__":
    window = CalibrationWindow()
    for calibration in [(2, 19), (3, 7), (5, 11)]:
        window.append(calibration)
    print("first:", window.combined())
    print("removed:", window.remove_oldest())
    window.append((7, 23))
    print("second:", window.combined())

Output

first: (30, 40)
removed: (2, 19)
second: (8, 54)

Time, space, and tradeoff

Append and remove-oldest take O(1) amortized time when the aggregate operation itself is O(1): each entry enters and leaves each stack at most once. A transfer makes one removal O(N) worst-case, so latency-sensitive services need a stricter queue design or bounded transfer work. The combined aggregate is O(1) and storage is O(N). This model performs modular integer arithmetic; if aggregation produces a growing object, copying that object can dominate the stated bounds. A monotone deque is often better for a minimum specifically, while this structure accepts any associative operation with an identity.

Common Mistakes

• Do not reverse operand order for a noncommutative aggregate.
• Do not claim worst-case constant time for the transfer-triggering removal.
• Do not use an operation without associativity and an identity.
• Do not treat this FIFO interface as arbitrary-range aggregation.

Connected lessons

• Stacks and Queues
• Data Structures
• Monotonic deques: maintain a sliding minimum in linear time
• Queues: preserve arrival order without front shifts
• Disjoint sparse tables: immutable sums with constant-time queries
• Projects
• Quizzes

Compare its update and query contract with Palindromic trees: index distinct palindromes as text arrives, Segment tree beats: cap a range while retaining its sum, Wavelet matrices: count frequencies and find subarray quantiles, then complete the structure audit and decision quiz.