Queues

A variable-size array optimized for the ends

A queue is declared with [$] — int q[$] — and is the container to reach for whenever elements arrive and leave over time. The simulator implements it so that adding or removing at either end is O(1) , while insertion in the middle costs O(n). Unlike a dynamic array there is no allocation step: a queue starts empty and grows one element per push. The special index $ means “last element”, so q[$] is the back and q[0] the front.

module queue_demo;
  int q[$];

  initial begin
    q.push_back(10);       // {10}
    q.push_back(20);       // {10, 20}
    q.push_front(5);       // {5, 10, 20}
    q.insert(1, 7);        // {5, 7, 10, 20}  insert before index 1
    q.delete(2);           // {5, 7, 20}      remove index 2

    $display("front=%0d back=%0d size=%0d", q[0], q[$], q.size());

    while (q.size() > 0)
      $display("popped %0d", q.pop_front()); // FIFO drain order

    // Slicing: q[1:$] is everything but the front element
    q = {1, 2, 3, 4, 5};
    q = q[1:$];            // drop front -> {2,3,4,5}
    q = q[0:$-1];          // drop back  -> {2,3,4}
    q = {q, 99};           // concat-append -> {2,3,4,99}
    q.delete();            // empty the whole queue
  end
endmodule

Bounded queues and slicing semantics

Declaring int q[$:7] creates a bounded queue with maximum index 7, i.e. at most 8 elements. Pushing beyond the bound is ignored and the simulator issues a warning — it does not error out, which makes silent data loss the real hazard. Bounded queues are useful for modeling hardware FIFOs with real depth limits, but most testbench queues are unbounded and rely on the consumer keeping up. Slices like q[1:$] produce a new queue value; combined with concatenation they give you list surgery without explicit loops.

QUEUE OPERATIONS AND COSTS

            push_front / pop_front          push_back / pop_back
                  O(1)                              O(1)
                   │                                 │
                   ▼                                 ▼
  front ──► ┌─────┬─────┬─────┬─────┬─────┬─────┐ ◄── back
            │q[0] │q[1] │q[2] │ ... │     │q[$] │
            └─────┴─────┴──┬──┴─────┴─────┴─────┘
                           │
                  insert(i,v) / delete(i)
                      O(n) — shifts elements

  bounded:  int q[$:7];   push #9 → DROPPED + warning (no error!)
  slicing:  q[1:$]  drop front     q[0:$-1]  drop back

Queues as testbench FIFOs — the scoreboard pattern

The single most important queue idiom is the scoreboard expected queue : the reference side pushes predicted transactions with push_back, the monitor side pops with pop_front, and in-order checking falls out of FIFO discipline. At end of test, a non-empty queue means the DUT dropped transactions — so checking residual size() is part of the pattern, not an afterthought. Interviewers often ask exactly this: “how would you check in-order data integrity through a DUT?” and expect the two-queue (or queue-per-stream) answer.

class scoreboard;
  packet expected_q[$];   // reference model pushes here

  function void write_expected(packet p);
    expected_q.push_back(p);
  endfunction

  function void write_actual(packet p);
    packet exp;
    if (expected_q.size() == 0) begin
      $error("Unexpected packet: DUT produced output with nothing predicted");
      return;
    end
    exp = expected_q.pop_front();   // in-order check
    if (!exp.compare(p))
      $error("Mismatch: exp=%s act=%s", exp.convert2string(), p.convert2string());
  endfunction

  function void check_drained();
    if (expected_q.size() != 0)
      $error("%0d expected packets never seen at DUT output",
             expected_q.size());
  endfunction
endclass

Key takeaways

• Queues grow per push — no new[] step; O(1) at both ends, O(n) in the middle.

• $ indexes the last element; q[1:$] and concatenation give loop-free list surgery.

• Bounded queues ([$:N]) silently drop overflow pushes with only a warning.

• push_back / pop_front is the canonical in-order scoreboard FIFO — check residual size() at end of test.

Common pitfalls

• pop_front() on an empty queue — returns the default value plus a warning, easy to misread as real data.

• Using insert/delete in hot loops — each call shifts elements, turning O(1) FIFO code into O(n²).

• Forgetting the end-of-test drain check — dropped DUT transactions go unnoticed.

• Deleting elements inside a foreach over the same queue — iteration indices shift under you.