Friday, March 29, 2024 14:22

Table of contents >> Data Structures > Queue

Queue

Queue is a linear data structure in which there are two operations defined: adding an element to the tail (enqueue) and extract the front-positioned element from the head (dequeue). These two operations take a constant time to execute, because the queue is usually implemented with a linked list. I remind you that the linked list can quickly add and remove elements from its
both ends. The queue’s behavior is FIFO (first in, first out). The operations searching and accessing through index are not supported. Queue can naturally model a list of waiting people, tasks or other objects, which have to be processed in the same order as they were added (enqueued).

As an example of using a queue, I can point out the implementation of the BFS (breadth-first search) algorithm, in which we start from an initial element and all its neighbors are added to a queue. After that they are processed in the order they were added and their neighbors are added to the queue too. This operation is repeated until we reach the element we are looking for or we process all elements.

The call to add elements for a queue (or the Push version) is Enqueue():

The reverse operation of removing items is accomplished using the Dequeue() method:

Similarly, the Peek() call allows you to view the top value without removing it. This specific data structure is very often used in conjuncture with stack data structures.

Keep in mind the queue data structure can be defined as a general Queue and as a type-specific Queue<T>.

The most important methods of the Queue data structure are:

Copy(), CopyTo() – Allows us to copy Queue elements. We might have a Queue collection but need to loop over the elements in the reverse order. We call CopyTo(), and then loop over the array in reverse. We use CopyTo() with an int array. We allocate the number of elements to the int[] with the same integer as the Queue’s Count property.

The output looks like this:

Clear() – Use this method to remove all elements from the Queue. This can be used instead of assigning the reference to a new Queue.
Contains() – You can use Contains() to search through the Queue for a matching element. This method does a linear search.
Dequeue() – Removes the object at the beginning of your Queue. It doesn’t loop over elements.
Peek() – Returns the object at the beginning of the Queue(T) without removing it. This means you only look at the object.
ToArray() – Converts your Queue(T) to an array. This is similar to CopyTo(), but it provides the new array reference.

The most important property of the queue is:

Count – Returns the number of elements. It requires constant time and doesn’t enumerate the elements.

Tags: ,

Leave a Reply



Follow the white rabbit