Last Updated : 25 May, 2023
Improve
Similar to Stack, Queueis a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Recommended PracticeImplement Queue using arrayTry It!
Queue Data structure
Basic Operations on Queue:
- enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
- dequeue(): This operation removes and returns an element that is at the front end of the queue.
- front(): This operation returns the element at the front end without removing it.
- rear(): This operation returns the element at the rear end without removing it.
- isEmpty(): This operation indicates whether the queue is empty or not.
- isFull(): This operation indicates whether the queue is full or not.
- size(): This operation returns the size of the queue i.e. the total number of elements it contains.
Types of Queues:
- Simple Queue: Simple queue also known as a linear queue is the most basic version of a queue. Here, insertion of an element i.e. the Enqueue operation takes place at the rear end and removal of an element i.e. the Dequeue operation takes place at the front end. Here problem is that if we pop some item from front and then rear reach to the capacity of the queue and although there are empty spaces before front means the queue is not full but as per condition in isFull() function, it will show that the queue is full then. To solve this problem we use circular queue.
- Circular Queue: In a circular queue, the element of the queue act as a circular ring. The working of a circular queue is similar to the linear queue except for the fact that the last element is connected to the first element. Its advantage is that the memory is utilized in a better way. This is because if there is an empty space i.e. if no element is present at a certain position in the queue, then an element can be easily added at that position using modulo capacity(%n).
- Priority Queue: This queue is a special type of queue. Its specialty is that it arranges the elements in a queue based on some priority. The priority can be something where the element with the highest value has the priority so it creates a queue with decreasing order of values. The priority can also be such that the element with the lowest value gets the highest priority so in turn it creates a queue with increasing order of values. In pre-define priority queue, C++ gives priority to highest value whereas Java gives priority to lowest value.
- Dequeue: Dequeue is also known as Double Ended Queue. As the name suggests double ended, it means that an element can be inserted or removed from both ends of the queue, unlike the other queues in which it can be done only from one end. Because of this property, it may not obey the First In First Out property.
Applications of Queue:
Queue is used when things don’t have to be processed immediately, but have to be processed inFirstIn FirstOut order likeBreadth First Search. This property of Queue makes it also useful in following kind of scenarios.
- When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
- When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
- Queue can be used as an essential component in various other data structures.
Array implementation Of Queue:
For implementing queue, we need to keep track of two indices, front and rear. We enqueue an item at the rear and dequeue an item from the front. If we simply increment front and rear indices, then there may be problems, the front may reach the end of the array. The solution to this problem is to increase front and rear in circular manner.
Steps for enqueue:
- Check the queue is full or not
- If full, print overflow and exit
- If queue is not full, increment tail and add the element
Steps for dequeue:
- Check queue is empty or not
- if empty, print underflow and exit
- if not empty, print element at the head and increment head
Below is a program to implement above operation on queue
C++
// CPP program for array
// implementation of queue
#include <bits/stdc++.h>
using
namespace
std;
// A structure to represent a queue
class
Queue {
public
:
int
front, rear, size;
unsigned capacity;
int
* array;
};
// function to create a queue
// of given capacity.
// It initializes size of queue as 0
Queue* createQueue(unsigned capacity)
{
Queue* queue =
new
Queue();
queue->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array =
new
int
[queue->capacity];
return
queue;
}
// Queue is full when size
// becomes equal to the capacity
int
isFull(Queue* queue)
{
return
(queue->size == queue->capacity);
}
// Queue is empty when size is 0
int
isEmpty(Queue* queue)
{
return
(queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
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"
;
}
// Function to remove an item from queue.
// It changes front and size
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;
}
// Function to get front of queue
int
front(Queue* queue)
{
if
(isEmpty(queue))
return
INT_MIN;
return
queue->array[queue->front];
}
// Function to get rear of queue
int
rear(Queue* queue)
{
if
(isEmpty(queue))
return
INT_MIN;
return
queue->array[queue->rear];
}
// Driver code
int
main()
{
Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
cout << dequeue(queue)
<<
" dequeued from queue\n"
;
cout <<
"Front item is "
<< front(queue) << endl;
cout <<
"Rear item is "
<< rear(queue) << endl;
return
0;
}
// This code is contributed by rathbhupendra
C
// C program for array implementation of queue
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// A structure to represent a queue
struct
Queue {
int
front, rear, size;
unsigned capacity;
int
* array;
};
// function to create a queue
// of given capacity.
// It initializes size of queue as 0
struct
Queue* createQueue(unsigned capacity)
{
struct
Queue* queue = (
struct
Queue*)
malloc
(
sizeof
(
struct
Queue));
queue->capacity = capacity;
queue->front = queue->size = 0;
// This is important, see the enqueue
queue->rear = capacity - 1;
queue->array = (
int
*)
malloc
(
queue->capacity *
sizeof
(
int
));
return
queue;
}
// Queue is full when size becomes
// equal to the capacity
int
isFull(
struct
Queue* queue)
{
return
(queue->size == queue->capacity);
}
// Queue is empty when size is 0
int
isEmpty(
struct
Queue* queue)
{
return
(queue->size == 0);
}
// Function to add an item to the queue.
// It changes rear and size
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);
}
// Function to remove an item from queue.
// It changes front and size
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;
}
// Function to get front of queue
int
front(
struct
Queue* queue)
{
if
(isEmpty(queue))
return
INT_MIN;
return
queue->array[queue->front];
}
// Function to get rear of queue
int
rear(
struct
Queue* queue)
{
if
(isEmpty(queue))
return
INT_MIN;
return
queue->array[queue->rear];
}
// Driver program to test above functions./
int
main()
{
struct
Queue* queue = createQueue(1000);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
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;
}
Java
// Java program for array
// implementation of queue
// A class to represent a queue
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];
}
// Queue is full when size becomes
// equal to the capacity
boolean
isFull(Queue queue)
{
return
(queue.size == queue.capacity);
}
// Queue is empty when size is 0
boolean
isEmpty(Queue queue)
{
return
(queue.size ==
0
);
}
// Method to add an item to the queue.
// It changes rear and size
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"
);
}
// Method to remove an item from queue.
// It changes front and size
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;
}
// Method to get front of queue
int
front()
{
if
(isEmpty(
this
))
return
Integer.MIN_VALUE;
return
this
.array[
this
.front];
}
// Method to get rear of queue
int
rear()
{
if
(isEmpty(
this
))
return
Integer.MIN_VALUE;
return
this
.array[
this
.rear];
}
}
// Driver class
public
class
Test {
public
static
void
main(String[] args)
{
Queue queue =
new
Queue(
1000
);
queue.enqueue(
10
);
queue.enqueue(
20
);
queue.enqueue(
30
);
queue.enqueue(
40
);
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());
}
}
// This code is contributed by Gaurav Miglani
Python3
# Python3 program for array implementation of queue
# Class Queue to represent a queue
class
Queue:
# __init__ function
def
__init__(
self
, capacity):
self
.front
=
self
.size
=
0
self
.rear
=
capacity
-
1
self
.Q
=
[
None
]
*
capacity
self
.capacity
=
capacity
# Queue is full when size becomes
# equal to the capacity
def
isFull(
self
):
return
self
.size
=
=
self
.capacity
# Queue is empty when size is 0
def
isEmpty(
self
):
return
self
.size
=
=
0
# Function to add an item to the queue.
# It changes rear and size
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))
# Function to remove an item from queue.
# It changes front and size
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
# Function to get front of queue
def
que_front(
self
):
if
self
.isEmpty():
print
(
"Queue is empty"
)
print
(
"Front item is"
,
self
.Q[
self
.front])
# Function to get rear of queue
def
que_rear(
self
):
if
self
.isEmpty():
print
(
"Queue is empty"
)
print
(
"Rear item is"
,
self
.Q[
self
.rear])
# Driver Code
if
__name__
=
=
'__main__'
:
queue
=
Queue(
30
)
queue.EnQueue(
10
)
queue.EnQueue(
20
)
queue.EnQueue(
30
)
queue.EnQueue(
40
)
queue.DeQueue()
queue.que_front()
queue.que_rear()
C#
// C# program for array implementation of queue
using
System;
namespace
GeeksForGeeks {
// A class to represent a linearqueue
class
Queue {
private
int
[] ele;
private
int
front;
private
int
rear;
private
int
max;
public
Queue(
int
size)
{
ele =
new
int
[size];
front = 0;
rear = -1;
max = size;
}
// Function to add an item to the queue.
// It changes rear and size
public
void
enqueue(
int
item)
{
if
(rear == max - 1) {
Console.WriteLine(
"Queue Overflow"
);
return
;
}
else
{
ele[++rear] = item;
}
}
// Function to remove an item from queue.
// It changes front and size
public
int
dequeue()
{
if
(front == rear + 1) {
Console.WriteLine(
"Queue is Empty"
);
return
-1;
}
else
{
Console.WriteLine(ele[front] +
" dequeued from queue"
);
int
p = ele[front++];
Console.WriteLine();
Console.WriteLine(
"Front item is {0}"
, ele[front]);
Console.WriteLine(
"Rear item is {0} "
, ele[rear]);
return
p;
}
}
// Function to print queue.
public
void
printQueue()
{
if
(front == rear + 1) {
Console.WriteLine(
"Queue is Empty"
);
return
;
}
else
{
for
(
int
i = front; i <= rear; i++) {
Console.WriteLine(ele[i] +
" enqueued to queue"
);
}
}
}
}
// Driver code
class
Program {
static
void
Main()
{
Queue Q =
new
Queue(5);
Q.enqueue(10);
Q.enqueue(20);
Q.enqueue(30);
Q.enqueue(40);
Q.printQueue();
Q.dequeue();
}
}
}
Javascript
<script>
// Queue class
class Queue
{
// Array is used to implement a Queue
constructor()
{
this
.items = [];
}
isEmpty()
{
// return true if the queue is empty.
return
this
.items.length == 0;
}
enqueue(element)
{
// adding element to the queue
this
.items.push(element);
document.write(element +
" enqueued to queue<br>"
);
}
dequeue()
{
// removing element from the queue
// returns underflow when called
// on empty queue
if
(
this
.isEmpty())
return
"Underflow<br>"
;
return
this
.items.shift();
}
front()
{
// returns the Front element of
// the queue without removing it.
if
(
this
.isEmpty())
return
"No elements in Queue<br>"
;
return
this
.items[0];
}
rear()
{
// returns the Rear element of
// the queue without removing it.
if
(
this
.isEmpty())
return
"No elements in Queue<br>"
;
return
this
.items[
this
.items.length-1];
}
}
// creating object for queue class
var
queue =
new
Queue();
// Adding elements to the queue
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
// queue contains [10, 20, 30, 40]
// removes 10
document.write(queue.dequeue() +
" dequeued from queue<br>"
);
// queue contains [20, 30, 40]
// Front is now 20
document.write(
"Front item is "
+ queue.front() +
"<br>"
);
// printing the rear element
// Rear is 40
document.write(
"Rear item is "
+ queue.rear() +
"<br>"
);
// This code is contributed by Susobhan Akhuli
</script>
Output
10 enqueued to queue20 enqueued to queue30 enqueued to queue40 enqueued to queue10 dequeued from queueFront item is 20Rear item is 40
Complexity Analysis:
- Time Complexity
Operations | Complexity |
---|---|
Enqueue(insertion) | O(1) |
Deque(deletion) | O(1) |
Front(Get front) | O(1) |
Rear(Get Rear) | O(1) |
IsFull(Check queue is full or not) | O(1) |
IsEmpty(Check queue is empty or not) | O(1) |
- Auxiliary Space:
O(N) where N is the size of the array for storing elements.
Advantages of Array Implementation:
- Easy to implement.
- 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.
Disadvantages of Array Implementation:
- Static Data Structure, fixed size.
- If the queue has a large number of enqueue and dequeue operations, at some point (in case of linear increment of front and rear indexes) we may not be able to insert elements in the queue even if the queue is empty (this problem is avoided by using circular queue).
- Maximum size of a queue must be defined prior.