Splat | WiseTome.com

In the last post of the series, we looked at the linked list - the basic form of data structure. In this part, we will look at the specialized type of a linked list - a queue.

The queue is nothing but a linked list, and the protocols to add and remove data from the queue are specified in a certain way. These specific constraints, when applied to a linked list, gives us a queue.

The queue of the software realm acts quite similar to the queue you find in real life. It is quite similar to the queue you find at movie theaters or bank teller counters. When people need to join the queue, they do so from behind - at the end of the queue. When they need to leave the queue, it is done at the starting point of the queue. The protocol is said to be ‘first in, first out’.

As mentioned earlier, the queue data structure is nothing but a linked list. It contains nodes - much similar to a person in a queue. Two operations are allowed on the queue.

1. Add node
2. Remove node

When a node is added, it is done at the end of the last node in the list. A remove node retrieves the first node to from the list.

In terms of pseudo code or ‘plain english’, the procedures or steps to implement a queue for these operations are can be put down in the following fashion.

Add node

1. Create a new node holding the data element
2. Set its reference element to empty (or null)
3. Set the reference element of the last node of the list to the address of the newly created node

Remove node

1. Retrieve the data from the data element from the first node of the list
2. Set the reference of the list to the address of the second node
3. Destroy/remove the first node of the linked list from memory

The queues are used in software whenever something needs to be done in an asynchronous way. If there is a particular operation that takes a bit more time than the time it takes to supply input to it - a queue may be implemented before it. A theoretical example would be implementation of the queue in the outbox of a mail program - the email is sent one after another from the outbox in the order they were put into it.

In the next post of this series, we will look at Stacks.