Stacks

learnings

Programming

Stacks

Stacks are an essential data structure in computer science, known for their Last-In-First-Out (LIFO) characteristic. They are used in various applications, including parsing expressions, backtracking problems, depth-first 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 Last-In-First-Out 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, depth-first search in graphs, function call management in programming languages, and more.

representation of an stack

ℹ️

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 array-based stack, but O(n) for a linked list-based stack. On the other hand, the linked list-based stack has no size limit, while the array-based 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 depth-first 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.
Depth-First 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.go


// 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)
}

Linked Lists Queues