A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, which means that the last element added to the stack is the first one to be removed. It can be thought of as a stack of objects, where you can only access or modify the topmost element.

Usage

• Function Call Management: When a function is called, its context (including variables and return address) is pushed onto the stack. When the function completes execution, its context is popped from the stack, allowing the program to return to the previous point of execution.
• Expression Evaluation: Stacks are handy for evaluating arithmetic expressions with parentheses or nested operations. By pushing operators and operands onto the stack in a Last-In-First-Out (LIFO) manner, stacks facilitate proper evaluation and precedence handling.
• Undo/Redo Functionality: Each action performed is stored as a state on the stack, allowing users to go back and forth through the sequence of actions.
• Browser History: Stacks are used to maintain the back button functionality in web browsers. As users navigate through web pages, each visited page is pushed onto the stack. Pressing the back button pops the top page from the stack, allowing users to revisit previous pages.
• Depth-First Search (DFS): They help keep track of visited nodes and explore the graph's depth by pushing adjacent nodes onto the stack for further exploration.
• Balancing Delimiters: Stacks are used to check and balance delimiters like parentheses, brackets, or braces in programming languages. Opening delimiters are pushed onto the stack, and when a closing delimiter is encountered, the stack is checked to ensure correct nesting and balance.

Operations

Main operations

• Push: Adds an element to the top of the stack
• Pop: Removes the top element from the stack

Additional operations

• Peek: Access the top element of the stack without removing it
• Size: Returns the number of elements in the stack
• Clear: Removes all elements from the stack

Push Operation

Pseudo Code

class
    private stack: array
    
    procedure push(item)
        if stack is full then
            return null
        else
            stack.add(item)
        end if
    end procedure
end class

Complexity

• Time: $O(1)$
• Space: $O(1)$

Pop Operation

Pseudo Code

class
    private stack: array
    
    procedure pop()
        if stack is empty then
            return null
        else
            return remove stack[top]
        end if
    end procedure
end class

Complexity

• Time: $O(1)$
• Space: $O(1)$

Peek Operation

Pseudo Code

class
    private stack: array
    
    procedure peek()
        if stack is empty then
            return null
        else
            return stack[top]
        end if
    end procedure
end class

Complexity

• Time: $O(1)$
• Space: $O(1)$

Size Operation

Pseudo Code

class
    private stack: array
    
    procedure size()
        return stack.length()
    end procedure
end class

Complexity

• Time: $O(1)$
• Space: $O(1)$

Clear Operation

Pseudo Code

class
    private stack: array
    
    function clearStack():
        while stack is not empty do:
            pop an element from the stack
        end while
    end function
end class

Complexity

• Time: $O(n)$
• Space: $O(1)$

Pros and Cons

Pros:

• LIFO Order: This allows for easy and efficient access to the most recently added elements. This is particularly useful in scenarios where the order of operations or data is significant
• Simple Implementation: Stacks are relatively simple to implement and understand
• Efficient Push and Pop Operations: This makes stacks suitable for applications requiring frequent push and pop operations.

Cons:

• Limited Access: Elements can only be accessed from the top of the stack, and direct access to other elements requires removing all elements above them.
• Lack of Random Access: To access elements lower in the stack, all the elements above them must be removed.
• Size Limitations: If the stack exceeds its maximum capacity, additional memory allocation or resizing may be required.
• Lack of Sorting: To sort elements in a stack, they need to be popped out, stored externally, sorted using other algorithms, and then pushed back onto the stack.