Circular Queue

Easy
0/40
Average time to solve is 15m
profile
Contributed by
140 upvotes
Asked in companies
AppleShareChatWolters Kluwer

Problem statement

You will be given ‘Q’ queries. You need to implement a circular queue according to those queries. Each query will belong to one of these two types:

1 ‘X’: Enqueue element ‘X’ into the end of the nth queue. Returns true if the element is enqueued, otherwise false.

2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.
Note: 
Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains two space-separated integers ‘N’ and ‘Q’ denoting the size of queue and number of queries, respectively. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For query of type 1, the integer ‘P’ is equal to 1 and it is followed by one integer ‘X’ denoting the element on which operation is to be performed.

For query of type 2, the integer ‘P’ is equal to 2 which dequeues the element.
Output Format: 
For each query, return the output returned after performing the corresponding operation on the data structure. 

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything. It has already been taken care of. You just have to complete the given functions.
Constraints: 
1 <= N <= 1000
1 <= Q <= 10^5 
1 <= P <= 2
1 <= X <= 10^5

Time limit: 1 sec
Sample Input 1:
3 7
1 2 
1 3 
2 
1 4 
1 6 
1 7 
2
Sample Output 1:
True 
True
2
True
True
False
3
Explanation of Sample Output 1:
For this input, we have the size of the queue, 'N' = 3, and the number of queries, 'Q' = 7.

Operations performed on the queue are as follows:

push(2): Push element ‘2’ into the queue. This returns true.
push(3): Push element ‘3’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 2.
push(4): Push element ‘4’ into the queue. This returns true.
push(6): Push element ‘6’ into the queue. This returns true.
push(7): Push element ‘7’ into the queue. This returns false because the queue is full.
pop(): Pop the top element from the queue. This returns 3.
Sample Input 2:
4 7
1 11 
1 51 
1 26 
2 
1 6
2
2
Sample Output 2:
True
True
True
11
True
51
26
Explanation for Sample Output 2:
For this input, we have the size of the queue, 'N' = 3, and the number of queries, 'Q' = 7.

Operations performed on the queue are as follows:

push(11): Push element ‘11’ into the queue. This returns true.
push(51): Push element ‘51’ into the queue. This returns true.
push(26): Push element ‘26’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 11.
push(6): Push element ‘6’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 51.
pop(): Pop the top element from the queue. This returns 26.
Hint

Can you think of using arrays?

Approaches (1)
Using Array

In this approach, we will be implementing a circular queue using arrays. A circular queue has two key methods or purpose:

 

  1. enqueue():
    • Check whether the queue is full.
      • A queue is full when the front is next to the rear. For example, with a queue of size 6, if front is 0 and rear is 5, or if front is 2 and rear is 1, it means that the queue is full.
      • If it is full, then return false.
      • If the queue is not full, then check if rear is the last index.
        • If it is, set rear to 0;
        • If it is not, increment rear and add the value at that index.
  2. dequeue():
    • Check whether the queue is empty (i.e., if front/rear has a value of -1).
      • If it is empty, the return -1.
      • If the queue is not empty, then check if the queue has only one value (i.e., front == rear).
        • If it does have only one value, set both rear and front to -1.
        • If it does not, check if front is the last index of the queue and, if so, set front to 0, otherwise, increment front.
Time Complexity

O(1).

 

Since we do not need to iterate in order to perform these methods, so the time complexity is O(1).

Space Complexity

O(N), where ‘N’ is the size of the queue.

 

Since array used for storing the values makes the space complexity to be O(N).

Code Solution
(100% EXP penalty)
Circular Queue
Full screen
Console