DSA 18: Queues [Part 1]

1. Definition

A queue is data structure, designed to process temporary data like a stack, however with variations on the order of data-processing (or data operations: insert, delete & read):

• array with restrictions
  • an abstract data class
    
  • visually like a single-lane drive-through at your favourite fast-food restaurant
    
  • or first-in, first-out (FIFO)
    
• front or beginning:
  • Is the First item of the queue
    
• back or end:
  • Is the Last item of the queue

2. Restrictions: Operational

2.1 add() or insert:

• back only
  • e.g. a customer joins the queue at the back, they can’t make an order (be processed) yet.

2.2 pop() or delete:

• front only
  • e.g. a customer at the front of queue can make & receive their order (processing) and leave the queue (order is complete, processed).

2.3 read():

• front only
  • e.g. customer service rep can only serve customer at their booth (first customer).

3. Queue Class Implementation: Python

class Queue:
    def __init__(self):
        print(f"queue created")
        self.data = []

    def add(self,value):
        self.data.append(value)
        print(f"{value!r} added: {self.data!r}")

    def remove(self):
        if len(self.data)>0:
            value = self.data.pop(0) # just realised can index 0
            # value = self.data.pop(-len(self.data))
            #   pop(-1) - is default last item
            #   pop(-2) - is second last item
            #   pop(-arrlen) - first item
            print(f"{value!r} removed: {self.data!r}")
            return value
        else:
            print(f"empty queue")
            return None
    
    def read(self):
        if len(self.data)>0:
            value = self.data[0]
            print(f"{value!r} read: {self.data!r}")
            return value
        else:
            print(f"empty queue")
            return None

4. Testing

tony_q = Queue()
tony_q.add(1)
tony_q.add(2)
tony_q.add(3)
tony_q.read()
tony_q.remove()
tony_q.read()
tony_q.remove()
tony_q.remove()
tony_q.remove()

queue created
1 added: [1]
2 added: [1, 2]
3 added: [1, 2, 3]
1 read: [1, 2, 3]
1 removed: [2, 3]
2 read: [2, 3]
2 removed: [3]
3 removed: []
empty queue