Queue

Queues are a linear data structure that store data in a “first in, first out” (FIFO) order. Unlike arrays, you cannot access elements by index and instead can only pull the next oldest element. This m

Queue SandboxQueue Continued...Dequeue

Queue.py

# lets think of another scenareo where we want to model a line at a store
#  or a queue at the airport

# for this comes the queue data structure
# like the stack we can add and remove data
# this is more like a line of people in a queue

# for this we could enqueue and item on to the data structure
# and we can dequeue an item from the queue

# This data structure works as a FIFO or (first in first out) data structure

# think of how you could utilise a linked list to create a queue

  
"""
A queue is a data structure whose primary purpose is to store and
return elements in First In First Out order. 
1. Implement the Queue class using an array as the underlying storage structure.
   Make sure the Queue tests pass.
2. Re-implement the Queue class, this time using the linked list implementation
   as the underlying storage structure.
   Make sure the Queue tests pass.
3. What is the difference between using an array vs. a linked list when 
   implementing a Queue?
   
Stretch: What if you could only use instances of your Stack class to implement the Queue?
         What would that look like? How many Stacks would you need? Try it!
"""

# Implement a Queue using an array for the underlying storage
class QueueA:
    def __init__(self):
        self.storage = []

    def __len__(self):
        return len(self.storage)

    def enqueue(self, value):
        self.storage.append(value)


    def dequeue(self):
        if len(self.storage) == 0:
            return None
        return self.storage.pop(0)


from linked_list import LinkedList

# Queue implementation using a Linked List for the underlying storage
class QueueL:
    def __init__(self):
        self.storage = LinkedList()
        self.size = 0

    def __len__(self):
        return self.size

    def enqueue(self, item):
        self.storage.add_to_tail(item)
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            return None
        self.size -= 1
        return self.storage.remove_head()
    

Queue2.py

# lets think of another scenareo where we want to model a line at a store
#  or a queue at the airport

# for this comes the queue data structure
# like the stack we can add and remove data
# this is more like a line of people in a queue

# for this we could enqueue and item on to the data structure
# and we can dequeue an item from the queue

# This data structure works as a FIFO or (first in first out) data structure

# think of how you could utilise a linked list to create a queue

  
"""
A queue is a data structure whose primary purpose is to store and
return elements in First In First Out order. 
1. Implement the Queue class using an array as the underlying storage structure.
   Make sure the Queue tests pass.
2. Re-implement the Queue class, this time using the linked list implementation
   as the underlying storage structure.
   Make sure the Queue tests pass.
3. What is the difference between using an array vs. a linked list when 
   implementing a Queue?
   
Stretch: What if you could only use instances of your Stack class to implement the Queue?
         What would that look like? How many Stacks would you need? Try it!
"""

# Implement a Queue using an array for the underlying storage
# class QueueA:
#     def __init__(self):
#         self.storage = []

#     def __len__(self):
#         return len(self.storage)

#     def enqueue(self, value):
#         self.storage.append(value)


#     def dequeue(self):
#         if len(self.storage) == 0:
#             return None
#         return self.storage.pop(0)

class QueueA:
    def __init__(self):
        self.storage = [] 

    def __len__(self):
        return len(self.storage)

    def enqueue(self, value):
        self.storage.append(value)

    def dequeue(self):
        if len(self.storage) == 0:
            return None
        return self.storage.pop(0)


from linked_list import LinkedList

# Queue implementation using a Linked List for the underlying storage
class QueueL:
    def __init__(self):
        self.storage = LinkedList()
        self.size = 0

    def __len__(self):
        return self.size

    def enqueue(self, item):
        self.storage.add_to_tail(item)
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            return None
        self.size -= 1
        return self.storage.remove_head()

class QueueLL(LinkedList):
    def __init__(self):
        super().__init__()
        self.size = 0

    def enqueue(self, item):
        self.add_to_tail(item)
        self.size += 1

    def dequeue(self):
        if self.size == 0:
            return None
        self.size -= 1
        return self.remove_head()
    

# FIFO: first in first out

