Describe the difference between a stack and a queue. Provide an example of when you might use each data structure. Write functions to implement the push and pop methods for a stack and the enqueue and dequeue methods for a queue. Explain the time complexity of each of these operations. Additionally, discuss a scenario where you might need to implement a stack using a queue or a queue using a stack.

Stack vs. Queue

Stacks and queues are fundamental data structures used in computer science. They differ in the order in which elements are added and removed.

Definitions

• Stack: A stack is a LIFO (Last-In, First-Out) data structure. The last element added to the stack is the first one to be removed.
• Queue: A queue is a FIFO (First-In, First-Out) data structure. The first element added to the queue is the first one to be removed.

Analogy

Imagine a stack of plates. You add plates to the top and remove plates from the top. The last plate you put on the stack is the first one you take off.

Now, imagine a queue of people waiting in line. The first person to join the line is the first person to be served.

Use Cases

Implementations

Stack

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None  # Or raise an exception

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


# Example usage:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek()) # Output: 2

Queue

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

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None  # Or raise an exception

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


# Example Usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.peek()) # Output: 2

Time Complexity

Space Complexity

Both stack and queue implementations using lists have a space complexity of O(n), where n is the number of elements in the data structure. This is because they store each element in memory.

Implementing a Stack Using Queues

To implement a stack using queues, you would need two queue instances. Here's the push and pop logic:

• push(item): Enqueue the item into the first queue.
• pop(): Transfer all elements from the first queue to the second queue, except for the last element. Dequeue and return the last element from the first queue. Swap the names of the two queues so the second queue becomes the first for the next operation.

class StackUsingQueues:
    def __init__(self):
        self.q1 = Queue()
        self.q2 = Queue()

    def push(self, item):
        self.q1.enqueue(item)

    def pop(self):
        if self.q1.is_empty():
            return None

        while self.q1.size() > 1:
            self.q2.enqueue(self.q1.dequeue())

        popped_item = self.q1.dequeue()

        # Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1

        return popped_item

    def is_empty(self):
        return self.q1.is_empty()

    def size(self):
        return self.q1.size()

# Example usage:
stack = StackUsingQueues()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.pop())  # Output: 2

Implementing a Queue Using Stacks

To implement a queue using stacks, you would also need two stack instances. Here's the enqueue and dequeue logic:

• enqueue(item): Push the item onto the first stack.
• dequeue(): If the second stack is empty, transfer all elements from the first stack to the second stack. Pop and return the top element from the second stack.

class QueueUsingStacks:
    def __init__(self):
        self.s1 = Stack()
        self.s2 = Stack()

    def enqueue(self, item):
        self.s1.push(item)

    def dequeue(self):
        if self.s2.is_empty():
            if self.s1.is_empty():
                return None  # Or raise an exception
            while not self.s1.is_empty():
                self.s2.push(self.s1.pop())
        return self.s2.pop()

    def is_empty(self):
        return self.s1.is_empty() and self.s2.is_empty()

    def size(self):
        return self.s1.size() + self.s2.size()

# Example usage:
queue = QueueUsingStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # Output: 1
print(queue.dequeue())  # Output: 2

When to use Stack with Queue or vice versa

While not common in day-to-day development, implementing a stack with queues or a queue with stacks can be useful in specific scenarios:

• Constraints on available data structures: In situations where you only have access to one type of data structure (e.g., only queues are provided by a library), you can simulate the behavior of the other.
• Educational purposes: These implementations are excellent exercises to understand the fundamental properties of stacks and queues and how they can be related.
• Specific algorithmic requirements: Certain algorithms might require you to process data in a stack-like manner but might only provide queue-based operations, or vice versa.