Implement Stack using Queues

Welcome to CodeYourCraft, your one-stop destination for learning programming! Today, we're diving into an interesting topic - implementing a Stack data structure using Queues. Let's get started! 🎯

What are Stacks and Queues?

Before we dive into the implementation, let's briefly understand what Stacks and Queues are.

Stacks

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It works like a pile of dishes where the last dish placed is the first one to be taken out.

Queues

A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It works like a line at a grocery store where the first person in line is the first one to be served.

Why implement Stack using Queues?

In some scenarios, we may not have direct access to implement Stacks, but we have Queues available. In such cases, we can leverage Queues to create a Stack-like behavior. 💡

Implementing Stack using Queues in Python

Now that we have a basic understanding let's dive into the implementation. We'll use Python for our examples, but the concepts can be applied to other programming languages as well.

python

class StackUsingQueue:
    def __init__(self):
        self.queue1 = queue.Queue()
        self.queue2 = queue.Queue()

    def push(self, item):
        self.queue1.put(item)

        # Transfer elements from queue1 to queue2
        while not self.queue1.empty():
            self.queue2.put(self.queue1.get())
            # Put the first element of queue2 back to queue1 to maintain the stack behavior
            if not self.queue1.empty():
                self.queue1.put(self.queue2.get())
        # Swap queue1 and queue2 to perform the final push operation
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self):
        if self.queue1.empty():
            return "Stack is empty"
        return self.queue1.get()

    def peek(self):
        if self.queue1.empty():
            return "Stack is empty"
        return self.queue1.queue[0]  # Return the first element of queue1 which is the top element of the stack

    def size(self):
        return self.queue1.qsize()

📝 Note: The queue module in Python provides the Queue data structure.

Understanding the implementation

Let's break down the implementation to understand how it works:

push(): It adds an item to the stack by first pushing it into queue1. Then, it transfers all the elements from queue1 to queue2. The first element of queue2 is then moved back to queue1 to maintain the LIFO behavior.
pop(): It removes the top element from the stack by first checking if the stack is empty. If not, it returns the first element of queue1.
peek(): It returns the top element of the stack without removing it. It first checks if the stack is empty, and if not, it returns the first element of queue1.
size(): It returns the number of elements in the stack by using the qsize() method of the queue object.

Practical Application

In real-world scenarios, this implementation can be useful when you have limited resources and need to simulate a Stack using Queues. For example, in a multi-threaded program where you don't want to use locks for each Stack, you can use Queues to implement a lightweight and efficient Stack.

Quiz Time!

We hope this lesson has helped you understand how to implement a Stack using Queues. Happy coding! 🎉