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_q

Mar 22, 2025 - 06:21

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])