Last Updated: 27 Jul, 2021

Implement a Queue

Easy

Asked in companies

Solve now

Problem statement

Implement a Queue Data Structure specifically to store integer data using a Singly Linked List or an array.

You need to implement the following public functions :

1. Constructor: It initializes the data members as required.

2. enqueue(data): This function should take one argument of type integer. It enqueues the element into the queue.

3. dequeue(): It dequeues/removes the element from the front of the queue and in turn, returns the element being dequeued or removed. In case the queue is empty, it returns -1.

4. front(): It returns the element being kept at the front of the queue. In case the queue is empty, it returns -1.

5. isEmpty(): It returns a boolean value indicating whether the queue is empty or not.

Operations Performed on the Queue :

Query-1(Denoted by an integer 1): Enqueues integer data to the queue.

Query-2(Denoted by an integer 2): Dequeues the data kept at the front of the queue and returns it to the caller, return -1 if no element is present in the queue.

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the front of the queue but doesn't remove it, unlike the dequeue function, return -1 if no element is present in the queue.

Query-4(Denoted by an integer 4): Returns a boolean value denoting whether the queue is empty or not.

Input Format :

The first line contains an integer ‘t’ denoting the number of test cases.

For each test case, the first line contains an integer 'q' which denotes the number of queries to be run against each operation on the queue. 

Every 'q' lines represent an operation that needs to be performed.

For the enQueue operation, the input line will contain two integers separated by a single space, representing the type of the operation in the integer and the integer data being enqueued into the queue.

For the rest of the operations on the queue, the input line will contain only one integer value, representing the query being performed on the queue.

Output Format :

For Query-1, print the data being enqueued in the queue.
For Query-2, print the data being dequeued from the queue.
For Query-3, print the data kept on the front of the queue.
For Query-4, print 'true' or 'false'(without quotes).

Output for every query will be printed in a separate line.

Note :

You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.

Constraints :

1 <= t <= 5
1 <= q <= 5000
1 <= x <= 4
1 <= data <= 2^31 - 1

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Take two Node pointers tail and head and an integer size to store the size of the queue.

In the Constructor function:
1. Initialize the head and tail pointer NULL.
In the enQueue function:
1. Increase the value of size by 1.
2. Create a new Node having the value to be pushed in the queue as data.
3. If the head is NULL
  1. Update head = newNode.
  2. Update tail = newNode.
4. Else, Update tail -> next = newNode.
5. Return data.
In the isEmpty function:
1. If size is zero return 1.
In the deQueue function:
1. Check whether the queue is empty then return -1.
2. Take a variable ans = head -> data.
3. Update the head pointer to its next.
4. Check if, after the update, head is NULL then update tail to NULL.
5. Decrease the value of size by 1.
6. Return ans.
In the front Function:
1. Check whether the queue is empty then return -1.
2. Return the value of head -> data.

Solve now

02 Approach

The approach is simple, you have to implement these functions such that your queue works properly.

Take some integers front, rear, size, queueSize denoting the position of the front element, the position of the last element, the number of elements present in the queue, and the total size of the queue, respectively.

In the Constructor function:
1. Create an array of max size and assign this value to queueSize.
2. Update front, rear, and size to 0.
In the enQueue function:
1. Check if rear + 1 is equal to the queueSize that means the queue is full, return -1.
2. Else, update the value of rear to rear + 1 and size to size + 1.
3. Assign data to q[rear].
4. Return data.
In the isEmpty function:
1. If size is zero return 1.
In the deQueue function:
1. Check whether the queue is empty then return -1.
2. Take a variable ans = q[ front ].
3. Increase the value of front to front + 1.
4. Decrease the value of size by 1.
5. If size equals zero, update front and rear to 0.
6. Return ans.
In the front Function:
1. Check whether the queue is empty then return -1.
2. Return the value of q[ front ].

Solve now