Web
Analytics Made Easy - StatCounter

Queues and Circular Queues (With Code in C, C++, Java, and Python)

Introduction

A queue is a linear data structure where an item can be inserted from one end and can be removed from another end. We can not insert and remove items from the same end. Figure 1 shows the structure of a queue.

Fig 1: A queue

One end of the queue is called a front and the other end is called a rear. Items are inserted in the rear end and are removed from the front end. A queue is called a First In First Out data structure because the item that goes first comes out first.

A real-life example of a queue would be a queue of people in a bank. A cashier can serve only one person at a time. When a person comes while the cashier is serving another person, he/she needs to sit in the queue. If there is more than one person in the queue, the person needs to go to the rear end of the queue and wait for his/her turn.

The queue as an Abstract Data Type (ADT) has following operations.

  1. EnQueue: It is also called a Push or an Insert operation. It inserts an item at the rear end of the queue.
  2. DeQueue: It is also called a Pop or a Remove operation. It removes the item from the front end of the queue.
  3. front: It returns the item at the front of the queue.
  4. isEmpty: It checks whether the queue is empty. If the queue is empty, we cannot do front and dequeue operations.

Details of these operations are described below.

Operations on a queue

EnQueue

The enqueue operation inserts a new item at the rear end of the queue. After the enqueue operation, the value of rear is increased by 1. Figure 2 shows the enqueue operation.

Fig 2: An enqueue operation

In Figure 2, when an item i4 is inserted, the rear moves one step to the right but the front remains in the same place. The algorithm for the insertion operation using an array is given below.

if (size of queue is > N) { 
    print "Error: queue is full" 
    return 
}

rear = rear + 1
queue[rear] = item

DeQueue

The dequeue operation removes the item at the front of the queue. When we remove the item at the front, we increase the value of front. Figure 3 shows the dequeue operation.

Fig 3: A dequeue operation

In Figure 3, when the item i1 is removed from the queue, we increase move the front one step to the right whereas the rear remains in the same place. The algorithm for dequeue operation using an array is given below.

if (rear == -1 and front == -1) { 
    print "Error: queue is empty" 
    return 
}
item = queue[front]
front = front + 1
return item

front

The front operation returns the item at the front of the queue. This operation does not affect the position of both rear and front.

isEmpty

The isEmpty operation checks whether the queue is empty or note. The queue is empty when the value of both the rear and front is -1 (initially we set both front and rear to -1).

Illustration of enqueue and dequeue

Figure 4 shows the enqueue and dequeue operations and changes in the value of rear and front for some insertions and deletions.

Fig 4: Illustration of enqueue and dequeue operation

Initially, we set both rear and front to -1. When the first item is inserted we increase the value of both rear and front by 1. After that for every enqueue operation, we increase the value of rear by 1 keeping the front as it is and for every dequeue operation, we increase the value of front by 1 keeping the rear as it is.

In both enqueue and dequeue operations, we increase the value of front and rear. We never decrease the value of both of them. For a limited sized queue (i.e. array implementation) this creates a problem when the rear of the queue reaches the maximum index. Figure 5 illustrates this.

Fig 5: Limitation of a linear queue

Figure 5 shows a queue that can hold 9 items. Currently, there are only 3 items. Even though the queue can still hold 6 more items, when we try to insert a new item, it says the queue is full. This is because the rear of the queue is already in its maximum index position. This problem can be avoided using the circular array.

Circular Queue

In a linear queue, when a new item is inserted, we increase the value of a rear by 1 and insert the new item in the new position. However, in a circular queue, when a new item is inserted, we update the rear as rear = (rear + 1) % N where N is the capacity of the queue. This makes the queue circular. Let us illustrate this by an example.

Suppose we have a queue whose capacity is 7 i.e. it can hold at most 7 items. Suppose the rear of the queue is at 7th position and the front of the queue is at 3rd position which means the 1st and 2nd position are unused. Let us try to insert a new item. The new position of the rear will be (7 + 1) % 7 = 1. Since the 1st position is unused, the item is inserted there. We do the similar for the front. When an item is deleted, we update the front as front = (front + 1) % N. Figure 6 shows an example of a circular queue.

