Queue using Two Stacks —Hackerrank

Problem

Implement a queue using two stacks. Then process q queries, where each query is one of the following 3 types:

1. Enqueue element x into the end of the queue
2. Dequeue the element at the front of the queue
3. Print the element at the front of the queue

Example

Input

The first line contains a single integer, q, denoting the number of queries.

Each line i of the q subsequent lines contains a single query in the form described in the problem statement above. All three queries start with an integer denoting the query type, but only query 1 is followed by an additional space-separated value, x, denoting the value to be enqueued.

• 1 → enqueue
• 2 → dequeue
• 3 → print front of the queue

Output

For each query of type 3, print the value of the element at the front of the queue on a new line.

14
14

Explanation

Perform the following sequence of actions:

1. Enqueue 42; queue = {42}
2. Dequeue the value at the head of the queue, 42; queue = {}
3. Enqueue 14; queue = {14}
4. Print the value at the head of queue, 14; queue = {14}
5. Enqueue 28; queue = {14,28}
6. Print the value at the head of queue, 14; queue = {14,28}
7. Enqueue 60; queue = {14,28,60}
8. Enqueue 78; queue = {14,28,60,78}
9. Dequeue the value at the head of the queue, 14; queue = {28,60,78}
10. Dequeue the value at the head of the queue, 28; queue = {60,78}

Algorithm Walk-through

Enqueue 42

Dequeue

Enqueue 14

Check the top of Incoming Stack

The answer is 14.

Enqueue 28

Check the bottom of Incoming Stack

The answer is 14.

Enqueue 60

Enqueue 78

Dequeue

Dequeue

Check the top of Outgoing Stack

The answer is 60.

Solution

def Solution(input_arr):
    out_stack, in_stack = [], []
    
    for _input in input_arr:
        val = list(map(
            int, 
            _input.split()
        ))
        
        if val[0] == 1:
            in_stack.append(val[1])
            
        elif val[0] == 2:
            if not out_stack :
                while in_stack:
                    out_stack.append(
                        in_stack.pop()
                    )
            out_stack.pop()
            
        else:
            print(out_stack[-1] if out_stack else in_stack[0])
            
Solution([
    "1 42",
    "2",
    "1 14",
    "3",
    "1 28",
    "3",
    "1 60",
    "1 78",
    "2",
    "2"
])

Time and Space Complexity

• Time Complexity: O(N*N). Given N is the number of elements in the array. There could be a scenario where there are all enqueue commands, then when a dequeue command is invoked, it could take N times to POP from the Incoming Stack and PUSH to the Outgoing Stack.
• Space Complexity: if we were to consider the stacks, then it should be O(N+N).

Takeaways

Thank you for reading this short problem solving question. If anyone knows a better or faster time complexity to solve this question, feel free to comment and feedback. Peace! ✌️