Stacks & Queues in Python

Stacks

A stack is a linear data structure with two main operations: push and pop. Push: append an element on top of the stack. Pop: remove an element from the top of the stack. Stacks are referred to as a LIFO ( Last in First out) as it supports fast last-in, first-out (LIFO) semantics for inserts and deletes. Unlike lists or arrays, stacks typically don’t allow for random access to the objects they contain

Performance-wise, a proper stack implementation is expected to take O(1) time for insert and delete operations.

When are stacks useful?

1. Tracing back to access previous elements/operations

For example, undo operations in editors are like popping a code change that was just pushed in the stack of edit history. Similarly, back operations in browsers are like popping a site visit that was just pushed in the stack of browser history.

2. Matching recursive elements/operations

For example, a stack comes in handy when checking if an operation “(5 + 6) + ((7 * 9) + 9) + 10)” is a valid syntax Another use case is to keep track of recursions in a code. Each call to the recursive function is pushed onto the stack so that it can be executed once lower recursions are done with their execution.

Stacks have a wide range of uses in algorithms, for example in language parsing and runtime memory management (“call stack”). A short algorithm using a stack is depth-first search (DFS) on a tree or graph data structure.

class Stack:
    def __init__(self):
        self.stack = []    
    
    def pop(self):
        if self.is_empty():
            return None
        else:
            return self.stack.pop()    
    
    def push(self,val):
        return self.stack.append(val)    
    def top(self):
        if self.is_empty():
            return None
        else:
            return self.stack[-1]    
    
    def size(self):
        return len(self.stack)    
    def is_empty(self):
        return self.size() == 0 stacks useful?

Queues

A queue is a data structure with two main operations: enqueue and dequeue. enqueue: append an element to the tail of the queue dequeue: remove an element from the head of the queue. Queues are referred to as a FIFO (First in First out) data structure. Unlike lists or arrays, queues typically don’t allow for random access to the objects they contain.

Performance-wise, a proper queue implementation is expected to take O(1) time for insert and delete operations.

When are queues useful?

Queues are used whenever you want to process things one at a time as they come in. Some examples are, uploading a bunch of images, printing multiple documents, and processing thousands of requests to a web server.

Queues have a wide range of applications in algorithms and to solve scheduling, as well as parallel programming problems. A short algorithm using a queue is breadth-first search (BFS) on a tree or graph data structure.

Scheduling algorithms often use priority queues internally. These are specialized queues: instead of retrieving the next element by insertion time, a priority queue retrieves the highest-priority element. The priority of individual elements is decided by the queue based on the ordering applied to their keys.

A regular queue, however, won’t re-order the items it carries. You get what you put in, and in exactly that order

class Queue:
    def __init__(self):
        self.queue = []    
 
    def enqueue(self,val):
        self.queue.insert(0,val)    
    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop()    
    def size(self):
        return len(self.queue)    
    def is_empty(self):
        return self.size() == 0

Queues are similar to stacks and the difference between them is in removing items. With a queue you remove the item least recently added (first-in, first-out or FIFO); and with a stack, you remove the item most recently added (last-in, first-out or LIFO).