Easy Notes Of Data structure using C unit-4 @Computer Diploma

Description

4.1 Introduction to Stack:

This section introduces the stack as a crucial linear data structure.

• Definition: A stack is an ordered list in which insertion and deletion of elements are done at only one end, called the Top of the Stack (TOS). This strict access pattern enforces the Last-In, First-Out (LIFO) principle, meaning the element that was most recently added is the first one to be removed.
• Stack as an Abstract Data Type (ADT): An ADT defines a data type by its behavior from a user’s point of view, independent of its implementation. As an ADT, the stack is defined by a set of data (the elements) and a set of operations that can be performed on them.
• Operations on Stack – (Push, Pop):
  • Push: The operation of adding a new element to the top of the stack.
  • Pop: The operation of removing the topmost element from the stack and returning its value.
  • (Note: Other common auxiliary operations often discussed include Peek/Top, which returns the top element without removing it, and isEmpty, which checks if the stack has any elements.)
• Stack Operation Conditions: These are error conditions that must be checked before performing the primary operations:
  • Stack Full / Stack Overflow: A condition that occurs when an attempt is made to Push a new element onto a stack that has already reached its maximum capacity. This is common in fixed-size implementations like arrays.
  • Stack Empty / Stack Underflow: A condition that occurs when an attempt is made to Pop or Peek an element from a stack that currently contains no elements.

4.2 Stack Implementation:

This section explores the practical ways to build and manage a stack in memory, focusing on both static and dynamic approaches.

• Stack Implementation using Array (Static Implementation):
  • The stack is implemented using a fixed-size linear array.
  • A special variable, typically named top, is used to keep track of the index of the top element. Initially, top is set to a value like -1 to signify an empty stack.
  • Push involves incrementing the top index and placing the new element at array[top]. An overflow check (top == MAX\_SIZE - 1) must be performed.
  • Pop involves retrieving the element at array[top] and then decrementing the top index. An underflow check (top == -1) must be performed.
  • Advantage: Simple to implement, fast access. Disadvantage: Fixed size, leading to potential stack overflow and memory wastage.
• Representation and Implementation using Linked List (Dynamic Implementation):
  • The stack is implemented using a singly linked list.
  • The Top of the Stack is typically represented by the head of the linked list.
  • Push involves creating a new node and setting it as the new head (top) of the list, pointing its next pointer to the old head.
  • Pop involves retrieving the data from the head node, moving the head pointer to the next node in the list, and then freeing the memory of the original head node.
  • Advantage: Dynamic size, allowing the stack to grow or shrink as needed (limited only by system memory). Disadvantage: Requires more memory per element (for the pointer) and is slightly more complex to implement.

4.3 Applications of Stack:

This section delves into the practical and theoretical uses of the stack data structure in solving various computing problems.

• Reversing a List (or String/Data): Due to the LIFO property, a stack is naturally used to reverse the order of elements. Elements are pushed onto the stack in their original order, and when popped, they emerge in the reverse order.
• Polish Notations (Prefix, Infix, Postfix): Stacks are fundamental in handling mathematical expressions.
  • Infix Notation: The standard mathematical notation (e.g., $A+B$).
  • Postfix Notation (Reverse Polish Notation): Operators follow the operands (e.g., $AB+$).
  • Prefix Notation (Polish Notation): Operators precede the operands (e.g., $+AB$).
• Conversion of Infix to Postfix Expression: Stacks are used to manage the operators and parenthesis during the conversion process. The algorithm follows precedence rules and operator associativity, using the stack to temporarily hold operators and reorder them correctly to produce the postfix form.
• Evaluation of Postfix Expression: Stacks are used to simplify the process of calculating the result of an expression already in postfix notation. Operands are pushed onto the stack, and when an operator is encountered, the required number of operands are popped, the operation is performed, and the result is pushed back onto the stack.

4.4 Recursion:

This section introduces Recursion, a powerful programming technique often closely associated with the stack due to its underlying implementation mechanism.

• Definition: Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. A function is said to be recursive if it calls itself.
  • A recursive function must have one or more base cases (which stop the recursion) and a recursive step (which makes the call to itself with a reduced problem size).
  • Relationship to Stack: When a function calls itself (or any function calls another), the operating system uses an internal Call Stack to manage the execution flow. The current state (local variables, return address) of each recursive call is pushed onto this stack. When a base case is reached, the function calls begin to return, and their stored states are popped off the call stack in LIFO order.
• Applications: Recursion is used to elegantly solve problems that exhibit an inherent recursive structure.
  • Mathematical Functions: Factorial calculation, Fibonacci series.
  • Data Structure Traversals: Tree traversals (In-order, Pre-order, Post-order).
  • Sorting Algorithms: Merge Sort, Quick Sort.
  • Backtracking Problems: Eight Queens problem, Maze solving.