Queue
Using Two
Stacks
Atharva Kulkarni (22404309)
Pranav Mirkar (22404307)
Pratik Kolhe(22404319)
• What is stack
• A Stack is a linear data structure that follows a particular order in which the
operations are performed.
• Stack follows LIFO (Last In First Out)
• The stack follows the LIFO order, which means that the last element added to the
stack will be the first element to be removed.
Operation on stack:
• push() - to insert an element into the stack.
• pop() - to remove an element from the stack.
2 Queue using two stack 20XX
• What is Queue
• A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
• It operates like a line where elements are added at one end (rear) and removed from the
other end (front).
• FIFO principles the element added first will be removed first.
Operation on Queue :-
• Enqueue (Insert): Adds an element to the rear of the queue.
• Dequeue (Delete): Removes and returns the element from the front of the
queue.
3 Presentation title 20XX
Implementation of queue using two stack
Requirement:
40 30 20 10
Queu
e
Stack Stack
1 2
4 Presentation title 20XX
Enqueue Operation
4
0
30 Elements are enqueued
into stack1.
20
10 Pushing
element
Stac s into
k1 stack
40 30 20 10 Que
ue
5 Queue using two stack 20XX
Elements are
transferred from
stack 1 to stack 2
40 1
0
30 20
20 3
0
1 40
0
Stack Stack
1 2
During dequeue, all elements from stack1 are transferred to stack2 (reversing the order).
6 20XX
Stack 2 is used to
dequeue elements,
maintaining the FIFO(First
In First Out) order.
10
Dequeued
10
20
Dequeued
20
30 Dequeued
30
Dequeued
40 40
Stack
2
7 20XX
• Advantages
1. Use of Basic Data Structures:
This approach demonstrates how a queue can be implemented using stacks, showing the versatility of stacks.
2. Efficient Space Usage
The space complexity is O(n) for both stack1 and stack2, which is optimal and similar to using a single
queue directly.
3. Simpler Code:
The code is relatively simple to implement once you understand the concept of transferring elements
between stacks.
8 Presentation title 20XX
.
• Disadvantages
1. Limited Practical Use:
While this approach is good for learning and problem-solving, it may not be used often in real-world
applications where a direct queue data structure is more appropriate and efficient.
2. Extra Overhead:
There is an extra step of transferring elements between two stacks, which introduces additional overhead. If a
large number of dequeue operations are required, this approach becomes costly in terms of performance.
9 P 20XX
10 Presentation title 20XX
