Stacks
Stacks are an essential data structure in computer science, known for their LastInFirstOut (LIFO) characteristic. They are used in various applications, including parsing expressions, backtracking problems, depthfirst search in graphs, and function call management in programming languages.
graph LR; A[Top: Element 5] B[Element 4] C[Element 3] D[Element 2] E[Bottom: Element 1] A > B B > C C > D D > E
Overview of Stacks

LIFO Principle: The LastInFirstOut principle means that the last element added to the stack will be the first one to be removed. This is analogous to a stack of plates; you can only take the top plate off first.

Basic Operations:
 Push: Adds an item to the top of the stack.
 Pop: Removes the item from the top of the stack.
 Peek (or Top): Returns the top element of the stack without removing it.

Implementation: Stacks can be implemented using arrays or linked lists. The choice of implementation affects the performance of various operations.

Usage: Stacks are used in various applications like parsing expressions, backtracking problems, depthfirst search in graphs, function call management in programming languages, and more.
Stacks are typically implemented using arrays, especially when the size of the stack is known in advance, or when the language supports dynamic arrays (e.g. slices).
The difference between implementing a stack using an array or a linked list lies in the time complexity of certain operations. For example, the push and pop operations are O(1) for an arraybased stack, but O(n) for a linked listbased stack. On the other hand, the linked listbased stack has no size limit, while the arraybased stack is limited by the size of the array.
Common Operations and Their Big O Notation
Operation  Time Complexity  Comments 

Push  O(1)  Adding an item to the top of the stack is a constant time operation. 
Pop  O(1)  Removing the top item from the stack is also a constant time operation. 
Peek/Top  O(1)  Accessing the top element without removing it is constant time. 
Search  O(n)  Searching for an element requires O(n) time as it might involve traversing the entire stack. 
Size  O(1)  Keeping track of the size (number of elements) of the stack can be done in constant time. 
Advantages of Stacks
 Simple and Fast: Basic operations like push and pop are very fast and straightforward to implement.
 Controlled Access: The LIFO property allows for controlled access to elements, making stacks ideal for certain recursive and depthfirst algorithms.
Disadvantages of Stacks
 Limited Access: Only the top element can be accessed directly, which limits the range of operations that can be performed efficiently.
Applications
 Function Calls/Recursion: Managing function calls in programming, especially for recursive functions, where each call adds a new layer to the stack.
 Expression Evaluation: Used in algorithms for parsing and evaluating expressions (e.g., infix to postfix conversion).
 Undo Mechanisms: In software applications (like text editors), where the last action can be undone.
 DepthFirst Search (DFS): In graph algorithms, stacks can be used to implement DFS.
Understanding stacks and their efficient LIFO characteristic is crucial for solving many algorithmic problems, particularly those involving recursion, backtracking, and expression parsing. Their simplicity and efficiency make them a popular choice in various computational tasks.
Code Representation
// Stack represents a stack data structure.
type Stack struct {
items []interface{}
}
// NewStack creates a new empty stack.
func NewStack() *Stack {
return &Stack{}
}
// Push adds an item to the top of the stack.
func (s *Stack) Push(item interface{}) {
s.items = append(s.items, item)
}
// Pop removes and returns the item at the top of the stack.
func (s *Stack) Pop() (interface{}, error) {
if s.IsEmpty() {
return nil, errors.New("stack is empty")
}
index := len(s.items)  1
item := s.items[index]
s.items = s.items[:index] // Remove the item from the slice
return item, nil
}
// Peek returns the item at the top of the stack without removing it.
func (s *Stack) Peek() (interface{}, error) {
if s.IsEmpty() {
return nil, errors.New("stack is empty")
}
return s.items[len(s.items)1], nil
}
// IsEmpty checks if the stack is empty.
func (s *Stack) IsEmpty() bool {
return len(s.items) == 0
}
// Size returns the number of items in the stack.
func (s *Stack) Size() int {
return len(s.items)
}