Understanding the Data Structure Implementation With Example

Data Structure Implementation

Computer science data structures like stacks and FIFO queues have different rules for adding and deleting elements. They can be implemented using a Priority Queue Abstract Data Type (ADT) instead of arrays or linked lists. This approach shows how flexible and abstract ADTs may be built on top of each other to perform certain behaviours.

Stacks

Stacks are linear data structures in Python governed by LIFO. Like a stack of plates, removing the top plate first signifies that the last item was removed first. Important actions for a stack consist of:

Push(e) adds e to the stack.
Pop() returns the top element if the stack is empty.
top(): If the stack is empty, an error is raised. Returns a reference to the top element without deleting it.
is_empty(): Checks stack contents.
To count stack elements, use len().

Applications for stacks include reversing data, matching HTML tags or brackets, and getting rid of recursion.Implementations often use arrays and linked lists.

FIFO Queues

First-In, First-Out (FIFO) queues add things at the rear and remove them at the front. As in a queue, the first person is served. Core functions include:

Adds e to the rear of the line.
If dequeue() returns the first item with an empty queue, an error occurs.
If the queue is empty, an exception occurs. first(): References the initial entry without deleting it.
is_empty(): Checks queue contents.
Len() returns the queue size.

Queues are used in CPU work scheduling and BFS algorithms. Arrays, including circular arrays, and linked lists can be used to implement them.

Priority Queues

An ADT that oversees a group of prioritised items is called a Priority Queue. It permits arbitrary element insertion and the removal of the element with the highest priority. An element is linked to a “key” that indicates its priority when it is inserted. Usually, the one with the highest priority is the one with the minimum key. Among the operations are:

Adds item with value v and key k.
Min() returns the minimum key item’s key-value pair without removal.
The key-value pair of the item with the minimum key is removed and returned by remove min().
Len() and is empty() are comparable to stacks and queues.

A heap data structure, which offers effective (logarithmic time) insertion and removal operations, is frequently used to create priority queues.

Implementing Stack and FIFO Queue using a Priority Queue

A priority queue can be used to implement stacks and FIFO queues, however “one additional integer instance variable” is needed. The fundamental idea is to give each element added to the priority queue a “priority” (key) so that, when items are removed using the remove min (or remove max) operation of the priority queue, the intended LIFO or FIFO order is preserved.

Implementing a Stack (LIFO) with a Priority Queue: The components that are pushed most recently must have the lowest numerical key (highest priority), thus they are remove mined first in order to mimic LIFO behaviour using a min-priority queue. A counter that decreases with each push operation can be used to accomplish this.

Initialisation: Keep a counter, such as next priority, set to either 0 or a significant negative integer.
push(e): Using next priority as its key, add element e to the priority queue. Reduce the next priority. The most recently pushed item will be the minimal key and, as a result, be deleted first by remove min as it will have a smaller (or more negative) priority value.
pop(): Invoke the remove min() function of the priority queue.
top(): Invoke the min() function of the priority queue.
Delegate to the is empty() and len() procedures of the priority queue.

Implementing a FIFO Queue with a Priority Queue: In order to use a min-priority queue to mimic FIFO behaviour, elements that are enqueued first must have the lowest numerical key (highest priority), which means they are remove mined first. A counter that increases with each enqueue action can be used to do this. Using a min-priority queue and Professor Idle’s recommendation to use the queue’s current size as the key for new items also accomplishes FIFO semantics.

Initialisation: Keep a counter set to zero, for example, next priority.
Enqueue(e): Using next priority as its key, add element e to the priority queue. The next priority increment. This guarantees that the item that is enqueued the earliest will have the lowest priority value, making it the minimal key and, consequently, the first item that remove min will remove.
Dequeue(): Invoke the remove min() function of the priority queue.
First(): Invoke the min() function of the priority queue.
Delegate to the is empty() and len() procedures of the priority queue.

Example:

Assume that we have a simple PriorityQueue class with support for len(), add(key, value), remove min(), min(), and is empty(). It give information about such a class, which is frequently implemented with a heap and has O(logn) time for operations like add() and remove in().

import heapq
class PriorityQueueBasedStack:
    def __init__(self):
        self.pq = []  # Priority queue
        self.counter = 0  
    def push(self, item):
        heapq.heappush(self.pq, (-self.counter, item))  
        self.counter += 1
    def pop(self):
        if not self.pq:
            raise IndexError("Pop from empty stack")
        return heapq.heappop(self.pq)[1] 
    def is_empty(self):
        return len(self.pq) == 0

class PriorityQueueBasedQueue:
    def __init__(self):
        self.pq = []  
        self.counter = 0  
    def enqueue(self, item):
        heapq.heappush(self.pq, (self.counter, item))  
        self.counter += 1
    def dequeue(self):
        if not self.pq:
            raise IndexError("Dequeue from empty queue")
        return heapq.heappop(self.pq)[1]  
    def is_empty(self):
        return len(self.pq) == 0

# Testing Stack and Queue implementations
if _name_ == "_main_":
    print("Testing Stack:")
    stack = PriorityQueueBasedStack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    while not stack.is_empty():
        print(stack.pop(), end=" ")  
    
    print("\n\nTesting Queue:")
    queue = PriorityQueueBasedQueue()
    queue.enqueue(10)
    queue.enqueue(20)
    queue.enqueue(30)
    while not queue.is_empty():
        print(queue.dequeue(), end=" ")

Output:

Testing Stack:
30 20 10 
Testing Queue:
10 20 30

Efficiency Considerations

The underlying Priority Queue implementation has a significant impact on how efficient various solutions are. An efficient data structure like a binary heap speeds up the Priority Queue’s add and remove min methods, where ‘n’ is the number of priority queue members. Stack Using Priority Queue and Queue Using Priority Queue’s push/enqueue and pop/dequeue operations also take O(logn) time.

The is empty/len and top/first operations would continue to be O(1).Standard array-based or linked-list implementations complete stack and FIFO queue main operations in O(1) time. Using a priority queue to create a simple stack or FIFO queue is technically accurate and a nice example of ADT composition, but it performs less efficiently than their direct, specialised implementations.

Page Content

Tutorials