Implementing Queue using Stacks 🎯

Welcome to CodeYourCraft's comprehensive guide on implementing Queue using Stacks! In this lesson, we'll dive into the world of data structures, specifically focusing on queues and stacks, and learn how to leverage the latter to create an efficient queue system.

Understanding Queues and Stacks 📝

Before we get started, let's quickly review what queues and stacks are and how they differ from each other.

Queues 📝

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. Queues are commonly used in scenarios like managing waiting lines or processing jobs sequentially.

Stacks 📝

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. Stacks are commonly used in functions call stacks, undo/redo operations, and depth-first search algorithms.

Implementing a Queue using Stacks 💡

Although queues and stacks have different principles, we can implement a queue using stacks efficiently. Here's a basic example in Python:

python

class Queue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def enqueue(self, item):
        self.stack1.append(item)

    def dequeue(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            # Now the top item is in the stack2
            return self.stack2.pop()
        else:
            return self.stack2.pop()

# Creating a Queue object
myQueue = Queue()

# Enqueueing items
myQueue.enqueue(1)
myQueue.enqueue(2)
myQueue.enqueue(3)

# Dequeueing items
print(myQueue.dequeue())  # Output: 1
print(myQueue.dequeue())  # Output: 2

# Let's add more items
myQueue.enqueue(4)
myQueue.enqueue(5)

# Dequeueing items
print(myQueue.dequeue())  # Output: 3
print(myQueue.dequeue())  # Output: 4
print(myQueue.dequeue())  # Output: 5

# The queue is now empty
print(myQueue.dequeue())  # Output: None

In this example, we created a simple queue implementation using two stacks: stack1 and stack2. When we enqueue an item, we add it to stack1. To dequeue an item, we first move all the items from stack1 to stack2 (if stack2 is empty) and then pop the top item from stack2.

Advanced Examples and Quiz 💡

Advanced Example

Let's create a more practical example of implementing a queue using stacks in a real-world scenario: a restaurant order system.

python

class Order:
    def __init__(self, name, dish):
        self.name = name
        self.dish = dish

class Restaurant:
    def __init__(self, name):
        self.name = name
        self.queue = Queue()

    def take_order(self, name, dish):
        self.queue.enqueue(Order(name, dish))

    def serve_order(self):
        return self.queue.dequeue().dish

restaurant = Restaurant("Pizza Hut")

# Taking orders
restaurant.take_order("John", "Pepperoni")
restaurant.take_order("Mike", "Cheese")
restaurant.take_order("Sara", "Veggie")

# Serving orders
print(restaurant.serve_order())  # Output: Pepperoni
print(restaurant.serve_order())  # Output: Cheese
print(restaurant.serve_order())  # Output: Veggie

In this example, we created a Restaurant class that implements a queue using stacks. The Order class represents an order with a customer's name and dish. When we take an order, we enqueue it in the queue. When we want to serve an order, we dequeue it and print the dish.

Quiz 💡

Question: What is the time complexity of the enqueue operation in the given queue implementation?

A: O(1) B: O(n) C: O(log n)

Correct: A - The time complexity of the enqueue operation is O(1) because we simply append an item to the stack1.

That's it for our comprehensive guide on implementing queues using stacks! We hope you found this lesson helpful in understanding the concepts and gaining practical experience. Happy coding! 💻🎉