Understanding Queues

Introduction

Queues are fundamental data structures in computer science that play a crucial role in managing and organizing elements in a specific order. They follow the First-In-First-Out (FIFO) principle, meaning that the first element inserted into the queue is the first one to be removed. This concept closely resembles a real-world queue, such as people waiting in line for service.

In queues, elements are added at one end, known as the rear or tail, and removed from the other end, called the front or head. This behaviour ensures that elements are processed in the same order they arrived, making queues suitable for scenarios where fairness and order preservation are important.

Implementation

• Push (Enqueue)

  The push operation, also known as enqueue, adds an element to the rear of the queue, expanding its size. This operation ensures that newly arriving elements are placed at the end of the line, preserving the order in which they arrived. In Python, the enqueue operation can be implemented using the append() function to add an element to the end of the list representing the queue.

    def enqueue(queue, item):
        queue.append(item)
  

• Pop (Dequeue)

  The pop operation, also known as dequeue, removes the element from the front of the queue. It follows the FIFO principle, ensuring that the element that has been waiting in the queue the longest gets removed first. In Python, the dequeue operation can be implemented using the pop() function with an index of 0 to remove the first element from the list representing the queue.

    def dequeue(queue):
        if not isEmpty(queue):
            return queue.pop(0)
        else:
            return "Queue is empty"
  

• Top (Peek)

  The top operation, also known as peek, allows us to retrieve the element from the front of the queue without removing it. It provides a way to examine the next element that will be dequeued.

    def peek(queue):
        if not isEmpty(queue):
            return queue[0]
        else:
            return "Queue is empty"
  

• Is Empty

  The isEmpty operation checks whether the queue is empty or not. It returns a Boolean value indicating whether the queue has any elements. The isEmpty operation is vital for conditionally executing code based on the state of the queue.

    def isEmpty(queue):
        return len(queue) == 0
  

• Display

  The display operation presents the elements of the queue in their order. It allows us to visualize the contents of the queue, facilitating debugging and analysis.

    def display(queue):
        if not isEmpty(queue):
            print(queue)
        else:
            print("Queue is empty")
  

Time Complexities

1. Push (Enqueue)

   • Time Complexity: O(1)

   • The push operation has a constant time complexity, as it involves a simple insertion at the end of the queue. Regardless of the size of the queue, the time taken to enqueue an element remains constant.

2. Pop (Dequeue)

   • Time Complexity: O(1) (amortized)

   • The pop operation also has a constant time complexity on average. Although removing an element from the beginning of the queue requires shifting the remaining elements, the overall time complexity remains constant due to the efficient implementation of list operations in Python.

3. Top (Peek)

   • Time Complexity: O(1)

   • The top operation has a constant time complexity, as it involves accessing the first element directly without any additional computational overhead.

4. Display

   • Time Complexity: O(n)

   • The display operation has a linear time complexity, as it requires iterating over all the elements in the queue to print them. The time taken is proportional to the number of elements in the queue.

5. Is Empty

   • Time Complexity: O(1)

   • The isEmpty operation has a constant time complexity, as it involves checking the length of the queue. The time taken to determine if the queue is empty or not does not depend on the number of elements in the queue.

Real-Time Example

Let's consider a real-time example of a ticket counter simulation to better understand how queues work. Suppose we have a ticket counter with multiple customers waiting in line. We can model this scenario using a queue, where customers join the queue and are served in a first-come-first-serve manner.

# Ticket Counter Simulation

def ticket_counter_simulation():
    ticket_queue = []  # Initialize an empty queue

    # Enqueue customers
    enqueue(ticket_queue, "Customer1")
    enqueue(ticket_queue, "Customer2")
    enqueue(ticket_queue, "Customer3")
    enqueue(ticket_queue, "Customer4")

    # Serve customers
    while not isEmpty(ticket_queue):
        current_customer = dequeue(ticket_queue)
        print("Serving", current_customer)

# Output: Serving Customer1, Customer2, Customer3, Customer4

ticket_counter_simulation()