14. DSA with C++ - Stack data structure

Stack

A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. It is a collection of elements in which the last element inserted is the first one to be removed. A stack has the following properties:

1. LIFO Order: The most significant property of a stack is the LIFO order. The last element inserted into the stack is the first one to be removed. It follows the "last in, first out" behavior.
2. Push Operation: The push operation adds an element to the top of the stack. It inserts an element onto the stack.
3. Pop Operation: The pop operation removes the top element from the stack. It deletes the element that was most recently added.
4. Peek/Top Operation: The peek operation returns the top element of the stack without removing it. It allows you to access the element at the top of the stack without modifying the stack itself.
5. Stack Size: The stack can have a limited size or be implemented with dynamic memory allocation, allowing it to grow or shrink as needed.

Stacks can be implemented using various data structures such as arrays or linked lists. The choice of implementation depends on the requirements and constraints of the problem at hand.

Some common applications of stacks include expression evaluation, function call stack in programming languages, backtracking algorithms, undo/redo functionality, and parsing operations.

Stacks are widely used in computer science and have efficient time complexities for their operations:

- Push operation: O(1)
- Pop operation: O(1)
- Peek/Top operation: O(1)

Overall, the properties and operations of a stack make it a useful data structure in situations where the order of element access and removal follows the LIFO principle.