Example
Input:
Enqueue(1), Enqueue(2), Dequeue(), Enqueue(3), Front()
Output:
1, 3
Explanation:
First, we enqueue 1 and 2. Dequeuing returns 1. We then enqueue 3. The front of the queue is now 3.
Constraints
- The queue should support standard operations: enqueue, dequeue, and front.
- The operations should maintain the FIFO (First In, First Out) principle.
- The implementation should handle dynamic resizing of stacks if necessary.
- Performance should be considered for either fast enqueue or fast dequeue operations based on the use case.
Method one (By creating enQueue operation costly)
This technique makes positive that the oldest entered part is usually at the highest of stack one, so deQueue operation simply pops from stack1. to place the part at the prime of stack1, stack2 is employed.
enQueue(q, x):
- While stack1 isn’t empty, push everything from stack1 to stack2.
- Push x to stack1 (By considering the size of stacks is infinite).
- Push everything back to stack1.
Here time quality are going to be O(n).
deQueue(q):
- If stack1 is empty then an error
- Pop Associate in a Nursing item from stack1 and come back it
Here time quality are going to be O(1).
Read about Shrinking Kotlin libraries & apps using Reflection with R8 on Coding Ninjas Blog.
Below is that the implementation of the on top of approach:
C++
#include <iostream>
#include <stack>
using namespace std;
struct Queue {
stack<int> s1, s2;
void enQueue(int x) {
// Move all elements from s1 to s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
}
int deQueue() {
// If first stack is empty
if (s1.empty()) {
cout << "Queue is Empty\n";
exit(0);
}
// Return top of s1
int x = s1.top();
s1.pop();
return x;
}
};
// Driver code
int main() {
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
cout << q.deQueue() << '\n';
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.Stack;
class Queue {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
void enQueue(int x) {
// Move all elements from s1 to s2
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
// Push item into s1
s1.push(x);
// Push everything back to s1
while (!s2.isEmpty()) {
s1.push(s2.pop());
}
}
int deQueue() {
if (s1.isEmpty()) {
System.out.println("Queue is Empty");
System.exit(0);
}
return s1.pop();
}
public static void main(String[] args) {
Queue q = new Queue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
System.out.println(q.deQueue());
System.out.println(q.deQueue());
System.out.println(q.deQueue());
}
}
You can also try this code with Online Java Compiler
Python
class QueueUsingStacks:
def __init__(self):
self.s1 = [] # Stack1
self.s2 = [] # Stack2
def enQueue(self, x):
# Move all elements from s1 to s2
while self.s1:
self.s2.append(self.s1.pop())
# Push item into s1
self.s1.append(x)
# Push everything back to s1
while self.s2:
self.s1.append(self.s2.pop())
def deQueue(self):
if not self.s1:
print("Queue is Empty")
return None
return self.s1.pop()
# Driver code
q = QueueUsingStacks()
q.enQueue(1)
q.enQueue(2)
q.enQueue(3)
print(q.deQueue()) # Output: 1
print(q.deQueue()) # Output: 2
print(q.deQueue()) # Output: 3
You can also try this code with Online Python Compiler
JS
class QueueUsingStacks {
constructor() {
this.s1 = [];
this.s2 = [];
}
enQueue(x) {
// Move all elements from s1 to s2
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
// Push item into s1
this.s1.push(x);
// Push everything back to s1
while (this.s2.length) {
this.s1.push(this.s2.pop());
}
}
deQueue() {
if (this.s1.length === 0) {
console.log("Queue is Empty");
return null;
}
return this.s1.pop();
}
}
// Driver code
const q = new QueueUsingStacks();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
console.log(q.deQueue());
console.log(q.deQueue());
console.log(q.deQueue());
You can also try this code with Online Javascript Compiler
Output:
Complexity Analysis:
- Time Complexity:
- Push operation: O(N): In the worst case we’ve got the empty whole of stack one into stack two.
- Pop operation: O(1). Same as pop operation in a stack.
- Auxiliary Space: O(N): Use of a stack for storing values. Method two (By creating deQueue operation costly)In this technique, in en-queue operation, the new part is entered at the highest of stack1. In de-queue operation, if stack2 is empty then all the weather square measure emotional to stack2 and eventually prime of stack2 is came.
Method 2 (By making deQueue operation costly):
In Method 2, the deQueue operation is made costly by transferring all elements from Stack1 to Stack2 during a dequeue. This ensures that the oldest element is always on top of Stack2 for efficient removal.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
Here time complexity will be O(n)
enQueue (q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from stack1 to stack2.
3) Pop the element from stack2 and return it.
Here time complexity will be O(n).
Method two is certainly better than method one.
Method one moves all the weather doubly in enQueue operation, whereas technique two (in deQueue operation) moves {the parts|the weather} once and moves elements on condition that stack2 empty. So, the amortised quality of the dequeue operation becomes
Implementation of method 2:
C++
#include <iostream>
#include <stack>
using namespace std;
struct Queue {
stack<int> s1, s2;
// Enqueue an item to the queue
void enQueue(int x) {
// Push item into the first stack
s1.push(x);
}
// Dequeue an item from the queue
int deQueue() {
// If both stacks are empty
if (s1.empty() && s2.empty()) {
cout << "Queue is empty";
exit(0);
}
// If s2 is empty, move elements from s1
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
// Return the top item from s2
int x = s2.top();
s2.pop();
return x;
}
};
// Driver code
int main() {
Queue q;
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
cout << q.deQueue() << '\n'; // Output: 1
cout << q.deQueue() << '\n'; // Output: 2
cout << q.deQueue() << '\n'; // Output: 3
return 0;
}
You can also try this code with Online C++ Compiler
Java
import java.util.Stack;
class Queue {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
// Enqueue an item to the queue
void enQueue(int x) {
s1.push(x);
}
// Dequeue an item from the queue
int deQueue() {
if (s1.isEmpty() && s2.isEmpty()) {
System.out.println("Queue is empty");
System.exit(0);
}
// If s2 is empty, move elements from s1 to s2
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
// Return the top item from s2
return s2.pop();
}
public static void main(String[] args) {
Queue q = new Queue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
System.out.println(q.deQueue()); // Output: 1
System.out.println(q.deQueue()); // Output: 2
System.out.println(q.deQueue()); // Output: 3
}
}
You can also try this code with Online Java Compiler
Python
class QueueUsingTwoStacks:
def __init__(self):
self.s1 = [] # First stack
self.s2 = [] # Second stack
# Enqueue an item to the queue
def enQueue(self, x):
self.s1.append(x)
# Dequeue an item from the queue
def deQueue(self):
if not self.s1 and not self.s2:
print("Queue is empty")
return None
# If s2 is empty, move elements from s1 to s2
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
# Return the top item from s2
return self.s2.pop()
# Driver code
q = QueueUsingTwoStacks()
q.enQueue(1)
q.enQueue(2)
q.enQueue(3)
print(q.deQueue()) # Output: 1
print(q.deQueue()) # Output: 2
print(q.deQueue()) # Output: 3
You can also try this code with Online Python Compiler
JS
class QueueUsingTwoStacks {
constructor() {
this.s1 = []; // First stack
this.s2 = []; // Second stack
}
// Enqueue an item to the queue
enQueue(x) {
this.s1.push(x);
}
// Dequeue an item from the queue
deQueue() {
if (this.s1.length === 0 && this.s2.length === 0) {
console.log("Queue is empty");
return null;
}
// If s2 is empty, move elements from s1 to s2
if (this.s2.length === 0) {
while (this.s1.length !== 0) {
this.s2.push(this.s1.pop());
}
}
// Return the top item from s2
return this.s2.pop();
}
}
// Driver code
const q = new QueueUsingTwoStacks();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
console.log(q.deQueue()); // Output: 1
console.log(q.deQueue()); // Output: 2
console.log(q.deQueue()); // Output: 3
You can also try this code with Online Javascript Compiler
Output:
Complexity Analysis:
- Time Complexity:
- Push operation: O(1). Same as pop operation in stack.
- Pop operation: O(N).
In the worst case we’ve got empty whole of stack one into stack two
Use of stack for storing values.
Queue may also be enforced victimisation one user stack and one call Stack. Below is changed technique two wherever rule (or call Stack) is employed to implement queue victimisation just one user outlined stack.
- enQueue(x)
- 1) Push x to stack1.
- deQueue:
- 1) If stack1 is empty then error.
6 2) If stack1 has just one part then come back it. - 3) Recursively pop everything from the stack1, store the popped item
- during a variable res, push the res back to stack1 and come back res
The step three makes positive that the last popped item is usually came and since the rule stops once there’s just one item in stack1 (step 2), we have a tendency to get the last part of stack1 in deQueue() and every one different things square measure pushed back in step.
You can also read about, floyd's algorithm
Recommended Topic, binary search algorithm
Frequently Asked Questions
How many queues are needed to implement a stack?
Two queues will be required to implement a stack with only push and pop operation.
How do you implement stacks?
Stacks are implemented by various methods. They can be implemented with traditional methods by writing the pop, push, size, isempty functions on their own or by using queues to implement the stacks.
Why is it challenging to implement a queue using stacks?
Implementing a queue using stacks is challenging because stacks follow Last In, First Out (LIFO) order, while queues follow First In, First Out (FIFO). This requires careful management of the stack operations to mimic queue behavior.
What are some real-world use cases where a queue implemented using stacks might be useful?
A queue implemented using stacks can be useful in scenarios like scheduling tasks, managing requests in web servers, or handling asynchronous data processing where order preservation is crucial despite the underlying data structure's limitations.
What is the fundamental difference between a queue and a stack?
The fundamental difference between a queue and a stack lies in their order of processing. A stack operates on LIFO (Last In, First Out), while a queue operates on FIFO (First In, First Out), impacting how elements are added and removed.
Conclusion
After reading the above article we realise several important things. We now know that a stack is a LIFO data structure where insertion and deletion operations are taking place on the same end (top of the stack) and a queue is a FIFO data structure where insertion is taking place on one end (rear of the queue) and deletion is taking place on the other end (front of the queue).
We are now aware of two methods of implementing a queue using a stack. The first one is where we use two stacks and make the enqueue operation costlier and the second is where we also use two stacks but make the dequeue operation costlier.
The second method is more suitable for practical implementation because in the first method the elements are being moved twice for each operation whereas in the second method the need of moving the elements only arises if the second stack is empty.
240+ registered 
