Stacks

Introduction to Relations and Representation

• Discussion on representing relations in a two-dimensional way.

• Transition to abstract concepts in data structures.

Stack Data Structure

• Definition of a stack:

  • A stack is a last-in, first-out (LIFO) data structure.

• Distinct operations for stack management:

  • Push: Adds an item onto the stack.

  • Pop: Removes the top item from the stack.

  • When popping from an empty stack, an error (underflow) should be raised.

  • When pushing onto a full stack, an error (overflow) should be indicated.

Representation of Stack

• The state of a stack is determined by the items it contains.

• Example of states:

  • Initially empty stack → Push an element → Stack with one element → Pop to return to empty state.

Stack Implementation Considerations

Error Handling

• Overflow: When attempting to push onto a full stack.

• Underflow: When attempting to pop from an empty stack.

• Signal to the programmer the state of the stack appropriately.

Stack Contents

• A stack can contain various data types (e.g., integers).

• Implementation assumptions may vary based on application.

Operations on Stack

Push Operation

• Procedure:

  • Create a new element with data set to the integer x to be pushed.

  • Set the new element's pointer to the previous top of the stack.

  • Update the stack's top pointer to the new element.

  • If the stack was empty, set the top pointer directly to the new element.

Pop Operation

• Procedure:

  • Check if the stack is empty (underflow condition).

  • Store the data from the current top in a temporary variable.

  • Update the top pointer to the previous element in the stack.

  • Return the data from the temporary variable.

Empty Check

• An empty method can be implemented:

  • Returns true if the top pointer is nil; otherwise returns false.

Bounded and Unbounded Stacks

Unbounded Stack Implementation

• Abstract data structure without explicit pointers like stars or addresses.

• Pointer referencing to a previous element tracks the stack state.

• Use of a distinguished pointer for the top of the stack.

Bounded Stack Implementation

• Representation via an array certainly holds elements within a fixed size (max size).

• Initial state of the stack when no elements are present:

  • The top pointer is set to -1 (indicating no valid locations).

• Methods to determine stack fullness and emptiness:

  • Full: The stack is full if top is equal to max size - 1.

  • Empty: The stack is empty if top is -1.

Push and Pop in Bounded Stack

• Push:

  • Check if the stack is full (if true, signal overflow).

  • Increment top pointer before adding the new element to the array.

• Pop:

  • Retrieve the data from the current index indicated by top and decrement top.

  • Handle the boundary conditions appropriately.

Applications of Stacks

Tower of Hanoi Problem

• A problem involving moving disks between pegs under constraints.

• Utilizes stacks for the transfer process of disks while maintaining ordering.

Call Stack in Program Execution

• A call stack is utilized in imperative programming languages (e.g. C, Java, Python).

• Each function call results in a new stack frame being pushed onto the stack,

  • Contains information such as function variables, state, and execution pointers.

• Function returns cause stack frames to pop off gradually until the stack is empty.

Example: Function Execution Flow

• When a function is called, push its frame onto the call stack:

  • Store relevant execution context (variables, current instruction).

• Return operations pop the stack frame to seamlessly transition back.

Brace Matching Problem in Compilers

• Task of ensuring matching pairs of braces in code.

• Utilize a stack to push each opening brace and pop for each corresponding closing brace:

  • If unmatched braces remain, signal an error.

Control Conditions

• Pushing operation for match opening braces.

• Popping operation for closing braces, maintaining checks to avoid underflow.

• Ensure that types of braces match appropriately when checking.

Pathfinding in a Maze Problem

• Use stacks to explore potential paths through a grid-like structure:

  • Represent cells, potential movement and obstacles.

  • Keep track of visited cells to avoid loops and dead ends using a stack.

Exploring Possible Moves

• At any cell, push possible moves onto the stack and explore sequentially:

  • Maintain logic to remember visited nodes and to backtrack when no options remain.

Conclusion

• Stacks provide a versatile way to manage function calls, data structures, and problem solving in programming.

• Their applications span from basic data structure usage to complex scenarios like recursion and pathfinding.