How would you implement a queue or a stack in Python ?

In Python, you can implement a queue or a stack using various data structures, such as lists or the collections.deque module. Below is how you can implement both:

1. Stack Implementation

A stack follows the “Last In, First Out” (LIFO) principle, meaning the last element added is the first one to be removed.

Using a List

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

    def push(self, item):
        self.stack.append(item)  # Adds an item to the end of the list

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()  # Removes and returns the last item
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]  # Returns the last item without removing it
        return None

    def is_empty(self):
        return len(self.stack) == 0  # Checks if the stack is empty

    def size(self):
        return len(self.stack)  # Returns the number of items in the stack

Example usage:

stack = Stack()
stack.push(10)
stack.push(20)
print(stack.pop())  # Output: 20
print(stack.peek())  # Output: 10

2. Queue Implementation

A queue follows the “First In, First Out” (FIFO) principle, meaning the first element added is the first one to be removed.

Using a List

You can use a list, but removing items from the front can be inefficient (O(n) time complexity). To implement an efficient queue, it’s better to use collections.deque.

Using collections.deque

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)  # Adds an item to the end of the deque

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()  # Removes and returns the first item
        return None

    def peek(self):
        if not self.is_empty():
            return self.queue[0]  # Returns the first item without removing it
        return None

    def is_empty(self):
        return len(self.queue) == 0  # Checks if the queue is empty

    def size(self):
        return len(self.queue)  # Returns the number of items in the queue

Example usage:

queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())  # Output: 10
print(queue.peek())  # Output: 20

Summary

• Stack: Can be implemented with a list where items are added with append() and removed with pop().
• Queue: Can be implemented using deque for efficient appending and popping from both ends.

Both of these implementations support the basic operations like adding, removing, and checking the status of the queue or stack.