Last Updated: 5 Feb, 2025

Implement Queue using Arrays

Easy

Asked in companies

Solve now

Problem statement

Queue is a linear data structure that follows the idea of First In First Out. That means insertion and retrieval operations happen at opposite ends.

Implement a simple queue using arrays.

You are given 'query' queries which are either of the 2 types:

1 'e': Enqueue (add) element ‘e’ at the end of the queue.

2: Dequeue (retrieve) the element from the front of the queue. If the queue is empty, return -1.

Example:

Input: Queries: 
             [ 1 2,
               1 7,
               2,
               1 13, 
               2, 
               2, 
               2 ]

Output:
         [ 2, 
           7, 
           13,  
           -1 ]

Explanation: After each operation, our queue is equal to the following:
1 2: {2}
1 7: {2, 7}
2: {7} and 2 is printed
1 13: {7, 13}
2: {13} and 7 is printed
2: {} and 13 is printed
2: {} and -1 is printed since the queue is empty.

Input Format:

The first line contains an integer ‘query’, the number of queries.
The next ‘query’ lines each contain a query.
If the first integer in the line is equal to 1, then it is an enqueue query and is followed by the integer 'e'.
Otherwise, if the first integer is equal to 2, then it is a dequeue query.

Output format:

Solve the queries and print the appropriate dequeued values.

Note:

You need not consider the queries. You are given the structure of the queue. It consists of an array ‘a’ of size 100001 and 2 variables ‘rear’ and ‘front’, storing the index of the rear and the front elements, respectively. Both ‘rear’ and ‘front’ are initially equal to 0. 
Implement the enqueue() and the dequeue() functions which add and retrieve the elements from the queue.

Solve now

Approaches

01 Approach

The elements currently in the queue are defined using the variables ‘rear’ and ‘front’.

When the array ‘a’ is empty, both ‘rear’ and ‘front’ are 0. This means the range of the queue can be defined from index ‘front’ to ‘rear’ - 1 (both inclusive).

This means there is an element in the queue if ‘front’ < ‘rear’. Therefore our queue is empty if ‘front’ >= ‘rear’. In our implementation, ‘front’ should never exceed ‘rear’. So the condition ‘front’ = ‘rear’ is sufficient for checking if the queue is empty.

For enqueue operation, place the element at ‘a[rear]’ and then increase ‘rear’ by 1.

For dequeue operation, check if the queue is empty. If it is not empty, return ‘a[front]’ and increase ‘front’ by 1. Don’t write the increase statement after the return statement, else it will become unreachable. Either store the value to be returned or use postfix increment.

Since the maximum value of ‘query’ is 10 ^ 5, and the given length of ‘a’ is more than 10 ^ 5, we can implement a simple queue. Otherwise, we can also implement a Circular Queue using the array. It has a fixed size, but we can use the entire array.

The steps are as follows:

void enqueue(int ‘e’)

‘a[rear]’ = ‘e’
‘rear’ = ‘rear’ + 1

int dequeue()

If ‘front’ = ‘rear’:
- Return -1.
Return ‘a[front++]’.

Solve now