Stack: Definition, Operations, and Postfix Evaluation

1. What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means the element inserted last is the first one to be removed.

A stack can be visualized as a pile of plates: you add a plate on top and also remove from the top.

Key characteristics:

• All insertions and deletions occur at one end called the TOP
• It is an ordered collection of elements
• It can be implemented using arrays or linked lists

2. Stack Operations

The following are the primary operations performed on a stack:

a) PUSH (Insertion)

Adds an element to the top of the stack.

Algorithm: PUSH(STACK, TOP, MAXSIZE, ITEM)

1. If TOP = MAXSIZE - 1, then:
      Print "Stack Overflow" and EXIT
2. Set TOP = TOP + 1
3. Set STACK[TOP] = ITEM
4. Return

b) POP (Deletion)

Removes and returns the top element from the stack.

Algorithm: POP(STACK, TOP, ITEM)

1. If TOP = -1, then:
      Print "Stack Underflow" and EXIT
2. Set ITEM = STACK[TOP]
3. Set TOP = TOP - 1
4. Return ITEM

c) PEEK / TOP

Returns the top element without removing it.

1. If TOP = -1, then:
      Print "Stack is Empty" and EXIT
2. Return STACK[TOP]

d) isEmpty

Checks whether the stack is empty.

1. If TOP = -1, return TRUE
2. Else return FALSE

e) isFull

Checks whether the stack is full.

1. If TOP = MAXSIZE - 1, return TRUE
2. Else return FALSE

3. Postfix Expression Evaluation

What is a Postfix Expression?

In postfix notation (also called Reverse Polish Notation), the operator comes after its operands.

• Infix: A + B
• Postfix: A B +

Postfix expressions do not require parentheses and are easy to evaluate using a stack.

Algorithm to Evaluate Postfix Expression

Input: A postfix expression string
Output: The evaluated result

Algorithm EVALUATE_POSTFIX(expression):

1. Create an empty stack S
2. Scan the expression from LEFT to RIGHT, one token at a time
3. For each token:
      a. If token is an OPERAND (number):
            PUSH it onto stack S
      b. If token is an OPERATOR (+, -, *, /):
            i.  POP the top element, call it OPERAND2
            ii. POP the next top element, call it OPERAND1
            iii.Apply the operator: RESULT = OPERAND1 operator OPERAND2
            iv. PUSH RESULT onto stack S
4. After scanning all tokens:
      POP and return the final value from stack S
      (This is the result of the expression)

Note: The order matters: first popped value is the right operand, second popped value is the left operand.

Worked Example

Evaluate postfix expression: 5 3 + 2 * 4 -

Final Result = 12

Another Example

Evaluate: 6 2 3 + - 3 8 2 / + *

Final Result = 7

Summary

Every basic stack operation touches only the top of the stack, so each of them runs in constant time. Postfix evaluation scans the expression once and performs a constant amount of work per token, so it is O(n) in time and O(n) in space for the stack in the worst case, where n is the number of tokens.

Conclusion

A stack is a linear list restricted to LIFO access through PUSH and POP at a single end, with PEEK, isEmpty and isFull as supporting operations. Its usefulness is best seen in expression evaluation: because postfix notation carries no parentheses and no precedence, a single left to right scan with one stack is enough, pushing every operand and replacing the top two operands by the result whenever an operator appears. The value left on the stack at the end of the scan is the value of the expression.

Applications of Binary Tree

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees have numerous important applications in computer science.

Applications of Binary Tree

1. Binary Search Tree (BST)

• A binary tree is used to implement BST, where the left subtree contains nodes with values less than the root and the right subtree contains nodes with values greater than the root.
• Used for efficient searching, insertion, and deletion operations with O(log n) average time complexity.
• Example: Dictionary implementations, symbol tables.

2. Expression Tree

• Binary trees are used to represent arithmetic expressions.
• Leaf nodes contain operands (numbers/variables) and internal nodes contain operators (+, -, *, /).
• Used in compilers to parse and evaluate expressions.
• Example:

      *
     / \
    +   5
   / \
  2   3
  

  Represents: (2 + 3) * 5

3. Heap (Priority Queue)

• A binary heap is a complete binary tree used to implement priority queues.
• Used in heap sort algorithm and scheduling algorithms.
• Min-heap: parent is smaller than children.
• Max-heap: parent is larger than children.

4. Huffman Coding Tree

• Used in data compression algorithms (e.g., ZIP, JPEG).
• A binary tree is built where frequently occurring characters are placed closer to the root (shorter codes) and less frequent characters are placed deeper (longer codes).
• This minimizes the total number of bits required to encode data.

