Stacks: Introduction and Key Operations

Key Concepts

• Linear Data Structure: Stack is a linear data structure.
• Access Type: Limited access (only one end for insertion and deletion).
• Principle: Follows the Last In, First Out (LIFO) or First In, Last Out (FILO) principle.

Real-life Analogies

• CD Stand: CDs can only be added or removed from the top.
• Plates Stack: Plates can only be added or removed from the top.

Stack Properties

• Ordered List: Collection of items ordered by the insertion/deletion rule.
• Single Access Point: Insertion and deletion only at one end.

Logical Representation

• Container: One open end for inserting and deleting data.
• Top: The open end where insertion (push) and deletion (pop) occur.

Basic Operations

1. Push: Insert data into the stack.
   • Syntax: push(data)
   • Stack must contain similar data types.
2. Pop: Remove the topmost data from the stack.
   • Syntax: pop()
   • No arguments needed as it always removes the topmost element.
3. Peek/Top: Return the topmost element without removing it.
   • Syntax: peek() or top()
   • Differs from pop() as it does not remove the element.
4. IsEmpty: Check if the stack is empty.
   • Returns true if empty, false otherwise.
5. IsFull: Check if the stack is full.
   • Returns true if full, false otherwise.

Example

• Capacity of the stack = 5 elements.
• Initial State: top = -1 (empty stack).
• Push 2: top becomes 0, insert 2 at index 0.
• Push 3: top becomes 1, insert 3 at index 1.
• Pop: Removes 3, top becomes 0.
• Pop: Removes 2, top becomes -1 (empty).
• Overflow Condition: Trying to push when stack is full.
• Underflow Condition: Trying to pop when stack is empty.

Memory Allocation

• Static: Using arrays.
• Dynamic: Using linked lists.
• Initial Top: top = -1 indicates an empty stack due to no elements.

Applications

1. String Reversal: Push characters and pop them to reverse the string.
2. Undo Mechanism: Store actions in a stack for reversing them.
3. Recursion: Use stack to store intermediate results in function calls.
4. Parentheses Balancing: Ensure every opening parenthesis has a closing match.
5. Expression Conversion: Infix to postfix or prefix using stack.
6. Algorithm Use: In topological sorting, DFS, Tower of Hanoi, and more.
7. Postfix Evaluation: Evaluate expressions using stack operations.

Conclusion

• Understanding the logical representation and key operations of stacks.
• Next step: Implement stack using arrays and linked lists.
• Discuss practical coding of push and pop operations.

Future Topics

• Coding of stack operations.
• Detailed applications with examples.