IMPLEMENT STACK
USING QUEUE
Introduction to Stack and Queue
Stack : LIFO Principle Stack is a linear data structure operating on Last In, First Out (LIFO)
principle, where the last added element is removed first. Common operations include push, pop,
peek, and isEmpty.
Queue : FIFO Principle: Queue is a linear data structure following First In, First Out (FIFO)
principle, where elements are added at the rear and removed from the front. Key operations are
enqueue, dequeue, peek, and isEmpty.
Differences Between Stack and Queue : Stack processes elements in LIFO order with insertion
and deletion at the top, while queue processes in FIFO order with insertion at rear and deletion at
front. Use cases and pointer management also differ.
PROBLEM STATEMENT
Implement stack using two queues. You need to complete the push and pop function of stack
class. You are given 2 types of queries-
'1' which represents that we need to push an integer into the stack.
'2' which represents that we need to pop the top element from the stack. If there is no top
element simply return -1.
Input Format
First line contains q of queries.
Followed by q lines.
Query of type 1 is followed by an integer x to push element in the stack.
Query of type 2 is for pop the top value from the stack and print it.
Output Format
Print the value for pop operations in the query given.
Example 1
Input
5
12
13
2
14
2
Output:
34
Example 2
Input
3
2
12
2
Output:
-1 2
LOGIC
1. Initialization: Two queues `q1` and `q2` are initialized as instances of the `LinkedList` class,
which implements the `Queue` interface.
2. Push Operation: When a new element is pushed onto the stack, it is added to `q1`. If `q1` is
not empty, the elements of `q1` are moved to `q2` one by one. Then, the new element is
added to `q1`. Finally, the elements of `q2` are moved back to `q1`. This ensures that the new
element is always at the front of the queue, simulating the behavior of a stack.
3. Pop Operation: When an element is popped from the stack, it is simply removed from `q1`
if `q1` is not empty. If `q1` is empty, `-1` is returned to indicate that the stack is empty.
LOGIC
4. Main Method: In the `main` method, the number of queries `q` is read from the input.
Then, a loop runs `q` times to process each query. For each query, the type of operation
(`QueryType`) is read from the input. If the operation is a push (`QueryType == 1`), the
value to be pushed onto the stack is read from the input and pushed onto the stack using
the `push` method. If the operation is a pop (`QueryType == 2`), the value popped from
the stack is added to the `ans` list using the `pop` method.
5. Output: Finally, the elements in the `ans` list are printed, separated by spaces, to
display the result of the pop operations.
JAVA CODE
import [Link].*; // Function to pop an element from stack using
import [Link].*; two queues.
int pop() {
class Queues { // your code here
if (![Link]()) {
Queue<Integer> q1 = new LinkedList<>(); return [Link]();
Queue<Integer> q2 = new LinkedList<>(); }
return -1;
// Function to push an element into }
stack using two queues. }
void push(int a) { public class Main {
// your code here public static void main(String args[])
if ([Link]() == true) { throws IOException {
Scanner sc = new Scanner([Link]);
[Link](a); Queues g = new Queues();
} else { int q = [Link]();
while (![Link]()) { ArrayList<Integer> ans = new
[Link]([Link]()); ArrayList<>();
} while (q > 0) {
[Link](a); int QueryType = [Link]();
while (![Link]()) { if (QueryType == 1) {
[Link]([Link]()); int a = [Link]();
[Link](a);
} } else if (QueryType == 2)
}
}
[Link]([Link]());
q--;
}
for (int x : ans)
[Link](x + " ");
[Link]();
}
}
Why Implement Stack using Queue?
• Prepares for system design and abstraction questions
• Reinforces algorithmic thinking
• Helps understand core data manipulation
Common Interview Questions
1. Implement stack using two queues. Which
operation should be costly?
2. Can you optimize space?
3. Why use queue when stack exists?
4. What about thread-safety?
5. Extend for max() in O(1)?
[Link]
THANK YOU
+91 78150 95095 codemithra@[Link] [Link]