Stack and Queue || Python || Data Structures and Algorithms
Understanding Stacks and Queues: Applications and Implementations
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.
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.
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
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
