Stacks and Queues

Stack (LIFO - Last-In, First-Out)

A stack is a linear data structure that follows a particular order in which operations are performed. The order is LIFO (Last-In, First-Out). Think of a stack of plates: you add a new plate to the top, and you also remove a plate from the top.

Core Operations:

• push(element): Adds an element to the top of the stack. (O(1))
• pop(): Removes and returns the top element of the stack. (O(1))
• peek() or top(): Returns the top element without removing it. (O(1))
• isEmpty(): Checks if the stack is empty. (O(1))

Applications: Function call management (the call stack), undo/redo functionality, expression evaluation (e.g., converting infix to postfix), and backtracking algorithms (DFS).

Queue (FIFO - First-In, First-Out)

A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. This is like a checkout line at a store: the first person to get in line is the first person to be served.

Core Operations:

• enqueue(element): Adds an element to the rear (end) of the queue. (O(1))
• dequeue(): Removes and returns the element from the front of the queue. (O(1))
• front(): Returns the front element without removing it. (O(1))
• isEmpty(): Checks if the queue is empty. (O(1))

Applications: Task scheduling (e.g., in operating systems), breadth-first search (BFS) in graphs, handling requests on a single shared resource (like a printer), and message processing systems.

Implementation

Both stacks and queues can be implemented using either dynamic arrays (like C++ std::vector or Python list) or linked lists. In competitive programming, standard library implementations are almost always used.

• C++: std::stack, std::queue.
• Python: list can be used as a stack (append for push, pop for pop). For a queue, use collections.deque for efficient O(1) appends and pops from both ends.
• Java: Stack class, and Queue interface (commonly implemented with LinkedList).