Queue using Two Stacks| Queue
TASK(medium)
A queue is an abstract data type that maintains the order in which elements were added to it, allowing the oldest elements to be removed from the front and new elements to be added to the rear. This is called a First-In-First-Out (FIFO) data structure because the first element added to the queue (i.e., the one that has been waiting the longest) is always the first one to be removed.
A basic queue has the following operations:
- Enqueue: add a new element to the end of the queue.
- Dequeue: remove the element from the front of the queue and return it.
In this challenge, you must first implement a queue using two stacks. Then process queries, where each query is one of the following types:
- 1 x: Enqueue element 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.
Input Format
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.
Constraints
1<=q<=105
1<=type<=3
1<=|x|<=109
It is guaranteed that a valid answer always exists for each query of type
.Output Format
For each query of type , print the value of the element at the front of the queue on a new line.
Sample Input
STDIN Function
----- --------
1 0 q = 10 (number of queries)
1 42 1st query, enqueue 42
2 dequeue front element
1 14 enqueue 42
3 print the front element
1 28 enqueue 28
3 print the front element
1 60 enqueue 60
1 78 enqueue 78
2 dequeue front element
2 dequeue front element
Sample Output
14
14
SOLUTION 1
n = int(input())
ins = [list(map(int, input().split())) for _ in range(n)]
queue = []
for i in ins:
if i[0] == 1:
queue.append(i[1])
elif i[0] == 2:
queue.pop(0)
else:
print(queue[0])
SOLUTION 2
stack1 = []
stack2 = []
n = int(input())
for _ in range(n):
cmd = input()
if cmd[0] == '1':
while(len(stack2)): stack1.append(stack2.pop())
stack1.append(int(cmd[2:]))
elif cmd[0] == '2':
while(len(stack1)): stack2.append(stack1.pop())
stack2.pop()
elif cmd[0] == '3':
while(len(stack1)): stack2.append(stack1.pop())
print(stack2[-1])
EXPLANATION STEPS
1. Enqueue Operation:
- Always push elements onto stack1.
2. Dequeue Operation:
- If stack2 is empty, transfer all elements from stack1 to stack2. This ensures that the oldest element (front of the queue) is at the top of stack2.
- Pop the top element from stack2, which corresponds to dequeuing the front element of the queue.
3. Print Operation:
- If stack2 is empty, transfer elements from stack1 to stack2.
- Peek (access) the top element of stack2 without removing it, which corresponds to printing the front element of the queue.
