Page 141 - DCAP407_DATA_STRUCTURE

Data Structure

Cars moving in line at a gas station or machine parts on the assembly line are the real-
life examples where queues are prevalent.

Thereby, queues in data structures are the same as queues that you would see in any shop while
waiting to pay at the checkout counter. In each of the cases, the object or customer at the front of the line
was the first to enter and the one at the end of the line is the last to have entered. Each time a customer
makes payment for their goods (or the machine part is removed from the line) the customer leaves the
queue. This represents the “dequeue” function of the queue. Each time another customer or object
enters the line to wait, they join the end of the line. This represents the “enqueue” function of the queue.
The “size” function of the queue returns the length of the line and “empty” function returns true only if
the line is empty. Figure 8.3 depicts how a queue is represented.

Figure 8.3: Representation of a Queue

Queue can be implemented using arrays and linked list too. The main benefit in linked
lists is that the size of the queue is not much of a concern. In linked lists, we can add as
many nodes as possible and the queue will never have a full condition. The queue that
uses linked list would be similar to that of a linked list. The only difference between the
two of them is that, in queues, the leftmost node and the rightmost node is called as
front and rear node respectively. Also, we cannot remove any of the arbitrary nodes
from the queue. Always the front node needs to be removed.

134 LOVELY PROFESSIONAL UNIVERSITY