Queue Reviewer -Data Structure and Algorithm

Queue

This is an abstract data structure, somewhat similar to stacks. Unlike stacks, a _____ is open at both its ends.

enqueue()

add (store) an item to the queue

dequeue()

remove (access) an item from the queue.

peek()

Gets the element at the front of the queue without removing it.

isfull()

checks if the queue is full

isemtpy()

checks if the queue is empty

Implementation of peek() function in C programing language

int peek () {

return queue [front];

}

Implementation of isfull() function in C programing language

bool isfull () {

if (rear = MAXSIZE - 1)

return true;

else return false;

}

isempty()

bool isempty() {

in (front < 0 || front > rear)

else

return false;

}

Enqueue Operation

• Step 1 − Check if the queue is full.

• Step 2 − If the queue is full, produce overflow error and exit.

• Step 3 − If the queue is not full, increment rear pointer to point the next empty space.

• Step 4 − Add data element to the queue location, where the rear is pointing.

• Step 5 − Return success.

Implementation of enqueue() in C programming language

int enqueue ( int data)

if (is full())

return 0;

rear = rear + 1;

queue [rear] = data;

return 1;

Dequeue Operation

• Step 1 − Check if the queue is empty.

• Step 2 − If the queue is empty, produce underflow error and exit.

• Step 3 − If the queue is not empty, access the data where front is pointing.

• Step 4 − Increment front pointer to point to the next available data element.

• Step 5 − Return success.

Implementation of dequeue() in C programming language

int dequeue() {

if (isempty())

return 0;

int data = queue[front];

front = front + 1;

return data;

}

• Simple Queue,

• Double-Ended Queue (Dequeue)

• Circular Queue

• Priority Queue

Different type of queues

Simple Queue

Simply follows FIFO Structure. We can only insert the element at the back and remove the element from the front of the queue.

Double-Ended Queue (Dequeue)

In a double-ended queue the insertion and deletion operations, both can be performed from both ends.

Input Restricted Queue

This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends

Output Restricted Queue

This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.

• Task Scheduling in operating systems

• Data Transfer in Network Communication

• Simulation of real-world system (e.g., waiting lines)

• Priority queues for event processing queues for event processing.

Applications of Queue

• A large amount of data can be managed efficiently with ease.

• Operations such as insertion and deletion can be performed with ease as it follows the first in first out rule.

• Queues are useful when a particular service is used by multiple consumers.

• Queues are fast in speed for data inter-process communication.

• Queues can be used in the implementation of other data structures.

Advantages of queue data structure

• The operations such as insertion and deletion of elements from the middle are time consuming.

• Maximum size of a queue must be defined prior in case of array implementation

Disadvantages of Queue Data Structure