Stack and Queue || Python || Data Structures and Algorithms

#learning #python #programming #algorithms

Stack

Stack - It is a storage container which supports retrieval by last-in, first-out ( LIFO) order. Stacks are probably the right container to use when retrieval order doesn’t matter at all, such as when processing batch jobs.

For example, consider a stack of plates used in cafeterias: the order in which plates are removed from the stack is the reverse of the order in which they were added, as only the top plate is accessible.

The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.

Push (x,s): Insert item x at the top of stack s.

Pop(s) : Return (and remove) the top item of stack s.

Food inserted into my refrigerator usually exits the same way, despite the incentive of expiration dates. Algorithmically, LIFO tends to happen in the course of executing recursive algorithms.

Applications of Stack -

Function calls: Used to manage function execution and recursion.
Undo operations: Tracks changes in editors for "Undo/Redo."
Browser history: Stores visited pages for backtracking.
Expression parsing: Evaluates and converts mathematical expressions.
Syntax validation: Matches parentheses or tags in code.
Memory management: Manages call stacks during program execution.
DFS: Implements Depth-First Search in graph algorithms.

Implement Stack Using Array -

push() - Insert an element into the stack
pop() - Remove an element from the stack
top() - Returns the top element of the stack.
isEmpty() - Returns true if the stack is empty else false.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

Queue

Queue - It is a storage container which supports retrieval by first-in, first-out (FIFO) order. We call the INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE. Like the stack operation POP, DEQUEUE takes no element argument. Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is predefined.

Enqueue(x,q): Insert item x at the back of queue q.

Dequeue(q): Return (and remove) the front item from queue q.

The queue has a head and a tail.

When an element is enqueued, it takes its place at the tail of the queue, just as a newly arriving customer takes a place at the end of the line.
The element dequeued is always the one at the head of the queue, like the customer at the head of the line, who has waited the longest.

Applications of Queue -

Task scheduling: Manages CPU processes and jobs in order.
BFS: Implements Breadth-First Search in graphs.
Print queues: Handles print jobs sequentially.
Network routing: Buffers data packets for transmission.
Call centers: Manages customer calls in waiting order.
Streaming: Buffers video or audio streams in real-time.
Input events: Processes keyboard and mouse inputs in GUI systems.

Implement Queue Using Array-

enqueue() – Insertion of elements to the queue.
dequeue() – Removal of elements from the queue.
peek() or front()- Acquires the data element available at the front node of the queue without deleting it.
isEmpty() – Checks if the queue is empty.

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

Implement Queue using Stacks -

push(x) - Move all elements from stack1 to stack 2 to reverse their order and then and again move all elements back from stack2 to stack 1.
pop() - Removes the element from the front of the queue and returns it
peek() - Returns the element at the front of the queue
empty() - Returns true if the queue is empty, false otherwise

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

Implement Stack using Queues -

push(x) - Add new element to second queue, then move all elements from queue 1 to queue 2 to maintain stack order (LIFO) and Swap the queues.
pop() - Removes the element on the top of the stack and returns it
peek or top() - Returns the element at the front of the queue
empty() - Returns true if the queue is empty, false otherwise

class MyStack:

    def __init__(self):
        # Initialize two queues for stack operations
        self.queue1 = [] # Main queue to hold elements
        self.queue2 = [] # Temporary queue used during push

    # Pushes element x to the top of the stack
    def push(self, x: int) -> None:

        # Add new element to second queue
        self.queue2.append(x)

        # Move all elements from queue 1 to queue 2 to maintain stack order (LIFO)
        while len(self.queue1) > 0:
            self.queue2.append(self.queue1.pop(0))

        # Swap the queues
        self.queue1, self.queue2 = self.queue2, self.queue1

    # Removes the element on the top of the stack and returns it
    def pop(self) -> int:
        return self.queue1.pop(0)

    # Returns the element on the top of the stack
    def top(self) -> int:
        return self.queue1[0]

    # Returns true if the stack is empty, false otherwise.
    def empty(self) -> bool:
        return len(self.queue1) == 0