Fig 6: A circular queue

Since there is no boundary in a circular queue, how do we know when the queue is full? The queue is full when rear and front are adjacent to each other i.e. when (rear + 1) % N == front, the queue is full. The implement of a circular queue is given in the implementation section.

Complexities

All the operations of a queue take a constant time.

OperationComplexity
enqueueO(1)
dequeueO(1)
front (Peek)O(1)
isEmptyO(1)

Applications of a queue

  1. In shared resources like a printer, jobs are stored in a queue.
  2. In task CPU scheduling, tasks are stored in a queue.
  3. In many graphs algorithms like Breadth First Search, vertices stored in a queue.
  4. Interrupt handling. Interrupts are stored in a queue.
  5. Many messaging queue systems using the queue to store messages.

Implementation in C, C++, Java, and Python

Using array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Circular queue implementation in C using array

#include <stdio.h>
#define MAX_SIZE 10
int front = -1;
int rear = -1;

int queue[MAX_SIZE];

// insert an item at the rear of the queue
void enqueue(int item) {
// Check if the queue is full
if ((rear + 1) % MAX_SIZE == front) {
printf("%s\n", "ERROR: Queue is full");
return;
}

// if there are no items, make front and rear 1
// else increment the rear by 1
if (front == -1 && rear == -1) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}

// insert the time at rear
queue[rear] = item;
}

// removes the item from the front of the queue
int dequeue() {
int item;
// Check if the queue is empty
if (rear == -1 && front == -1) {
printf("%s\n", "ERROR: Queue is empty");
return -999999;
}
item = queue[front];

if (front == rear) {
front = rear = -1;
} else {
// increase the front
front = (front + 1) % MAX_SIZE;
}
return item;

}

// returns the item from the front of the queue
int getFront() {
// Check if the queue is empty
if (rear == -1 && front == -1) {
printf("%s\n", "ERROR: Queue is empty");
return -999999;
}

return queue[front];
}

int main() {
enqueue(34);
enqueue(35);
enqueue(41);
enqueue(56);
printf("%d\n", dequeue());
printf("%d\n", dequeue());
enqueue(62);
enqueue(63);
enqueue(64);
enqueue(65);
enqueue(66);
enqueue(67);
enqueue(68);
enqueue(69);
printf("%d\n", dequeue());
enqueue(70);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// C++ implementation of queue using array

#include <iostream>
using namespace std;

class QueueArray {
private:
const static int MAX_SIZE = 10;
int queue[MAX_SIZE];
int rear;
int front;
public:
QueueArray() {
rear = front = -1;
}

// insert an item at the rear of the queue
void enqueue(int item) {
// Check if the queue is full
if ((rear + 1) % MAX_SIZE == front) {
cout<<"ERROR: Queue is full"<<endl;
return;
}

// if there are no items, make front and rear 1
// else increment the rear by 1
if (front == -1 && rear == -1) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}

// insert the time at rear
queue[rear] = item;
}

// removes the item from the front of the queue
int dequeue() {
int item;
// Check if the queue is empty
if (rear == -1 && front == -1) {
cout<<"ERROR: Queue is empty"<<endl;
return -999999;
}
item = queue[front];

if (front == rear) {
front = rear = -1;
} else {
// increase the front
front = (front + 1) % MAX_SIZE;
}
return item;

}

// returns the item from the front of the queue
int getFront() {
// Check if the queue is empty
if (rear == -1 && front == -1) {
cout<<"ERROR: Queue is empty"<<endl;
return -999999;
}

return queue[front];
}
};

