Last Updated on July 20, 2022 by Ria Pathak
Queue:
A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.
Basic Operations of Queue:
-
Enqueue: This function is used to add an element to the rear end of the queue. If the queue is completely filled, then it will be in an overflow condition. The time complexity of the enqueue is O(1).
-
Dequeue: This function is used to remove an element from the front end of the queue. If the queue is empty, then it will be in an underflow condition. The time complexity of the dequeue is O(1).
-
Front: This function returns the front element of the queue. The time complexity of this function is O(1).
-
Rear: This function returns the last element of the queue. The time complexity of this function is O(1).
-
Peek(): This operation is used to get the value of the element from the front of the queue.
Types of queues:
-
Simple Queue: In Simple queue, insertion of the element takes place at the rear end i.e. ENQUEUE and removal of the element takes place at the front end i.e. DEQUEUE. Simple queue is also called a linear queue.
-
Circular Queue: In a circular queue, the elements act like a circular ring. The working of a circular queue is similar to a simple queue but in a circular queue the element in the last position is connected to the element in the first position. The main advantage of a circular queue is that the memory will be utilized in a better way.
-
Priority Queue: In a priority queue, the elements are stored according to their priority, Based on the priority of elements we’ll set our queue accordingly i.e. in ascending order or in descending order.
-
Dequeue: Dequeue is known as double ended queue. In dequeue, the elements can be inserted or removed from both of the ends.
Due to this property, dequeue may not follow the first in first out property.
Queue implementation using Array:
For the implementation of queue, we need to initialize two pointers i.e. front and rear, we insert an element from the rear and remove the element from the front, and if we increment the rear and front pointer we may occur error,
Due to which the front pointer may reach the end.
The solution of the above problem is to increase the front and rear pointer in a circular manner.
Enqueue Operation / Insertion:
- First check if the queue is full or not.
- For the first element, set the FRONT pointer to 0.
- Increment the REAR index by 1.
- Add the new element in the position which was pointed by REAR.
Dequeue Operation / Remove:
- First check if the queue is empty or not.
- Return the value which was pointed by FRONT.
- Increment the FRONT index by 1.
- For the last element, reset the values of FRONT and REAR to -1.
#include#include #include struct Queue { int front, rear, size; unsigned capacity; int* array; }; struct Queue* createQueue(unsigned capacity) { struct Queue* queue = (struct Queue*)malloc( sizeof(struct Queue)); queue->capacity = capacity; queue->front = queue->size = 0; queue->rear = capacity - 1; queue->array = (int*)malloc( queue->capacity * sizeof(int)); return queue; } int isFull(struct Queue* queue) { return (queue->size == queue->capacity); } int isEmpty(struct Queue* queue) { return (queue->size == 0); } void enqueue(struct Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->array[queue->rear] = item; queue->size = queue->size + 1; printf("%d enqueued to queue\n", item); } int dequeue(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; int item = queue->array[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } int front(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->front]; } int rear(struct Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->rear]; } int main() { struct Queue* queue = createQueue(1000); enqueue(queue, 1); enqueue(queue, 2); enqueue(queue, 3); enqueue(queue, 4); printf("%d dequeued from queue\n\n", dequeue(queue)); printf("Front item is %d\n", front(queue)); printf("Rear item is %d\n", rear(queue)); return 0; }
#includeusing namespace std; class Queue { public: int front, rear, size; unsigned capacity; int* array; }; Queue* createQueue(unsigned capacity) { Queue* queue = new Queue(); queue->capacity = capacity; queue->front = queue->size = 0; queue->rear = capacity - 1; queue->array = new int[queue->capacity]; return queue; } int isFull(Queue* queue) { return (queue->size == queue->capacity); } int isEmpty(Queue* queue) { return (queue->size == 0); } void enqueue(Queue* queue, int item) { if (isFull(queue)) return; queue->rear = (queue->rear + 1) % queue->capacity; queue->array[queue->rear] = item; queue->size = queue->size + 1; cout << item << " enqueued to queue\n"; } int dequeue(Queue* queue) { if (isEmpty(queue)) return INT_MIN; int item = queue->array[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } int front(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->front]; } int rear(Queue* queue) { if (isEmpty(queue)) return INT_MIN; return queue->array[queue->rear]; } int main() { Queue* queue = createQueue(1000); enqueue(queue, 1); enqueue(queue, 2); enqueue(queue, 3); enqueue(queue, 4); cout << dequeue(queue) << " dequeued from queue\n"; cout << "Front item is " << front(queue) << endl; cout << "Rear item is " << rear(queue) << endl; return 0; }
class Queue {
int front, rear, size;
int capacity;
int array[];
public Queue(int capacity)
{
this.capacity = capacity;
front = this.size = 0;
rear = capacity - 1;
array = new int[this.capacity];
}
boolean isFull(Queue queue)
{
return (queue.size == queue.capacity);
}
boolean isEmpty(Queue queue)
{
return (queue.size == 0);
}
void enqueue(int item)
{
if (isFull(this))
return;
this.rear = (this.rear + 1)
% this.capacity;
this.array[this.rear] = item;
this.size = this.size + 1;
System.out.println(item
+ " enqueued to queue");
}
int dequeue()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
int item = this.array[this.front];
this.front = (this.front + 1)
% this.capacity;
this.size = this.size - 1;
return item;
}
int front()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.front];
}
int rear()
{
if (isEmpty(this))
return Integer.MIN_VALUE;
return this.array[this.rear];
}
}
class Test {
public static void main(String[] args)
{
Queue queue = new Queue(1000);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
System.out.println(queue.dequeue()
+ " dequeued from queue\n");
System.out.println("Front item is "
+ queue.front());
System.out.println("Rear item is "
+ queue.rear());
}
}
class Queue:
# __init__ function
def __init__(self, capacity):
self.front = self.size = 0
self.rear = capacity -1
self.Q = [None]*capacity
self.capacity = capacity
def isFull(self):
return self.size == self.capacity
def isEmpty(self):
return self.size == 0
def EnQueue(self, item):
if self.isFull():
print("Full")
return
self.rear = (self.rear + 1) % (self.capacity)
self.Q[self.rear] = item
self.size = self.size + 1
print("% s enqueued to queue" % str(item))
def DeQueue(self):
if self.isEmpty():
print("Empty")
return
print("% s dequeued from queue" % str(self.Q[self.front]))
self.front = (self.front + 1) % (self.capacity)
self.size = self.size -1
def que_front(self):
if self.isEmpty():
print("Queue is empty")
print("Front item is", self.Q[self.front])
def que_rear(self):
if self.isEmpty():
print("Queue is empty")
print("Rear item is", self.Q[self.rear])
if __name__ == '__main__':
queue = Queue(30)
queue.EnQueue(1)
queue.EnQueue(2)
queue.EnQueue(3)
queue.EnQueue(4)
queue.DeQueue()
queue.que_front()
queue.que_rear()
Complexity:
Time Complexity :
Enqueue: O(1)
Dequeue: O(1)
Front: O(1)
Rear: O(1)
Space complexity:
O(N) where N is the size of the array.
Applications of queue:
- Queue is used in CPU Scheduling.
- Queue is used in Asynchronous processes.
This article tried to discuss Queue Data Structure. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming.