Table of Contents
In this blog, we’ll explore how to implement a queue using two stacks and a stack using two queues. We’ll provide implementations in both Java and Python, following clean code practices for better readability and maintainability. 💻
Queue Implementation Using Stacks 🥞
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. We can implement a queue using two stacks, where one stack is used for enqueue operation, and the other is used for dequeue operation.
Java Implementation: ☕
import java.util.Stack;
class QueueUsingStacks {
private Stack<Integer> enqStack; // For enqueue operation
private Stack<Integer> deqStack; // For dequeue operation
public QueueUsingStacks() {
enqStack = new Stack<>();
deqStack = new Stack<>();
}
// Enqueue operation
public void enqueue(int value) {
enqStack.push(value);
}
// Dequeue operation
public int dequeue() {
if (deqStack.isEmpty()) {
// Move all elements from enqStack to deqStack
while (!enqStack.isEmpty()) {
deqStack.push(enqStack.pop());
}
}
// If both stacks are empty, return an error value
if (deqStack.isEmpty()) {
return -1; // Or throw an exception
}
// Return the top element from deqStack
return deqStack.pop();
}
}Python Implementation: 🐍
class QueueUsingStacks:
def __init__(self):
self.enq_stack = [] # For enqueue operation
self.deq_stack = [] # For dequeue operation
def enqueue(self, value):
self.enq_stack.append(value)
def dequeue(self):
if not self.deq_stack:
# Move all elements from enq_stack to deq_stack
while self.enq_stack:
self.deq_stack.append(self.enq_stack.pop())
# If both stacks are empty, return an error value
if not self.deq_stack:
return -1 # Or raise an exception
# Return the top element from deq_stack
return self.deq_stack.pop()In both implementations, we use two stacks: enqStack (or enq_stack) for enqueue operation and deqStack (or deq_stack) for dequeue operation. The enqueue method simply pushes the element onto the enqStack. 🥞➡️🍽️
The dequeue method first checks if the deqStack is empty. If it is, we move all elements from enqStack to deqStack in reverse order. This ensures that the first element pushed into enqStack will be the last element in deqStack, maintaining the FIFO order. 🍽️⬅️🥞 If both stacks are empty, we return an error value or raise an exception. 🚫 Otherwise, we pop and return the top element from deqStack. 🍽️🔝
Stack Implementation Using Queues 🌮
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. We can implement a stack using two queues, where one queue is used for pushing elements, and the other is used for popping elements.
Java Implementation: ☕
import java.util.LinkedList;
import java.util.Queue;
class StackUsingQueues {
private Queue<Integer> pushQueue; // For push operation
private Queue<Integer> popQueue; // For pop operation
public StackUsingQueues() {
pushQueue = new LinkedList<>();
popQueue = new LinkedList<>();
}
// Push operation
public void push(int value) {
pushQueue.offer(value);
}
// Pop operation
public int pop() {
if (popQueue.isEmpty()) {
// Move all elements from pushQueue to popQueue except the last one
while (pushQueue.size() > 1) {
popQueue.offer(pushQueue.poll());
}
// If pushQueue is empty, return an error value
if (pushQueue.isEmpty()) {
return -1; // Or throw an exception
}
// The last element in pushQueue is the top of the stack
int topElement = pushQueue.poll();
popQueue.offer(topElement);
}
// Return the front element from popQueue
return popQueue.poll();
}
}Python Implementation: 🐍
from collections import deque
class StackUsingQueues:
def __init__(self):
self.push_queue = deque() # For push operation
self.pop_queue = deque() # For pop operation
def push(self, value):
self.push_queue.append(value)
def pop(self):
if not self.pop_queue:
# Move all elements from push_queue to pop_queue except the last one
while len(self.push_queue) > 1:
self.pop_queue.append(self.push_queue.popleft())
# If push_queue is empty, return an error value
if not self.push_queue:
return -1 # Or raise an exception
# The last element in push_queue is the top of the stack
top_element = self.push_queue.popleft()
self.pop_queue.append(top_element)
# Return the front element from pop_queue
return self.pop_queue.popleft()In both implementations, we use two queues: pushQueue (or push_queue) for push operation and popQueue (or pop_queue) for pop operation. The push method simply adds the element to the end of the pushQueue. 🌮➡️🍔
The pop method first checks if the popQueue is empty. If it is, we move all elements from pushQueue to popQueue except the last one. This last element in pushQueue is the top of the stack. 🌮🔝 We store this element in a temporary variable and add it to the end of popQueue. If pushQueue is empty, we return an error value or raise an exception. 🚫 Otherwise, we pop and return the front element from popQueue. 🍔⬅️🌮
In both implementations, we follow clean code practices by using descriptive variable and method names, adding comments to explain the logic, and handling edge cases like empty stacks or queues. 👌
By implementing a queue using stacks and a stack using queues, we can understand the underlying principles of these data structures and how they can be used to create different abstractions. 🧠 These implementations also demonstrate the power of using existing data structures to create new ones, showcasing the versatility of programming languages like Java and Python. 💪