# create the abstract data type
class Queue:
    def __init__(self):
        # initialize it to a one dimensional array or linked list
        self.queue = []

    """
    Stack methods (enqueue, dequeue, peek, is_empty, size_queue)
    """

    # function to check if the queue is empty O(1)
    def is_empty(self):
        return self.queue == []

    # function to add data to the queue O(1)
    def enqueue(self, data):
        self.queue.append(data)

    # function to remove and return the first item inserted to the queue O(N)
    def dequeue(self):

        # first check to make sure its not an empty queue
        if self.size_queue()!= 0:
            # get the first item in the queue
            data = self.queue[0]
            # remove it
            del self.queue[0]
            # return the item
            return data
        else:
            return -1

    # function to return the first item in the queue without removing it
    # O(1)
    def peek(self):
        return self.queue[0]

    # function get the size of the queue O(1)
    def size_queue(self):
        return len(self.queue)


"""
Using the methods
"""
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f'Size: {queue.size_queue()}')
print(f'Dequeue: {queue.dequeue()}')
print(f'Size: {queue.size_queue()}')
print(f'Peeked item: {queue.peek()}')
print(f'Size: {queue.size_queue()}')

Queue

• Implement a Queue class from scratch with an existing bug, the bug is that it cannot take more than 5 elements.

• Implement a Queue using two stacks. You may only use the standard push(), pop(), and peek() operations traditionally available to stacks. You do not need to implement the stack yourself (i.e. an array can be used to simulate a stack).

Queues in Python

Queues are a linear data structure that store data in a “first in, first out” (FIFO) order. Unlike arrays, you cannot access elements by index and instead can only pull the next oldest element. This makes it great for order-sensitive tasks like online order processing or voicemail storage.

You can think of a queue as a line at the grocery store; the cashier does not choose who to check out next but rather processes the person who has stood in line the longest.

We could use a Python list with append() and pop() methods to implement a queue. However, this is inefficient because lists must shift all elements by one index whenever you add a new element to the beginning.

Instead, it’s best practice to use the deque class from Python’s collections module. Deques are optimized for the append and pop operations. The deque implementation also allows you to create double-ended queues, which can access both sides of the queue through the popleft() and popright() methods.

Advantages:

• Automatically orders data chronologically

• Scales to meet size requirements

• Time efficient with deque class

Disadvantages:

• Can only access data on the ends

Applications:

• Operations on a shared resource like a printer or CPU core
• Serve as temporary storage for batch systems

• Provides an easy default order for tasks of equal importance

Common queue interview questions in Python

• Reverse first k elements of a queue

• Implement a queue using a linked list

• Implement a stack using a queue

Implementation

"""Make a Queue class using a list!
Hint: You can use any Python list method
you'd like! Try to write each one in as
few lines as possible.
Make sure you pass the test cases too!"""

class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        if(self.storage):
            self.storage.append(new_element)
        else:
            self.storage = [new_element]
        return new_element

    def peek(self):
        if(self.storage):
            return self.storage[0]
        else:
            return None

    def dequeue(self):
        if(self.storage):
            return self.storage.pop(0)
        else:
            return None

# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print q.peek()

# Test dequeue
# Should be 1
print q.dequeue()

# Test enqueue
q.enqueue(4)
# Should be 2
print q.dequeue()
# Should be 3
print q.dequeue()
# Should be 4
print q.dequeue()
q.enqueue(5)
# Should be 5
print q.peek()

"""Make a Queue class using a list!
Hint: You can use any Python list method
you'd like! Try to write each one in as
few lines as possible.
Make sure you pass the test cases too!"""

class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        if(self.storage):
            self.storage.append(new_element)
        else:
            self.storage = [new_element]
        return new_element

    def peek(self):
        if(self.storage):
            return self.storage[0]
        else:
            return None

    def dequeue(self):
        if(self.storage):
            return self.storage.pop(0)
        else:
            return None

# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print q.peek()

# Test dequeue
# Should be 1
print q.dequeue()

# Test enqueue
q.enqueue(4)
# Should be 2
print q.dequeue()
# Should be 3
print q.dequeue()
# Should be 4
print q.dequeue()
q.enqueue(5)
# Should be 5
print q.peek()

Array

Binary Search Tree

Linked List

Extra-Array

Stack

Binary Tree

Recursion

Hash Table

Searching

Sorting

Queue Sandbox

Hash Table

Double Linked List

Graphs

Exotic

Heap