Queues

A queue is a variable-size, ordered collection of homogeneous elements. A queue supports constant time access to all its elements as well as constant time insertion and removal at the beginning or the end of the queue. Each element in a queue is identified by an ordinal number that represents its position within the queue, with 0 representing the first, and $ representing the last. A queue is analogous to a one-dimensional unpacked array that grows and shrinks automatically. Thus, like arrays, queues can be manipulated using the indexing, concatenation, slicing operator syntax, and equality operators. Queues are declared using the same syntax as unpacked arrays, but specifying $ as the array size. The maximum size of a queue can be limited by specifying its optional right bound (last index).
For example:

byte q1[$]; // A queue of bytes
string names[$] = { "Bob" }; // A queue of strings with one element
integer Q[$] = { 3, 2, 7 }; // An initialized queue of integers
bit q2[$:255]; // A queue whose maximum size is 256 bits

The empty array literal {} is used to denote an empty queue. If an initial value is not provided in the declaration, the queue variable is initialized to the empty queue.

Queue Operators

Queues support the same operations that can be performed on unpacked arrays, and using the same operators and rules except as defined below:

int q_[$] = { 2, 4, 8 };
int p_[$];
int e, pos;
e = q_[0]; // read the first (left-most) item
e = q_[$]; // read the last (right-most) item
q_[0] = e; // write the first item
p_ = q_; // read and write entire queue (copy)
q_ = { q_, 6 }; // insert ’6’ at the end (append 6)
q_ = { e, q_ }; // insert ’e’ at the beginning (prepend e)
q_ = q_[1:$]; // delete the first (left-most) item
q_ = q_[0:$-1]; // delete the last (right-most) item
q_ = q_[1:$-1]; // delete the first and last items
q_ = {}; // clear the queue (delete all items)
q_ = { q_[0:pos-1], e, q_[pos,$] }; // insert ’e’ at position pos
q_ = { q_[0:pos], e, q_[pos+1,$] }; // insert ’e’ after position pos

Unlike arrays, the empty queue, {}, is a valid queue and the result of some queue operations. The following rules govern queue operators:

  • Q[ a : b ] yields a queue with b – a + 1 elements.
  • If a > b then Q[a:b] yields the empty queue {}.
  • Q[ n : n ] yields a queue with one item, the one at position n. Thus, Q[ n : n ] === { Q[n] }.
  • If n lies outside Q’s range (n < 0 or n > $) then Q[n:n] yields the empty queue {}.
  • If either a or b are 4-state expressions containing X or Z values, it yields the empty queue {}.
  • Q[ a : b ] where a < 0 is the same as Q[ 0 : b ].
  • Q[ a : b ] where b > $ is the same as Q[ a : $ ].

Queue methods

In addition to the array operators, queues provide several built-in methods.

size()

The prototype for the size() method is:
function int size();

The size() method returns the number of items in the queue. If the queue is empty, it returns 0.

for ( int j = 0; j < q.size; j++ ) $display( q[j] );

insert()

The prototype of the insert() method is:
function void insert(int index, queue_type item);

The insert() method inserts the given item at the specified index position.

  • Q.insert(i, e) is equivalent to: Q = {Q[0:i-1], e, Q[i,$]}

delete()

The prototype of the delete() method is:
function void delete(int index);

The delete() method deletes the item at the specified index position.

  • Q.delete(i) is equivalent to: Q = {Q[0:i-1], Q[i+1,$]}

pop_front()

The prototype of the pop_front() method is:
function queue_type pop_front();

The pop_front() method removes and returns the first element of the queue.

              e = Q.pop_front() is equivalent to: e = Q[0]; Q = Q[1,$]

pop_back()

The prototype of the pop_back() method is:
function queue_type pop_back();

The pop_back() method removes and returns the last element of the queue.

e = Q.pop_back() is equivalent to: e = Q[$]; Q = Q[0,$-1]

push_front()

The prototype of the push_front() method is:
function void push_front(queue_type item);

The push_front() method inserts the given element at the front of the queue.

Q.push_front(e) is equivalent to: Q = {e, Q}

push_back()

The prototype of the push_back() method is:
function void push_back(queue_type item);

The push_back() method inserts the given element at the end of the queue.

  • Q.push_back(e) is equivalent to: Q = {Q, e}

<< Previous | Next >>