Data Structures: Stack Operations

Data Structures

• This lecture covers data structures, specifically stacks.
• Different types of data structures include hash tables, trees, stacks, linked lists, sets, and graphs.
• Queues, sets, linked lists, and hash tables are also mentioned as data structures.
• The slide deck focuses on stacks, their operations, implementation, and applications.

Stacks

• A stack is an Abstract Data Type (ADT).
• Stacks behave like real-world stacks, like a deck of cards or a pile of plates.
• Operations are performed at one end only.
• LIFO (Last-In, First-Out) data structure.
• The top element is the last element added to the stack.
• The element added last is always removed first.
• Push operation: Inserting an element onto the stack.
• Pop operation: Removing an element from the stack.
• Peek operation: Accessing the top element without removing it.
• Implementing stacks using arrays restricts the number of elements.
• Linked lists provide unlimited storage.

Stack Representation

• Depicts a stack and its operations (push and pop).
• Shows the LIFO nature of a stack.

Stack Implementation using Array

• Steps for creating an empty stack using an array:
  • Include header files.
  • Define a constant 'SIZE'.
  • Declare stack functions.
  • Create a one-dimensional array stack[SIZE].
  • Define an integer variable top and initialize it to -1.
  • In the main method, display a menu with operations and make function calls.

Stack Operations using Array

• Push: Checks if the stack is full. If full, displays an error message. Otherwise, increments top and stores the value.
• Pop: Checks if the stack is empty. If empty, displays an error message. Otherwise, removes the top element and decrements top.
• Peek: Returns the top element without removing it.
• IsFull: Returns true if the stack is full, false otherwise.
• IsEmpty: Returns true if the stack is empty, false otherwise.

Stack Implementation using Linked List

• Stacks can be implemented using linked lists for unlimited storage.
• Every new element in a linked list stack is inserted as the top element.
• Removing an element involves removing the top node.

Push Operation (Linked List)

• Steps for inserting a new node into the stack:
  • Create a new node with the given value.
  • Check if the stack is empty (top == NULL).
  • If empty, set newNode->next = NULL.
  • If not empty, set newNode->next = top.
  • Set top = newNode.

Pop Operation (Linked List)

• Steps for deleting a node from the stack:
  • Check if the stack is empty (top == NULL).
  • If empty, display an error message and terminate.
  • Otherwise, define a node pointer temp and set it to top.
  • Set top = top->next.
  • Delete temp (e.g., free(temp)).

Display Operation (Linked List)

• Steps for displaying stack elements:
  • Check if the stack is empty.
  • If empty, display "Stack is empty".
  • If not empty, define a node pointer temp and initialize it with top.
  • Display temp->data, move to the next node until temp->next == NULL.

Multiple Stack

• Multiple stacks can be implemented in a single array to avoid memory wastage.
• Stacks can grow from different ends of an array.

Applications of Stacks

• Conversion of an infix expression into postfix.
• Evaluation of a postfix expression.
• Conversion of an infix expression into a prefix expression.
• Evaluation of a prefix expression.
• Reversing a list.
• Parentheses checker.
• Recursion.
• Tower of Hanoi.

Expressions

• Expressions are a set of symbols used for calculations and conditions in programming.
• An expression is a collection of operators and operands.

Expression Types

• Infix expressions: Operators are between operands (e.g., a + b).
• Postfix expressions: Operators are after operands (e.g., ab+).
• Prefix expressions: Operators are before operands (e.g., +ab).

Precedence

• Operator precedence determines which operator is evaluated first when multiple operators exist in an expression.
• Multiplication and division often have higher precedence than addition and subtraction.

Associativity

• Associativity determines the order of evaluation for operators with the same precedence.
• Operators like addition and subtraction are typically left-associative (from left to right).

Expression Conversion (Infix to Postfix/Prefix)

• Methods for converting infix expressions to postfix or prefix forms using stacks.

Postfix Expression Evaluation

• Algorithm for evaluating postfix expressions with operators and operands.

Prefix Expression Evaluation

• Algorithm for evaluating prefix expressions, similar to the postfix method.

Infix, Postfix, and Prefix Conversions

• Procedures for converting between these forms of expressions.

Reversing a List

• Using a stack to reverse a list of numbers stored in an array.

Implementing Parentheses Checker

• Using a stack to check the validity of parentheses in an expression.

Recursion

• Functions calling themselves to solve smaller problems.
• Includes base and recursive cases.

Tower of Hanoi

• A classic example of recursive problem-solving.

Advantages of Recursion

• Recursive code is often more concise and readable.
• It often directly mirrors the problem's logic.

Drawbacks of Recursion

• Can be less efficient in terms of memory and time compared to iterative solutions.
• Stack overflow could occur if recursion depth is too high.

Test your knowledge on stack operations, including push and pop methods, conditions for element insertion, and differences in implementation using linked lists versus arrays. This quiz covers fundamental concepts necessary for understanding stack functionality in programming.