Last Updated: 17 May, 2023

Implement Queue Using Linked List

Easy

Asked in company

Problem statement

You are given ‘q’ queries, where each query can be of the following types:

(1) 1 x -> this means to push the element ‘x’ in the queue.
(2) 2 -> This means deleting the front element of the queue and returning it. If there’s no element in the queue, return -1.

Your task is to implement a queue that supports these two queries.

You must write an algorithm whose time complexity is O(1), and whose space complexity is O(1).

Note:

In the output, you will see the output of queries of type 2. 
In the queries, there will be at least one type 2 query.
You will be given two functions, ‘push’, and ‘pop’. 
Your task is to implement the two functions.

Example:

Input: ‘q’ = 5
‘queries’ = [[1 3], [2], [1 4], [2], [2]]

Output: 3 4 -1

Explanation: After the first query, the queue is {3}. After the second query, the queue is {}, and we returned 3. After the third query, the queue is {4}. After the fourth query, the queue is {}, and we returned 4. After the fifth query, the queue is {}, and we returned -1(since there was no element at the time of the pop statement).

Input Format

The first line contains one integer, ‘q’, denoting the number of queries.

The following ‘q’ lines contain one of the two queries described in the statement.

Output format:

Return the integer for every type 2 query.

Note:-

You don't need to print anything. Just implement the given function.

Solve now

Approaches

01 Approach

In the push function, we will make a new node ‘tempNode’, and in the ‘next’ of ‘rear’ node of the linked list, we will attach this node ‘tempNode’.

In the pop function, we will remove the ‘front’ node of the linked list, and assign ‘front’ node to the ‘next’ of ‘front’ node. However, we need to look for the case when the ‘front’ node is ‘NULL’.

The steps are as follows:-

// Function to push element in the queue
function push(Queue* q, int x):

Create a temporary node ‘tempNode’, giving the value ‘x’.
If ‘front == NULL’:
q->front = q->rear = tempNode
Else:
q->rear = tempNode
q = q->rear

// Function to pop element from the queue
function pop(Queue* q):

Create a temporary node ‘tempNode’, and assign it to ‘q->front’.
If ‘tempNode == NULL’:
Return -1
Initialize a variable ‘answer’, and assign it to ‘tempNode.val’.
If ‘tempNode.next != NULL’:
Assign ‘tempNode’ to the ‘next’ of ‘tempNode’, i.e., tempNode = tempNode.next
delete ‘q->front’.
Assign ‘q->front’ to ‘tempNode’, i.e., q->front = tempNode
Else:
delete ‘q->front’.
Assign ‘front’, and ‘rear’ of the queue to be equal to ‘NULL’.
Return ‘answer’.