Queues in Data Structure

A queue, like a stack, is a linear structure in which actions are conducted in a certain order. First in, first out (FIFO) is the order. Any line of consumers for a resource in which the consumer who arrived first gets serviced first is an example of a queue. In programming, a queue is an important data structure.

The distinction between stacks and queues is in the removal process. In a stack, we delete the most recently added item; in a queue, we remove the least recently added item. This article will discuss what a queue is in a data structure, operations of queue, applications, and implementation of queue array.

Queue

Queues are abstract data structures that are comparable to stacks. A queue, unlike a stack, is open on both ends. One end is always used to input data (enqueue), whereas the other end is always used to delete data (dequeue). The queue employs the First-In-First-Out (FIFO) mechanism, which means that the data item placed first will be accessed first.

A single-lane one-way road, where the vehicle enters first and departs first, is a real-world example of a queue. Queues at ticket booths and bus stations are two more real-world examples.

Representation of a Queue

As we now understand, we access both ends of the queue for distinct purposes. 

A queue, like a stack, may be implemented using arrays, linked-lists, pointers, and structures. To keep things simple, we’ll use a one-dimensional array to implement queues.

Operations of a Queue

The following are some of the operations that may be performed on a queue:

• Insert
• Delete

Insert: It refers to the adding of a queue item. Assume you wish to add item F to the queue below. Because the elements are inserted at the back end, F comes after D. F is now the tail end.

Delete: It refers to removing an item from the queue. Because the items are withdrawn from the front end, item B is removed from the queue. A is now at the front of the queue.

Queue types in Data Structure

In data structures, there are four types of queues:

• A basic or simple queue

It is the simplest basic queue in which an item is inserted at the head of the queue and deleted at the back.

• Queue in a circle

The last node of a circular node is connected to the initial node. Because all ends are linked to one another, it is also known as a ring buffer. Insertion occurs at the head of the queue, while deletion occurs at the back.

• Priority queue

The nodes in a priority queue will have a predetermined priority in the priority queue. The node with the lowest priority will be removed from the queue first. Insertion occurs in the sequence in which the nodes arrive. Priority queue applications include Dijkstra’s quickest route method, Prim’s algorithm, and data compression techniques such as Huffman coding.

• Dequeue (Double-ended queue)

Insertion and deletion can occur at both the front and back ends of a double-ended queue.

Applications of Queues

Queues have a wide range of practical uses, including:

• Printer Spooling
• CPU Scheduling
• Mail Service
• Keyboard Buffering
• Elevator
• Printer Spooling

1. A printer may receive multiple print requests in a short period of time. 
2. The rate at which these requests are received is much faster than the rate they are processed at. 
3. As a result, a temporary storage mechanism is required to store these requests in the order of their arrival. 
4. A queue is the best choice in this case, storing the print requests so that they are processed on a first-come-first-served basis.

• CPU Scheduling

1. A CPU can only handle one request at a time.
2. The pace at which the CPU receives requests is typically substantially faster than the rate at which the CPU processes requests.
3. As a result, the requests are temporarily held in a queue in the order in which they arrive.
4. When the CPU becomes available, it retrieves the requests from the queue.
5. When a request is completed, its reference is removed from the queue.
6. The CPU then receives the next request in the sequence, and the process is repeated.
7. In a time-sharing system, the CPU is assigned to each request for a certain time.
8. All of these requests are temporarily queued.
9. For a set amount of time, the CPU executes each request one at a time.
10. If the request is completed within that time frame, the reference to it is removed from the queue.
11. If the request is not handled within the stated time frame, it is moved to the bottom of the queue.
12. The CPU subsequently processes the next request in the queue, repeating the cycle.

• Mail service

1. Many transactions in many organisations are carried out by mail.
2. If the mail server fails and someone sends you an email, the email is returned to the sender.
3. Many businesses use a mail backup service to avoid this type of catastrophe.
4. When there is a problem with the mail server that prevents messages from being sent, the mail is routed to the backup server.
5. The backup server briefly saves the emails in a queue.
6. When the mail server is operational, all messages are delivered to the recipient in the order in which they came.

• Keyboard buffering

1. Queues are used to save keystrokes while you write on the keyboard.
2. When you input data into the keyboard, it is not always instantly shown on the screen.
3. This is because, during that time, the processor might be busy doing some other task.
4. In this case, the data is temporarily kept in a queue until it is read by the processor.
5. When the CPU is free, all keystrokes are read in the order received and shown on the screen.

• Elevator

1. A queue is used by an elevator to hold the requests made by users.
2. Assume the elevator is currently located on the first floor. To request an elevator, a user on the lowest floor hits the elevator button. A user on the second level hits the elevator button almost simultaneously.
3. In that case, the elevator would go to the floor where the button was pressed earlier, implying that the requests would be handled on an FCFS basis.
4. However, if one of the users was on the first floor and the other was on the ninth floor, the elevator would go to the ground floor first, regardless of who pressed the button first, because the distance to the ground floor is much less than the distance to the ninth floor. In this case, some sort of queue priority would be required.

Queue Array Implementation

We must keep track of two indices, front and back, when implementing a queue. We enqueue something from the back and dequeue something from the front. If we merely increase the front and rear indices, we may have issues since the front may approach the end of the array. The answer to this problem is to raise the front and back circularly.

Enqueue procedures

• Check to see if the queue is full
• If the buffer is full, print overflow and quit
• If the queue isn’t full, add the element to the tail

Dequeue processing steps

• Check whether the queue is empty or not
• If the buffer is empty, print underflow and quit
• If the element at the head is not empty, print it and increment the head

Conclusion

The queue data structure is a form of linear data structure used to hold items. In programming, a queue is an important data structure. Elements in this data structure are stored using the FIFO approach. During the implementation of a queue data structure, an array or linked list was utilised. Insertion into the line takes place at the REAR end, while deletion from the queue takes place at the FRONT end. This data structure is used to serve many requests from a single shared resource.