5. Decision Tree

• Used in Artificial Intelligence and Machine Learning for classification and decision-making.
• Each internal node represents a condition/test, each branch represents an outcome, and each leaf node represents a decision/result.
• Also used in game trees (e.g., chess, tic-tac-toe).

6. Tree Traversal in File Systems

• Binary trees model hierarchical file systems and directory structures.
• Traversal techniques (Inorder, Preorder, Postorder) are used to search, list, or process files and directories.

Summary Table

Binary trees are fundamental data structures that form the basis of many efficient algorithms and real-world systems.

Spanning Tree and Minimum Spanning Tree

Spanning Tree

A spanning tree of a connected, undirected graph G = (V, E) is a subgraph that:

• Includes all vertices of the graph
• Is a tree (connected and acyclic)
• Has exactly |V| - 1 edges

A graph with n vertices will have a spanning tree with exactly n - 1 edges.

Minimum Spanning Tree (MST)

A Minimum Spanning Tree is a spanning tree of a weighted, connected, undirected graph in which the total sum of edge weights is minimum among all possible spanning trees.

Key Properties:

• Contains all V vertices and exactly V - 1 edges
• No cycles are present
• The total edge weight is minimized

Example

Consider the following weighted graph with 4 vertices:

        2
   A -------- B
   |  \       |
  6|    \ 3   | 4
   |      \   |
   D -------- C
        5

Edges and weights:

Finding MST (using Kruskal's approach - pick minimum weight edges without forming cycle):

MST Edges: A-B, A-C, D-C

        2
   A -------- B
    \        
   3 \       
      \      
       C -------- D
            5

Total MST Weight = 2 + 3 + 5 = 10

This is the minimum possible weight to connect all 4 vertices, using exactly 4 - 1 = 3 edges.

Common Algorithms to find MST:

• Kruskal's Algorithm - sorts edges by weight and adds them greedily
• Prim's Algorithm - grows the MST one vertex at a time from a starting vertex

Short Notes

a.) Doubly Circular Linked List

A Doubly Circular Linked List is a type of linked list that combines the properties of both a doubly linked list and a circular linked list.

Structure of Each Node

Each node contains three fields:

[ PREV | DATA | NEXT ]

• PREV: Pointer to the previous node
• DATA: The actual data stored
• NEXT: Pointer to the next node

Key Properties

• Every node has a pointer to both its next and previous node.
• The last node's NEXT pointer points back to the first node.
• The first node's PREV pointer points back to the last node.
• There is no NULL pointer in the list.

Diagram

  +-------+    +-------+    +-------+
  |  10   | <->|  20   | <->|  30   |
  +-------+    +-------+    +-------+
      ^                          |
      |__________________________|

Advantages

• Traversal is possible in both directions (forward and backward).
• Insertion and deletion are easier compared to singly linked lists.
• Starting from any node, the entire list can be traversed.
• No need to handle NULL; traversal stops when we return to the starting node.

Disadvantages

• Requires extra memory for the PREV pointer.
• Implementation is more complex than singly linked lists.

Applications

• Used in music players (next/previous song).
• Used in browser history (forward/backward navigation).
• Implementation of deques (double-ended queues).

b.) Breadth First Search (BFS)

Breadth First Search (BFS) is a graph/tree traversal algorithm that explores all nodes level by level, starting from a given source node.

Key Idea

• Visit all neighbors of a node before moving to the next level.
• Uses a Queue (FIFO) data structure to keep track of nodes to visit.
• Uses a visited array to avoid revisiting nodes.

Algorithm Steps

1. Start from the source node, mark it as visited, and enqueue it.
2. Dequeue a node from the front of the queue.
3. Visit all unvisited adjacent nodes, mark them visited, and enqueue them.
4. Repeat steps 2-3 until the queue is empty.

Pseudocode

BFS(Graph, start):
    Create a Queue Q
    Mark start as visited
    Enqueue start into Q

    while Q is not empty:
        node = Dequeue(Q)
        print node
        for each neighbor of node:
            if neighbor is not visited:
                mark neighbor as visited
                Enqueue(neighbor)

Example

Consider the graph:

    1
   / \
  2   3
 / \
4   5

BFS Traversal starting from node 1:

Output: 1 -> 2 -> 3 -> 4 -> 5

Characteristics

Applications

• Shortest path finding in unweighted graphs.
• Web crawlers for indexing pages.
• Social networking (finding friends within k distance).
• Cycle detection in graphs.