Queues

Queue is a new data type introduced in SystemVerilog that combines the best of a linked list and an array.

Like a linked list, elements can be added and removed anywhere in the queue, without performance degradation when using a dynamic array that has to allocate a new array and copy the entire contents.
Like an array, any element in the queue can be directly accessed with the help of the index, without the linked list’s overhead of stepping through the preceding element.

A queue is declared with the word subscript containing a dollar sign “[$]”. The elements in the queue are numbered from 0 to $. Initializing a queue is different for arrays as the initial apostrophe is not required and the elements must be declared inside the curly brackets. SystemVerilog allocates extra space for a queue so that you don’t run out of space when filling up a queue. This way a queue can grow and shrink without any performance penalty of a dynamic array.

The queue elements are stored in a contiguous location, so it is efficient to push and pop elements from the front and back. Adding and deleting elements in the middle of a queue requires shifting the existing data to make room and time to do this grows linearly with the size of the queue.

Queue example in SystemVerilog is shown below:

module queues ();

  int q[$] = {1,2,3,4,5};
  int k;

  initial begin


    $display("------------------  Queue  ------------------");
    foreach(q[i])$display("\t q[%0d]=%0d",i, q[i]);

    k = q.pop_front();
    $display("-----------------  Pop Front -----------------");
    $display("\t k=%0d", k);

    k = q.pop_back();
    $display("-----------------  Pop Back  -----------------");
    $display("\t k=%0d", k);


    q.push_front(9);
    $display("--------------  Insert @ Front  --------------");
    foreach(q[i])$display("\t q[%0d]=%0d",i, q[i]);


    q.push_back(0);
    $display("--------------  Insert @ Back  -_-------------");
    foreach(q[i])$display("\t q[%0d]=%0d",i, q[i]);

    q.delete(1);
    $display("--------------  Delete Element  --------------");
    foreach(q[i])$display("\t q[%0d]=%0d",i, q[i]);

  end
endmodule

Execute the example in EDA Playground

Queues#

Queues