The LIFO (Last-In, First-Out) property is fundamental to stack operations because it ensures that the most recent item added to the stack is the first to be removed. This behaviour is critical in applications such as the call stack in programming, where functions are nested within each other. When a function calls another, the calling function is paused and pushed onto the stack. Once the called function finishes, control must return to the last paused function—hence the need for LIFO. Similarly, in undo operations like those in text editors, the last action performed by the user must be the first one reversed. The stack ensures that the system always undoes the most recent action before earlier ones. Without LIFO, actions would be undone in the wrong order, causing unexpected and incorrect results. This structure provides a controlled and predictable reversal process, which is what makes stacks uniquely suited for such tasks.

In array-based stacks, memory is allocated as a single block of fixed size at the time the stack is created. This means that the memory usage is predictable, and the memory addresses are contiguous, which allows for faster access due to caching and direct indexing. However, this approach can lead to inefficiencies if the actual number of elements used is much smaller than the allocated size, resulting in wasted memory. In contrast, linked list-based stacks allocate memory dynamically, one node at a time, as elements are added. Each node contains both the data and a pointer to the next node. This allows the stack to grow or shrink exactly as needed, conserving memory. However, this comes with additional overhead: each element requires extra space for the pointer, and the nodes are scattered in memory, which can slow down access due to non-contiguous allocation. Linked list stacks are ideal in scenarios with highly variable or unpredictable stack sizes.

Sentinel values are special constants used to represent boundary or error conditions in data structures like stacks. In stack implementations, they are often used to indicate empty or full conditions without needing additional boolean checks. For example, a top value of -1 is commonly used in array-based stacks to signify that the stack is currently empty. Similarly, a null value can represent an empty stack in linked list implementations. Sentinel values can also be pushed onto a stack deliberately to mark the bottom of a stack or to serve as a stopping condition during traversal or processing. For instance, a parser might use a sentinel character like # to signal the end of an expression. While sentinel values simplify implementation and reduce the need for complex condition checking, they must be chosen carefully to avoid conflict with legitimate data values. They are particularly useful in low-level or performance-sensitive applications where control structures must be kept minimal.

Yes, it is possible to implement multiple stacks using a single array, a technique known as stack partitioning or multi-stack implementation. One common method is to divide the array into fixed sections, each assigned to a different stack. For example, two stacks can grow towards each other from opposite ends of the array. Stack 1 grows from the start of the array towards the end, and Stack 2 grows from the end towards the start. Each stack maintains its own top pointer. This arrangement maximises space usage since the stacks only collide when the entire array is full. Another, more flexible method is to use dynamic allocation and metadata arrays to track the top and next pointers, which is more complex but allows multiple stacks of varying sizes to share the array. This is useful in systems with limited memory, such as embedded devices, where efficient memory use is critical. However, careful management is required to avoid overflow and pointer collisions.

In recursive algorithms, the system’s call stack automatically manages the sequence of function calls and returns. Each recursive call pushes a new stack frame onto the call stack, storing the function’s local state and return address. When a base case is reached, the stack begins to unwind as each function call returns. This natural use of the stack makes recursion elegant and concise, especially for problems like tree traversal, factorial computation, or backtracking. However, recursion has the risk of stack overflow if the recursion depth is too large, as each call consumes additional stack space. In iterative algorithms, the programmer explicitly manages the stack (usually with a data structure), using loops and manual push/pop operations to simulate recursion. This approach gives more control over memory usage and can often be optimised to avoid stack overflow. Choosing between recursion and iteration depends on the problem’s nature, memory constraints, and whether the overhead of recursion is acceptable or needs to be avoided.