CS Fundamentals: Stacks

CS Fundamentals: Stacks

• Stacks are linear data structures following the LIFO (Last-In, First-Out) principle.
• Key operations include:
  • Push: Adds an element to the top.
  • Pop: Removes and returns the top element.
  • Peek/Top: Returns the top element without removing it.
  • isEmpty: Checks if the stack is empty.
• Python example:

  stack = []
  stack.append(10)  # Push 10
  stack.append(20)  # Push 20
  print(stack.pop())  # Pop and print 20
  print(stack[-1])  # Peek at the top element (10)
  

• Applications:
  • Undo functionality in text editors.
  • Recursion management (function calls).
  • Reversing data.
• Balanced Parentheses Example
  • Stacks help check for balanced parentheses in expressions.
    • Algorithm:
      • Traverse the expression.
      • Push opening parentheses onto the stack.
      • For each closing parenthesis, pop from the stack and check matching.
      • Stack should be empty at the end for balanced expression.
  • Python Code Example (checking for balanced parentheses):

  def is_balanced(expression):
      stack = []
      for char in expression:
          if char in "({[":
              stack.append(char)
          elif char in ")}]":
              if not stack or not matches(stack.pop(), char):
                  return False
      return len(stack) == 0
  
  def matches(opening, closing):
      pairs = {')': '(', '}': '{', ']': '['}
      return pairs[closing] == opening
  

Queues

• Queues are linear data structures based on the FIFO (First-In, First-Out) principle.
• Different types: simple, circular, priority, deque (double-ended queue).
• Key operations:
  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes and returns the element from the front.
• Practical Use Cases and code examples will be included when the full 75,000 write-up is complete.

Arrays

• Arrays are linear data structures storing elements of the same data type.
• Types: 1D, 2D, multidimensional.
• Operations:
  • Traversal: Accessing each element.
  • Insertion: Adding elements.
  • Deletion: Removing elements.
  • Searching: Finding an element.
• Examples for sorting and searching algorithms will be explored in the full write-up.
• Practical Applications in data representation
  • Matrix operations
  • Prefix sums

Control Statements

• Control Statements allow for conditional execution of code blocks.
• Common types:
  • if, if-else, nested conditions (decision making.)
  • switch-case statements (alternatives to chained if-else; Python does not have switch-case directly so examples will be of if-elif-else.)
• Real-world examples: calculators and other computing applications

Loops

• Loops execute a block of code repeatedly.
• Types: for, while , do-while.
• Nested loops have an inner loop within an outer loop.
• Examples will be demonstrated in Python, C++, and JavaScript in the full document.

Return Statements

• Return statements are used in functions; they send a value back to where the function was called.
• Important for functions and recursion, allowing functions to produce results and use those results in further calculations.
• Syntax and examples will be given in the detailed document in multiple languages.

Strings

• Strings are sequences of characters.
• String operations: Concatenation, substring extraction, manipulation.
• Examples: reversing strings, checking for palindromes.

Additional Notes

• Data structures like stacks, queues, and arrays are fundamental to computer science.
• Understanding these data structures and their applications is extremely important in developing and utilizing programs.