Hi,
in Dave’s answers in the following link, He stated that a queue in sv is implemented as a linked list. hence, he said: “and requires a traversal of elements to get to element in between the head an tail.”
in the SV LRM section 7.10 I found this sentence: “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” which tells that a queue is more like an array, not a linked list because accessing any element in the queue consumes the same amount of time.
I got really confused now :(. can anyone explain?
In reply to ahennawy:
The LRM does not prescribe the memory layout of any data type. I think the purpose of that section is just describing the functionality that gives you easy access to the head and tail of the queue as well as any selected index.
In reply to dave_59:
So Dave, I got that the LRM standardizes the needed behavior of each data type but how this is achieved is left to each simulator implementation.
But we are agreed that if the queue is implemented as a linked list, accessing head and tail takes the same time and is faster than accessing any index in between.
Please confirm my understanding.
Thanks in advance.
In reply to ahennawy:
That is true for a simple linked list. But if you implement a queue as a contiguous array of elements, then you run into the problem that reallocating the array when enqueuing another element takes longer as the queue grows in size.
The reality may be that queues get implemented using a combination fixed sized arrays subblocks and lists to balance the performance of different types of access.
Thanks a lot Dave for the explanation.
It was really helpful.