queue

from collections import deque
import heapq

# Basic Queue Implementation using deque
class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        """Enqueue an item to the queue."""
        self.queue.append(item)

    def dequeue(self):
        """Dequeue an item from the queue. Returns None if the queue is empty."""
        if not self.is_empty():
            return self.queue.popleft()
        return None

    def front(self):
        """Return the front item of the queue."""
        if not self.is_empty():
            return self.queue[0]
        return None

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

    def size(self):
        """Return the size of the queue."""
        return len(self.queue)

    def clear(self):
        """Clear all items in the queue."""
        self.queue.clear()

    def print_queue(self):
        """Print all elements in the queue."""
        print(list(self.queue))


# Queue Implementation using Two Stacks
class QueueWithTwoStacks:
    def __init__(self):
        self.stack1 = Stack()
        self.stack2 = Stack()

    def enqueue(self, item):
        """Enqueue an item to the queue."""
        self.stack1.push(item)

    def dequeue(self):
        """Dequeue an item from the queue."""
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())
        return self.stack2.pop() if not self.stack2.is_empty() else None


# Circular Queue Implementation (Fixed-size Queue)
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front:
            print("Queue is full")
            return
        if self.front == -1:  # First element
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        item = self.queue[self.front]
        if self.front == self.rear:  # Single element
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

    def peek(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        return self.queue[self.front]

    def is_empty(self):
        return self.front == -1

    def size(self):
        if self.front == -1:
            return 0
        return (self.rear - self.front + 1) % self.capacity


# Priority Queue Implementation using a heap
class PriorityQueue:
    def __init__(self):
        self.queue = []
        self.counter = 0  # To maintain order for equal priorities

    def enqueue(self, item, priority):
        heapq.heappush(self.queue, (priority, self.counter, item))
        self.counter += 1

    def dequeue(self):
        if self.is_empty():
            return None
        return heapq.heappop(self.queue)[-1]

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[0][-1]

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

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


# Helper Function: Reverse a Queue using a stack
def reverse_queue(queue):
    """
    Reverse the elements of a queue using a stack.
    :param queue: The queue (using deque).
    :return: The reversed queue.
    """
    stack = []
    # Dequeue all elements and push them onto a stack
    while queue:
        stack.append(queue.popleft())

    # Push all elements back into the queue
    while stack:
        queue.append(stack.pop())

    return queue


# Example Use Cases

# 1. Basic Queue operations
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print("Queue operations:")
print(queue.front())  # Output: 10
print(queue.dequeue()) # Output: 10
print(queue.size())    # Output: 2
queue.print_queue()    # Output: [20, 30]

# 2. Queue with Two Stacks
queue2 = QueueWithTwoStacks()
queue2.enqueue(10)
queue2.enqueue(20)
queue2.enqueue(30)
print("\nQueueWithTwoStacks operations:")
print(queue2.dequeue())  # Output: 10
print(queue2.dequeue())  # Output: 20

# 3. Circular Queue operations
circular_queue = CircularQueue(3)
circular_queue.enqueue(10)
circular_queue.enqueue(20)
circular_queue.enqueue(30)
print("\nCircularQueue operations:")
print(circular_queue.dequeue())  # Output: 10
circular_queue.enqueue(40)
print(circular_queue.peek())    # Output: 20
print(circular_queue.size())    # Output: 3

# 4. Priority Queue operations
priority_queue = PriorityQueue()
priority_queue.enqueue("task1", 2)
priority_queue.enqueue("task2", 1)
priority_queue.enqueue("task3", 3)
print("\nPriorityQueue operations:")
print(priority_queue.dequeue())  # Output: task2
print(priority_queue.peek())     # Output: task1

# 5. Reverse a Queue
queue = deque([1, 2, 3, 4, 5])
print("\nReversing the queue:")
reversed_queue = reverse_queue(queue)
print(reversed_queue)  # Output: deque([5, 4, 3, 2, 1])