int main() {
QueueArray queue;
queue.enqueue(34);
queue.enqueue(35);
queue.enqueue(41);
queue.enqueue(56);
printf("%d\n", queue.dequeue());
printf("%d\n", queue.dequeue());
queue.enqueue(62);
queue.enqueue(63);
queue.enqueue(64);
queue.enqueue(65);
queue.enqueue(66);
queue.enqueue(67);
queue.enqueue(68);
queue.enqueue(69);
printf("%d\n", queue.dequeue());
queue.enqueue(70);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Java implementation of Queue using array

public class QueueArray {
private static final int MAX_SIZE = 10;
private int[] queue;
private int front;
private int rear;

public QueueArray() {
queue = new int[MAX_SIZE];
front = -1;
rear = -1;
}

// insert an item at the rear of the queue
public void enqueue(int item) {
// Check if the queue is full
if ((rear + 1) % MAX_SIZE == front) {
System.out.println("ERROR: Queue is full");
return;
}

// if there are no items, make front and rear 1
// else increment the rear by 1
if (front == -1 && rear == -1) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}

// insert the time at rear
queue[rear] = item;
}

// removes the item from the front of the queue
public int dequeue() {
int item;
// Check if the queue is empty
if (rear == -1 && front == -1) {
System.out.println("ERROR: Queue is empty");
return -999999;
}
item = queue[front];

if (front == rear) {
front = rear = -1;
} else {
// increase the front
front = (front + 1) % MAX_SIZE;
}
return item;

}

// returns the item from the front of the queue
public int getFront() {
// Check if the queue is empty
if (rear == -1 && front == -1) {
System.out.println("ERROR: Queue is empty");
return -999999;
}

return queue[front];
}

public static void main(String [] args) {
QueueArray queue = new QueueArray();
queue.enqueue(34);
queue.enqueue(35);
queue.enqueue(41);
queue.enqueue(56);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
queue.enqueue(62);
queue.enqueue(63);
queue.enqueue(64);
queue.enqueue(65);
queue.enqueue(66);
queue.enqueue(67);
queue.enqueue(68);
queue.enqueue(69);
System.out.println(queue.dequeue());
queue.enqueue(70);
}
}

Using linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Queue implementation in C using linked list

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node *NodePtr;

// define front and rear globally
NodePtr front = NULL;
NodePtr rear = NULL;

// inserts an item at the rear of the queue
void enqueue(int item) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = item;
node->next = NULL;
node->prev = NULL;

// if the queue is empty, make this node front and rear
// else insert it at the end of the queue
if (rear == NULL) {
rear = node;
front = node;
} else {
rear->next = node;
node->prev = rear;
rear = node;
}
}

// remove the item at the front of the queue
int dequeue() {
int item;
if (front == NULL) {
printf("%s\n", "ERROR: Queue is empty");
return -999999;
}

// destory the front and make the next item new front
item = front->data;
NodePtr next = front->next;

if (next != NULL) {
next->prev = NULL;
} else {
rear = NULL;
}

free(front);
front = next;
return item;
}


// returns the item at the front of the queue
int getFront() {
if (front == NULL) {
printf("%s\n", "ERROR: Queue is empty");
return -999999;
}

return front->data;
}

int main() {
enqueue(34);
enqueue(35);
enqueue(41);
enqueue(56);
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("%d\n", dequeue());
printf("%d\n", dequeue());
enqueue(70);
printf("%d\n", getFront());
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// C++ implementation of queue using array

#include <iostream>
using namespace std;

class QueueArray {
private:
const static int MAX_SIZE = 10;
int queue[MAX_SIZE];
int rear;
int front;
public:
QueueArray() {
rear = front = -1;
}

// insert an item at the rear of the queue
void enqueue(int item) {
// Check if the queue is full
if ((rear + 1) % MAX_SIZE == front) {
cout<<"ERROR: Queue is full"<<endl;
return;
}

// if there are no items, make front and rear 1
// else increment the rear by 1
if (front == -1 && rear == -1) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}

// insert the time at rear
queue[rear] = item;
}

// removes the item from the front of the queue
int dequeue() {
int item;
// Check if the queue is empty
if (rear == -1 && front == -1) {
cout<<"ERROR: Queue is empty"<<endl;
return -999999;
}
item = queue[front];

if (front == rear) {
front = rear = -1;
} else {
// increase the front
front = (front + 1) % MAX_SIZE;
}
return item;

}

// returns the item from the front of the queue
int getFront() {
// Check if the queue is empty
if (rear == -1 && front == -1) {
cout<<"ERROR: Queue is empty"<<endl;
return -999999;
}

return queue[front];
}
};

