SystemVerilog Queue

Queue is a variable size, ordered collection of homogeneous elements which can grow and shrink. The size of a queue is variable similar to a dynamic array, but a queue may be empty with no element and it is still a valid data structure. Queues can be used as LIFO (Last In First Out) Buffer or FIFO (First In First Out) type of buffers.

Syntax:
A queue is declared simply by putting a $ as the size of an array.

integer my_q[$];

You can initialize a queue at the place of its variable declaration:

integer my_q[$] = {1, 3, 5};

You can also set up an upper limit of index for a queue (a bounded queue):

integer my_q[$:127];

Since index of an array can only be non-negative, the maximum number of elements for the queue in the above case is 128 (i.e., 0 through 127).

Each element in the queue is identified by an ordinal number that represents its position within the queue, with 0 representing the first element and $ represents the last element.

Bounded Queues
Size of a queue can be limited by giving the last index (i.e. upper bound) as follows

int queueA[$:99]; // A queue whose maximum size is 100 integers 

These are called bounded queues.It will not have an element whose index is higher than the queue’s declared upper bound. Operators on bounded queue can be applied exactly the same way as unbounded queues, except that, result should fall in the upper bound limit.

The size of the queue is variable similar to dynamic array but queue may be empty with zero element and still its a valid data structure.

Queues and dynamic arrays have the same assignment and argument passing semantics. Also, queues support the same operations that can be performed on unpacked arrays and use the same operators and rules except as defined below:

// SystemVerilog Queue Operations
int q[$] = { 2, 4, 8 }; 
int p[$]; 
int e, pos; 
e = q[0]; // read the first (leftmost) item 
e = q[$]; // read the last (rightmost) 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 (leftmost) item 
q = q[0:$-1]; // delete the last (rightmost) 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 

Queue Methods:

Queues also provides several built-in methods to access/modify queue. Below we have list down all such methods.

• The size() method returns the number of items in the queue. If the queue is empty, it returns 0. 
• The insert() method inserts the given item at the specified index position. 
• The delete() method deletes the item at the specified index. 
• The pop_front() method removes and returns the first element of the queue. 
• The pop_back() method removes and returns the last element of the queue. 
• The push_front() method inserts the given element at the front of the queue. 
• The push_back() method inserts the given element at the end of the queue. 

// SystemVerilog Queue Methods
module queue_methods();

// Queue is declated with $ in array size
  integer queue[$] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
integer i;

initial begin
  $display ("Initial elements in the queue");
  print_queue;
  // Insert new element at begin of queue
  queue = {11, queue};
  $display ("new element added using concatenation");
  print_queue;
  // Insert using method at beginning
  queue.push_front(12);
  $display ("new element added using push_front");
  print_queue;
  // Insert using method at end
  queue.push_back(12);
  $display ("new element added using push_back");
  print_queue;
  // Using insert to insert, here 6 is index
  // and 13 is value
  queue.insert(6,13);
  $display ("new element added using insert(index,value)");
  print_queue;
  // get first queue element method at begining
  i = queue.pop_front();
  $display ("element poped using pop_front");
  print_queue;
  // get last queue element method at end
  i = queue.pop_back();
  $display ("element poped using pop_end");
  print_queue;
  // Use delete method to delete element at index 4 in queue
  queue.delete(10);
  $display ("deleted element at index 10");
  print_queue;
  #1 $finish;
end

  // Method to print queue
task print_queue;
  integer i;
  $write("Queue contains ");
  for (i = 0; i < queue.size(); i ++) begin
    $write (" %g", queue[i]);
  end
  $write("\n");
endtask

endmodule

Results:
Initial elements in the queue
Queue contains  0 1 2 3 4 5 6 7 8 9 10
new element added using concatenation
Queue contains  11 0 1 2 3 4 5 6 7 8 9 10
new element added using push_front
Queue contains  12 11 0 1 2 3 4 5 6 7 8 9 10
new element added using push_back
Queue contains  12 11 0 1 2 3 4 5 6 7 8 9 10 12
new element added using insert(index,value)
Queue contains  12 11 0 1 2 3 13 4 5 6 7 8 9 10 12
element poped using pop_front
Queue contains  11 0 1 2 3 13 4 5 6 7 8 9 10 12
element poped using pop_end
Queue contains  11 0 1 2 3 13 4 5 6 7 8 9 10
deleted element at index 10
Queue contains  11 0 1 2 3 13 4 5 6 7 9 10

Try simulation yourself here

Hope you get the idea how to declare and use the SystemVerilog Queues. Next we will learn about Linked lists, array methods and we will compare the array types in SystemVerilog.

Previous : SystemVerilog Associative Arrays
Next : SystemVerilog Linked Lists