Implement Queue Using Linked List

Easy
0/40
Average time to solve is 20m
profile
Contributed by
30 upvotes
Asked in company
EPAM Systems

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).
Detailed explanation ( Input/output format, Notes, Images )
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.


Sample Input 1:
5
1 3
2
1 4
2
2
Sample Output 1 :
3 4 -1
Explanation Of Sample Input 1:
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).
Sample Input 2:
2
2
1 1
Sample Output 2:
-1
Explanation Of Sample Input 2:
Input: ‘q’ = 2
‘queries’ = [[2], [1 1]]

Output: -1

Explanation: After the first query, the queue remains {}, and we returned -1. After the second query, the queue is {1}.
Constraints:
2 <= q <= 10^4
1 <= Element ‘x’ in the push function <= 10^5

Time Limit: 1-sec
Hint

Use Linked List.

Approaches (1)
Linked List

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):

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

// Function to pop element from the queue

function pop(Queue* q):

  1. Create a temporary node ‘tempNode’, and assign it to ‘q->front’.
  2. If ‘tempNode == NULL’:
    • Return -1
  3. Initialize a variable ‘answer’, and assign it to ‘tempNode.val’.
  4. 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
  5. Else:
    • delete ‘q->front’.
    • Assign ‘front’, and ‘rear’ of the queue to be equal to ‘NULL’.
  6. Return ‘answer’.
Time Complexity

O( 1 ).
 

Push and pop function both take constant time.

 

Hence, the time complexity is O( 1 ).

Space Complexity

O( 1 ).

 

We are using constant space.

 

Hence, the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Implement Queue Using Linked List
Full screen
Console