Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Queue & Deque

Guide 2 of 6 · Path 2 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Easyqueue-deque

Moving Average from Data Stream

Problem (restated)

Given window size, stream integers via next(val). Return the average of the last at most size values.

Intuition

Queue holds the window; maintain running sum; drop oldest when full.

Approaches

Fixed-size window queue

Tested only
Time O(1) nextSpace O(size)

Idea. Enqueue val, add to sum; if count > size dequeue and subtract; return sum/count.

Walkthrough. size=3: 1 → 1; 10 → 5.5; 3 → 4.666…; 5 → 6.

Trade-offs. Circular buffer avoids shift costs in some languages.

Solution
export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

Template connection

Queue / deque rolling window aggregate.

Reflection