Queues
push/pop, bounded queues, slicing, insert/delete, FIFO modeling.
Module 3 · Page 3.4
The Array That Thinks Like a List
A queue is a variable-size ordered collection. Unlike a dynamic array — where you resize by calling new[] explicitly — a queue grows and shrinks automatically as you push and pop elements. Unlike an associative array, it maintains insertion order and gives you integer-indexed random access at any position. It is the hybrid: dynamic sizing of a list, indexed access of an array.
In verification, queues show up constantly. The scoreboard that accumulates expected transactions as the driver sends them uses a queue. The FIFO behavior checker that captures data on write and compares on read uses a queue. The UVM sequence that builds an ordered list of items before driving them uses a queue. The [$] declaration suffix is one of the first things you encounter when reading professional SV testbench code.
The one piece of queue syntax that surprises engineers: q[$] does not declare a queue of queues — it is how you write the type of a single queue. And inside an expression, q[$] means the last element of queue q. Same syntax, two completely different meanings depending on context. Always check which one you're reading.
How Queues Work — The Mental Model
Think of a queue as a dynamic array that has efficient insertion and removal at both ends. Position 0 is the front (head); position q.size()-1 or equivalently q[$] is the back (tail). push_back() appends to the tail — standard FIFO behavior. push_front() inserts at the head. pop_front() removes and returns the head element — also standard FIFO dequeue. pop_back() removes and returns the tail — LIFO (stack) behavior.
Beyond push/pop, queues support everything dynamic arrays do: indexed access, whole-queue assignment with =, comparison with == and !==, foreach iteration, and slicing. You can also use concatenation-style syntax to build or modify queues. The insert(i, val) and delete(i) methods give you arbitrary position insertion and removal in O(N) time.
- push_back / pop_front — Standard FIFO: enqueue at back, dequeue from front. Models hardware FIFOs, protocol pipelines, ordered event logs.
- push_front / pop_back — Standard LIFO stack: push and pop from opposite ends, or use as a double-ended deque with full front/back access.
- q[i] — Random access — Index any position. q[0] = front, q[$] = back, q[$-1] = second from back. No need to pop just to peek.
- [$:N] — Bounded queue — Maximum N+1 elements. Useful for modeling bounded hardware FIFOs where overflow is an error condition. size() ≤ N+1.
Syntax — Every Operation You'll Use
// ── Declaration ──────────────────────────────────────────────────
int fifo [$]; // unbounded queue of ints
string names [$]; // unbounded queue of strings
logic [7:0] bytes [$]; // unbounded queue of bytes
int bfifo [$:15]; // bounded: max 16 elements (0..15)
// ── Push — add elements ──────────────────────────────────────────
fifo.push_back(10); // [10]
fifo.push_back(20); // [10, 20]
fifo.push_front(5); // [5, 10, 20]
// ── Pop — remove and return ───────────────────────────────────────
int v = fifo.pop_front(); // v=5 queue=[10, 20]
int t = fifo.pop_back(); // t=20 queue=[10]
// ── Indexed access ────────────────────────────────────────────────
fifo[0] // front element (same as peek without removing)
fifo[$] // last element ($ = size-1)
fifo[$-1] // second from last
// ── Size ──────────────────────────────────────────────────────────
fifo.size() // number of current elements
$size(fifo) // equivalent
// ── insert / delete at arbitrary position ────────────────────────
fifo.insert(1, 99); // insert 99 at index 1 — shifts rest right
fifo.delete(0); // delete element at index 0 — shifts rest left
fifo.delete(); // delete ALL elements (clear)
// ── Slice — range of elements ────────────────────────────────────
int first3 [$] = fifo[0:2]; // elements 0, 1, 2 as a new queue
int last2 [$] = fifo[$-1:$]; // last two elements
// ── Concatenation-style build ────────────────────────────────────
fifo = {fifo, 100}; // append 100 to back (same as push_back)
fifo = {0, fifo}; // prepend 0 to front (same as push_front)
// ── foreach and whole-queue operations ───────────────────────────
foreach (fifo[i]) $display("%0d", fifo[i]);
int copy [$] = fifo; // whole-queue deep copy
if (fifo == copy) $display("equal");| Method | Action | Returns | Queue after (was [10, 20, 30]) |
|---|---|---|---|
push_back(val) | Append to tail | void | [10, 20, 30, val] |
push_front(val) | Prepend to head | void | [val, 10, 20, 30] |
pop_front() | Remove and return head | 10 | [20, 30] |
pop_back() | Remove and return tail | 30 | [10, 20] |
insert(i, val) | Insert at index i | void | [10, val, 20, 30] for i=1 |
delete(i) | Remove element at index i | void | [20, 30] for i=0 |
delete() | Remove all elements | void | [] |
size() | Current element count | int | 3 (unchanged) |
Visual — FIFO Operations Step by Step
Queue State After Each Operation
| Step | Operation | Queue contents [front → back] | size() | Returned value |
|---|---|---|---|---|
| 0 | Initial (empty) | [ ] | 0 | — |
| 1 | push_back(10) | [10] | 1 | — |
| 2 | push_back(20) | [10, 20] | 2 | — |
| 3 | push_back(30) | [10, 20, 30] | 3 | — |
| 4 | push_front(5) | [5, 10, 20, 30] | 4 | — |
| 5 | pop_front() | [10, 20, 30] | 3 | 5 |
| 6 | pop_back() | [10, 20] | 2 | 30 |
| 7 | insert(1, 15) | [10, 15, 20] | 3 | — |
| 8 | q[$] | [10, 15, 20] (unchanged) | 3 | 20 (read last) |
| 9 | delete(0) | [15, 20] | 2 | — |
$ Index — The Last-Element Shorthand
| Queue contents | Expression | Resolves to | Value |
|---|---|---|---|
| [10, 20, 30, 40] | q[$] | q[3] (size-1) | 40 |
| [10, 20, 30, 40] | q[$-1] | q[2] | 30 |
| [10, 20, 30, 40] | q[0] | q[0] | 10 (front) |
| [10, 20, 30, 40] | q[1:2] | Slice [20, 30] | Queue of 2 elements |
| [10, 20, 30, 40] | q[$-1:$] | Slice [30, 40] | Last two elements |
| [ ] (empty) | q[$] | Out-of-bounds — fatal error | — |
Bounded Queue Behavior
| Declaration | Max elements | push_back when full | Use case |
|---|---|---|---|
int q [$] | Unlimited | Always succeeds | General-purpose event/transaction queues |
int q [$:3] | 4 (indices 0..3) | Tool-dependent: may drop or error | FIFO overflow modeling; model capacity constraints |
int q [$:0] | 1 | Drops or errors when already 1 element | Single-entry buffer model |
Code Examples — FIFOs to Verification Pipelines
Example 1 — Beginner: Core Queue Operations
module tb_queue_basics;
int q [$];
initial begin
// ── Build the queue ───────────────────────────────────────────
q.push_back(10);
q.push_back(20);
q.push_back(30);
q.push_front(5);
$display("After pushes: %p size=%0d", q, q.size()); // '{5,10,20,30} 4
// ── Indexed access without removing ──────────────────────────
$display("front=q[0]=%0d back=q[$]=%0d", q[0], q[$]); // 5 30
// ── FIFO dequeue ──────────────────────────────────────────────
$display("pop_front = %0d", q.pop_front()); // 5
$display("pop_front = %0d", q.pop_front()); // 10
$display("Queue now: %p", q); // '{20,30}
// ── insert at arbitrary position ─────────────────────────────
q.insert(1, 25);
$display("After insert(1,25): %p", q); // '{20,25,30}
// ── slice ────────────────────────────────────────────────────
int tail [$] = q[$-1:$];
$display("Last 2 elements: %p", tail); // '{25,30}
// ── Concatenation-style append ───────────────────────────────
q = {q, 99};
$display("After concat append: %p", q); // '{20,25,30,99}
// ── Clear ─────────────────────────────────────────────────────
q.delete();
$display("After delete: size=%0d", q.size()); // 0
$finish;
end
endmoduleExpected output:
After pushes: '{5, 10, 20, 30} size=4
front=q[0]=5 back=q[$]=30
pop_front = 5
pop_front = 10
Queue now: '{20, 30}
After insert(1,25): '{20, 25, 30}
Last 2 elements: '{25, 30}
After concat append: '{20, 25, 30, 99}
After delete: size=0Example 2 — Intermediate: FIFO Behavioral Model
// Behavioral model of a 4-deep, 8-bit FIFO
module tb_fifo_model;
parameter int DEPTH = 4;
logic [7:0] fifo [$:3]; // bounded: max 4 entries (0..3)
task automatic enqueue(input logic [7:0] d);
if (fifo.size() >= DEPTH) begin
$error("FIFO OVERFLOW — capacity %0d, tried to push 0x%02h", DEPTH, d);
return;
end
fifo.push_back(d);
$display("PUSH 0x%02h [depth=%0d/%0d]", d, fifo.size(), DEPTH);
endtask
task automatic dequeue(output logic [7:0] d);
if (fifo.size() == 0) begin
$error("FIFO UNDERFLOW — cannot pop from empty FIFO");
d = 8'hXX;
return;
end
d = fifo.pop_front();
$display("POP 0x%02h [depth=%0d/%0d]", d, fifo.size(), DEPTH);
endtask
function automatic bit is_full(); return fifo.size() >= DEPTH; endfunction
function automatic bit is_empty(); return fifo.size() == 0; endfunction
logic [7:0] d_out;
initial begin
enqueue(8'hAA); enqueue(8'hBB); enqueue(8'hCC); enqueue(8'hDD);
enqueue(8'hEE); // overflow!
dequeue(d_out); dequeue(d_out);
$display("is_full=%0b is_empty=%0b", is_full(), is_empty());
$finish;
end
endmoduleExpected output:
PUSH 0xAA [depth=1/4]
PUSH 0xBB [depth=2/4]
PUSH 0xCC [depth=3/4]
PUSH 0xDD [depth=4/4]
ERROR: FIFO OVERFLOW — capacity 4, tried to push 0xEE
POP 0xAA [depth=3/4]
POP 0xBB [depth=2/4]
is_full=0 is_empty=0Example 3 — Verification: Ordered Scoreboard and Stimulus Queue
module tb_scoreboard_queue;
typedef struct {
logic [7:0] opcode;
logic [31:0] data;
} txn_t;
txn_t expected [$]; // in-order expected transactions
txn_t received [$]; // captured DUT responses
int mismatch_cnt = 0;
// Driver: enqueue expected transactions as they are sent
task automatic send_txn(input txn_t t);
expected.push_back(t);
endtask
// Monitor: enqueue captured responses
task automatic capture_txn(input txn_t t);
received.push_back(t);
endtask
// In-order compare: drain both queues together
task automatic drain_and_compare();
while (expected.size() > 0 && received.size() > 0) begin
txn_t exp = expected.pop_front();
txn_t got = received.pop_front();
if (exp.opcode !== got.opcode || exp.data !== got.data) begin
$error("MISMATCH: exp={op:0x%02h d:0x%08h} got={op:0x%02h d:0x%08h}",
exp.opcode, exp.data, got.opcode, got.data);
mismatch_cnt++;
end else
$display("PASS op=0x%02h data=0x%08h", got.opcode, got.data);
end
if (expected.size() != 0)
$error("%0d expected transactions with no matching response", expected.size());
if (received.size() != 0)
$error("%0d unexpected responses from DUT", received.size());
endtask
initial begin
send_txn('{8'h10, 32'hAAAA_0001});
send_txn('{8'h20, 32'hBBBB_0002});
capture_txn('{8'h10, 32'hAAAA_0001}); // match
capture_txn('{8'h20, 32'hCCCC_0002}); // data mismatch
drain_and_compare();
$display("Total mismatches: %0d", mismatch_cnt);
$finish;
end
endmoduleExpected output:
PASS op=0x10 data=0xAAAA0001
ERROR: MISMATCH: exp={op:0x20 d:0xBBBB0002} got={op:0x20 d:0xCCCC0002}
Total mismatches: 1Example 4 — Corner Case: $-Indexing, pop_front on Empty, Queue Sorting
module tb_queue_corners;
int q [$];
initial begin
// ── $ index: last element shorthand ──────────────────────────
q = '{10, 20, 30, 40};
$display("q[$] = %0d (last)", q[$]); // 40
$display("q[$-1] = %0d (2nd last)", q[$-1]); // 30
$display("q[$-2] = %0d (3rd last)", q[$-2]); // 20
// ── Safe pop: check size first ───────────────────────────────
q.delete();
if (q.size() > 0)
$display("popped: %0d", q.pop_front());
else
$display("Queue empty — pop guarded");
// ── Sorting: sort() and rsort() work on queues ───────────────
q = '{50, 10, 40, 20, 30};
q.sort();
$display("Sorted asc: %p", q); // '{10,20,30,40,50}
q.rsort();
$display("Sorted desc: %p", q); // '{50,40,30,20,10}
// ── Building from array literal ───────────────────────────────
int arr [5] = '{1,2,3,4,5};
int q2 [$];
foreach (arr[i]) q2.push_back(arr[i]);
$display("From array: %p", q2); // '{1,2,3,4,5}
// ── Using queue as collect-keys buffer (from assoc array) ─────
int aa [string];
string keys [$];
aa["z"]=3; aa["a"]=1; aa["m"]=2;
foreach (aa[k]) keys.push_back(k); // collect sorted keys
$display("Keys: %p", keys); // '{a, m, z}
$finish;
end
endmoduleExpected output:
q[$] = 40 (last)
q[$-1] = 30 (2nd last)
q[$-2] = 20 (3rd last)
Queue empty — pop guarded
Sorted asc: '{10, 20, 30, 40, 50}
Sorted desc: '{50, 40, 30, 20, 10}
From array: '{1, 2, 3, 4, 5}
Keys: '{"a", "m", "z"}Simulation Behavior — What the Simulator Does
Pop on Empty Queue: Fatal Error
Like dynamic arrays, calling pop_front() or pop_back() on an empty queue is a fatal error that terminates simulation. There is no "return X" behavior — it crashes. Similarly, accessing q[$] when the queue is empty is an out-of-bounds access on an empty array. Always guard with q.size() > 0 before any pop in code that might encounter an empty queue.
Queues and the Constraint Solver
Queues have limited support in constraint blocks compared to dynamic arrays. You cannot write constraint { q.size() == len; } and have the solver automatically grow the queue the way it does for dynamic arrays. If you need a variable-size array in a rand class, use a dynamic array rand type data [] with a size constraint. Use queues for post-randomization collection and processing, not for constrainable size.
| Operation | Queue behavior | Dynamic array equivalent |
|---|---|---|
| Pop from empty | Fatal error | Fatal error (out-of-bounds) |
| Access q[$] on empty | Fatal error | Fatal error (index > size) |
| push_back / push_front | O(1) amortized — efficient | newN+1 — O(N) copy |
| insert(i, v) at middle | O(N) — shifts all elements after i | No direct equivalent |
| Random indexed read q[i] | O(1) | O(1) |
| Constraint solver support | Limited — cannot constrain size directly | Full — data.size() == len works |
Where Queues Belong in Real Verification
// ── 1. IN-ORDER SCOREBOARD ─────────────────────────────────────────
txn_t exp_q [$]; // driver enqueues expected; monitor dequeues for comparison
// Driver: exp_q.push_back(txn);
// Monitor: if (exp_q.size()>0) { txn_t e = exp_q.pop_front(); compare(e, got); }
// ── 2. UVM SEQUENCE: dynamic stimulus list ─────────────────────────
// class my_sequence extends uvm_sequence;
// my_item items [$];
// task body();
// foreach (items[i]) `uvm_do(items[i]);
// endtask
// endclass
// ── 3. PIPELINE DEPTH TRACKING ─────────────────────────────────────
int pipeline [$]; // models DUT pipeline: push on accept, pop on output
always @(posedge clk) begin
if (valid_in) pipeline.push_back(data_in);
if (valid_out && pipeline.size()>0) pipeline.pop_front();
end
// ── 4. COLLECTING KEYS FOR SAFE AA DELETE ─────────────────────────
int map [string];
string expired [$];
foreach (map[k]) if (map[k] < threshold) expired.push_back(k);
foreach (expired[i]) map.delete(expired[i]); // safe: not during AA iteration
// ── 5. LAST-N TRANSACTIONS (sliding window) ───────────────────────
parameter int WINDOW = 8;
logic[31:0] recent [$];
// In monitor:
// recent.push_back(data);
// if (recent.size() > WINDOW) void'(recent.pop_front()); // keep last N
// ── 6. ASSERTION HELPER: N-CYCLE DELAY MODEL ─────────────────────
int delay_q [$];
// Verify that output matches input delayed by exactly N cycles:
// always @(posedge clk) begin
// delay_q.push_back(data_in);
// if (delay_q.size() > LATENCY)
// assert(data_out === delay_q.pop_front());
// endBugs Engineers Hit With Queues
Bug 1 — Accessing q[$] or pop on Empty Queue
int q [$]; // empty
// BUGGY: pop on empty queue — FATAL
int v = q.pop_front(); // Fatal: "pop_front of empty queue"
// BUGGY: $ index on empty queue — FATAL
int last = q[$]; // Fatal: out-of-bounds (size=0, index=-1)
// CORRECT: always check size before pop or $ access
if (q.size() > 0) v = q.pop_front();
if (q.size() > 0) last = q[$];Bug 2 — $ in Declaration vs Expression — The Same Syntax, Two Meanings
// ── Context 1: Declaration — [$] declares a queue type ───────────
int q [$]; // DECLARATION: q is an unbounded queue of int
int b [$:7]; // DECLARATION: b is a bounded queue (max 8 elements)
// ── Context 2: Expression — q[$] accesses the last element ───────
q = '{10, 20, 30};
int last = q[$]; // EXPRESSION: last = 30 (last element, index = size-1)
int prev = q[$-1]; // EXPRESSION: prev = 20 (second from last)
// ── Common confusion: thinking q[$] declares a 1-element queue ───
// q[$] in an expression is NOT a 1-element bounded queue declaration
// It is reading the LAST ELEMENT of q
$display("q[$] = %0d", q[$]); // 30 — always the last element
// ── Another trap: modifying via $ index ──────────────────────────
q[$] = 99; // modifies the last element in-place — queue[2] = 99
$display("%p", q); // '{10, 20, 99}Bug 3 — In-Order Scoreboard Stalls When DUT Drops a Transaction
// In-order scoreboard compares front of expected vs front of received
// If DUT drops transaction 2, received contains [T1, T3, T4]
// Expected still has [T1, T2, T3, T4]
// Comparison: T1==T1 PASS, T2 vs T3 FAIL, T3 vs T4 FAIL ... cascade!
// Every subsequent comparison after the drop is a false mismatch
// This is why in-order scoreboards are appropriate ONLY when the DUT
// guarantees in-order, no-drop behavior. For potentially out-of-order
// or drop-possible designs, use an associative array scoreboard instead
// (see section 3.3) keyed by transaction ID.
// DETECTION: at end-of-test, check both queues empty
if (expected.size() != 0)
$error("%0d unmatched expected transactions — DUT may have dropped",
expected.size());
if (received.size() != 0)
$error("%0d extra responses — DUT sent more than expected",
received.size());Bug 4 — Using Queue Size Constraint in rand Class
class bad_txn;
rand logic [7:0] data [$]; // queue — not constraint-solver-friendly for size
rand int len;
// BUGGY: solver cannot allocate queue size the same way as dynamic array
constraint sz { data.size() == len; } // tool-dependent — may not work
endclass
// CORRECT: use a dynamic array for variable-size rand data fields
class good_txn;
rand logic [7:0] data []; // dynamic array — works with constraint solver
rand int len;
constraint sz { len inside {[1:16]}; data.size() == len; } // works
endclass
// After randomizing good_txn, copy data into a queue if queue behavior needed:
// int q [$];
// foreach (good_txn.data[i]) q.push_back(good_txn.data[i]);Interview Questions
Beginner Level
Q1: What does q[$] mean when used in an expression versus in a declaration? In a declaration, int q [$] declares an unbounded queue of integers. In an expression, q[$] refers to the last element of the queue — equivalent to q[q.size()-1]. Same syntax, completely different meaning. q[$-1] in an expression gives the second-to-last element. Q2: What is the difference between int q [$] and int q [$:7]?int q [$] is an unbounded queue — it grows without limit. int q [$:7] is a bounded queue with a maximum of 8 elements (indices 0 to 7). Pushing to a bounded queue that is already full has tool-dependent behavior — some simulators drop the element silently, others report an error. Bounded queues are used when modeling hardware FIFOs with fixed depth where overflow is an error condition.
Intermediate Level
Q3: When should you use a queue vs a dynamic array in a verification class? Use a dynamic array when: (a) the size needs to be randomized via a constraint, (b) you need random access by a computed index as the primary operation, or (c) you're passing data to or receiving data from another dynamic array context. Use a queue when: (a) you primarily add to one end and remove from the other (FIFO/LIFO), (b) you need to collect items incrementally without knowing the final count upfront, (c) you need the sort()/rsort() methods. Queues have O(1) push/pop at either end, which is more efficient than growing a dynamic array one element at a time. Q4: What happens if you call pop_front() on an empty queue? Fatal simulation error — the simulator terminates immediately with an out-of-bounds error. Unlike static arrays which silently return X on out-of-bounds access, queues (like dynamic arrays) enforce strict bounds checking at runtime. Always guard with if (q.size() > 0) before any pop operation in code where the queue could be empty.
Experienced Engineer Level
Q5: An in-order scoreboard uses two queues: one for expected transactions, one for received. At end-of-test, expected.size()=3 and received.size()=0. What does this tell you, and what should you look for in the waveform? The DUT sent the driver's transactions but never produced 3 responses. Possible causes: (1) DUT has a latency bug — responses are in flight but the test ended before they arrived (check the end-of-test drain time), (2) DUT dropped the transactions internally — check the DUT's internal FIFO flags and handshake signals for backpressure, (3) the monitor missed the responses due to wrong sampling edge, polarity, or interface signal — check monitor handshaking logic, (4) there is a deadlock — DUT is waiting for a signal that was never driven. In the waveform: verify the output valid signal ever asserted, check whether the DUT's internal pipeline shows the transactions progressing through to the output stage, and verify the monitor's sampling condition matches the DUT's output timing.
Best Practices & Coding Guidelines
- Guard every pop with size check — if (q.size() > 0) before every pop_front(), pop_back(), or q[$] access in code paths that may reach an empty queue. Fatal errors here crash the whole simulation.
- Drain check at end-of-test — Check both expected and received queues are empty at test completion. A non-empty queue means dropped or extra transactions — always a test failure, not informational.
- Use dynamic arrays for rand size — Queues do not work reliably with constraint solver sizing. Use rand type data [] (dynamic array) with a size constraint when the array size must be randomized.
- Use queues for FIFO, not indexed lookup — Queues shine for push/pop operations. If your primary access pattern is random indexing by a computed key, a dynamic array or associative array is a better fit.
| Array type | Best for | Avoid when |
|---|---|---|
Static type [N] | Fixed RTL/TB structures, register files, known-size buffers | Size unknown at compile time |
Dynamic type [] | Variable-size rand data, resize operations, constraint-controlled size | Frequent front/back push-pop (use queue instead) |
Associative type [key] | Sparse maps, named configs, OOO scoreboards, memory models | Sequential ordered data; dense sequential keys |
Queue type [$] | FIFOs, ordered event lists, collect-then-process patterns, sliding window | Constraint solver size; high-frequency random index access |
Summary
Queues complete the set of four array types. They occupy the specific niche of ordered, dynamically-sized collections where you primarily add to or remove from the ends. The FIFO scoreboard, the pipeline latency checker, the sliding-window monitor — all of these are natural queue use cases. The bounded form [$:N] is the right tool for modeling hardware FIFOs where overflow is an assertion condition rather than silent data loss.
[$]in declaration = queue type.q[$]in expression = last element. Same syntax, different context.- Pop on empty = fatal error. Always guard with
size() > 0. - Queues support all array operations — indexed access, foreach, sort, slice, whole-queue copy/compare — plus the push/pop methods that dynamic arrays don't have.
- Use dynamic arrays in rand classes, not queues. The constraint solver allocates dynamic arrays; it does not reliably size queues.
- End-of-test drain check is mandatory. Non-empty expected queue = dropped transactions = failing test.