arrays stacks queues

Arrays are fundamental data structures that store elements of the same data type in contiguous memory locations, accessed via an index (starting at 0 in most languages). Arrays can be one-dimensional (linear list), two-dimensional (matrix/table), or multi-dimensional. Key properties: fixed size (declared at creation), direct access in O(1) time, and efficient memory usage due to sequential storage.

Stacks follow the LIFO (Last In, First Out) principle—the most recently added element is removed first. Essential operations include:

• PUSH(item): Add element to top
• POP(): Remove and return top element
• PEEK(): View top element without removing
• ISEMPTY(): Check if stack is empty
• ISFULL(): Check if stack is at capacity

Top pointer tracks the position of the most recent element. Stack overflow occurs when pushing to a full stack; underflow happens when popping from an empty stack.

Queues implement FIFO (First In, First Out)—elements are added at the rear and removed from the front. Core operations:

• ENQUEUE(item): Add to rear
• DEQUEUE(): Remove from front
• ISEMPTY(), ISFULL()

Circular queues optimize space by wrapping around when reaching array end, using front and rear pointers with modulo arithmetic: rear = (rear + 1) MOD size. This prevents the queue appearing full when space exists at the array's beginning.

Cambridge Definition: A queue is an abstract data type that maintains a sequence where elements are added at one end and removed from the other, following FIFO ordering.

Arrays as Filing Cabinets: Imagine a row of numbered filing drawers (0, 1, 2...). Each drawer (index) holds exactly one document (element). You can instantly access drawer 47 without opening drawers 0-46—this is direct access. However, you can't easily add more drawers; the cabinet's size is fixed.

Stack Applications in Computing:

• Browser History: Clicking 'Back' pops the most recent page from the history stack
• Undo Functionality: Text editors push each change onto a stack; Ctrl+Z pops the last action
• Function Call Stack: When functionA() calls functionB(), the computer pushes A's state onto the stack, executes B, then pops A to resume
• Expression Evaluation: Converting infix notation (3 + 4) to postfix (3 4 +) uses stacks

Real-World Stack Analogy: A stack of dinner plates. You add (push) plates to the top and remove (pop) from the top. Trying to pull a plate from the bottom causes a collapse—that's like accessing elements incorrectly!

Queue Applications:

• Printer Queue: Documents print in submission order (FIFO)
• Customer Service: First caller gets served first
• CPU Task Scheduling: Processes await execution in order
• Breadth-First Search (BFS): Graph traversal uses queues to visit nodes level-by-level

Circular Queue Analogy: A rotating sushi conveyor belt. When the belt reaches the end, it continues from the beginning. Diners (dequeue) take dishes from one position while chefs (enqueue) add new dishes further along. The belt never "wastes" space, unlike a linear queue where dequeued spaces become unusable.

Key Insight: Choice of data structure depends on access pattern. Random access? Use arrays. LIFO processing? Use stacks. FIFO ordering? Use queues.