int main() {
QueueArray queue;
queue.enqueue(34);
queue.enqueue(35);
queue.enqueue(41);
queue.enqueue(56);
printf("%d\n", queue.dequeue());
printf("%d\n", queue.dequeue());
queue.enqueue(62);
queue.enqueue(63);
queue.enqueue(64);
queue.enqueue(65);
queue.enqueue(66);
queue.enqueue(67);
queue.enqueue(68);
queue.enqueue(69);
printf("%d\n", queue.dequeue());
queue.enqueue(70);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// Java implementation of Queue using array

public class QueueArray {
private static final int MAX_SIZE = 10;
private int[] queue;
private int front;
private int rear;

public QueueArray() {
queue = new int[MAX_SIZE];
front = -1;
rear = -1;
}

// insert an item at the rear of the queue
public void enqueue(int item) {
// Check if the queue is full
if ((rear + 1) % MAX_SIZE == front) {
System.out.println("ERROR: Queue is full");
return;
}

// if there are no items, make front and rear 1
// else increment the rear by 1
if (front == -1 && rear == -1) {
front = rear = 0;
} else {
rear = (rear + 1) % MAX_SIZE;
}

// insert the time at rear
queue[rear] = item;
}

// removes the item from the front of the queue
public int dequeue() {
int item;
// Check if the queue is empty
if (rear == -1 && front == -1) {
System.out.println("ERROR: Queue is empty");
return -999999;
}
item = queue[front];

if (front == rear) {
front = rear = -1;
} else {
// increase the front
front = (front + 1) % MAX_SIZE;
}
return item;

}

// returns the item from the front of the queue
public int getFront() {
// Check if the queue is empty
if (rear == -1 && front == -1) {
System.out.println("ERROR: Queue is empty");
return -999999;
}

return queue[front];
}

public static void main(String [] args) {
QueueArray queue = new QueueArray();
queue.enqueue(34);
queue.enqueue(35);
queue.enqueue(41);
queue.enqueue(56);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
queue.enqueue(62);
queue.enqueue(63);
queue.enqueue(64);
queue.enqueue(65);
queue.enqueue(66);
queue.enqueue(67);
queue.enqueue(68);
queue.enqueue(69);
System.out.println(queue.dequeue());
queue.enqueue(70);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# Python implementation of queue using linked list

class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None

class QueueLinkedList:
def __init__(self):
self.front = None
self.rear = None

# inserts an item at the rear of the queue
def enqueue(self, item):
node = Node(item)

# if the queue is empty, make this node front and rear
# else insert it at the end of the queue
if self.rear == None:
self.rear = node
self.front = node
else:
self.rear.next = node
node.prev = self.rear
self.rear = node

# remove the item at the front of the queue
def dequeue(self):
if self.front == None:
print "ERROR: Queue is empty"
return -999999

# destory the front and make the next item new front
item = self.front.data
next_node = self.front.next

if next_node != None:
next_node.prev = None
else:
self.rear = None

self.front = next_node;
return item

# returns the item at the front of the queue
def getFront(self):
if self.front == None:
print "ERROR: Queue is empty"
return -999999

return self.front.data

if __name__ == "__main__":
queue = QueueLinkedList()
queue.enqueue(34)
queue.enqueue(35)
queue.enqueue(41)
queue.enqueue(56)
print queue.dequeue()
print queue.dequeue()
print queue.dequeue()
print queue.dequeue()
queue.enqueue(70)
print queue.getFront()