Introduction to Stacks, Queues, and Deques (Double Ended Queues)

Stacks

• Analogy: Think of a stack as a stack of pancakes.
  • Only the top pancake can be removed or added.
  • Concept: Last In, First Out (LIFO).
  • Operations:
    • Add (Push): Adding an element to the top.
    • Delete (Pop): Removing an element from the top.
  • Implementation:
    • Use an array with a pointer to the last added element.
    • Initialize the pointer to -1 when the stack is empty.
    • Add Operations: Move pointer and add element.
    • Pop Operations: Move pointer backward and optionally remove element.
    • Ensure the stack does not exceed the array length.

Queues

• Analogy: Think of a queue as a line of people waiting to see an octopus.
  • Concept: First In, First Out (FIFO).
  • Operations:
    • Add (Enqueue): Adding an element at the end.
    • Delete (Dequeue): Removing an element from the front.
  • Implementation:
    • Use an array with two pointers:
      • Front Pointer: Points to the first element.
      • Rear Pointer: Points to the position after the last element.
    • Initialize both pointers to 0 when the queue is empty.
    • Enqueue Operations: Add element and move rear pointer.
    • Dequeue Operations: Remove element and move front pointer.
    • Use a circular array to handle out-of-bound errors.
    • Only store up to n-1 elements where n is the array length.

Deques (Double Ended Queues)

• Concept: Generalized version of the queue.
  • Can add or remove elements from either end.
  • Operations:
    • AddLeft / AddRight: Add elements on the left or right end.
    • RemoveLeft / RemoveRight: Remove elements from the left or right end.
  • Implementation:
    • Similar to queue using a circular array.
    • Can perform all operations in constant time O(1).

Practical Example on AlgoExpert

• Problem: Given a string of brackets (regular, square, curly), write a function to determine if the brackets are balanced.
  • Return true if balanced, false otherwise.
  • Balanced Examples: ([]), {[()]}.
  • Unbalanced Examples: ([), {[}].
  • Solve using O(n) time and O(n) space where n is the length of the string.

Recommendation: Practice these concepts on AlgoExpert.io with referral code: cs dojo.