Unit I - Introduction to Data Structures & Stack

1. Introduction to Data Structures

1. Types of Data Structures — Static, Dynamic, Primitive, Non-Primitive, Linear, Non-Linear
2. Stack
   • Definition
   • Representation
   • Operations
   • Implementation
   • Applications — Conversion of Polish notations, Evaluation of postfix expressions

1.1 Data Structure — Definition

• Examples: Arrays, Linked List, Stack, Queue, Tree, Graph, etc.
• Data Structures are widely used in almost every aspect of Computer Science — Operating System, Compiler Design, Artificial Intelligence, Graphics and many more.
• Data Structures are the main part of many computer science algorithms as they enable programmers to handle data in an efficient way.
• It plays a vital role in enhancing the performance of software or a program — the main function of software is to store and retrieve user data as fast as possible.

1.2 Basic Terminology

Data structures are the building blocks of any program or software. Choosing the appropriate data structure for a program is the most difficult task for a programmer. Following terminology is used as far as data structures are concerned:

1.3 Need of Data Structures

As applications are getting complex and amount of data is increasing day by day, the following problems may arise:

1. Processor speed: To handle very large amount of data, high speed processing is required. But as data grows day by day to billions of files per entity, processor may fail to deal with that much amount of unorganized data.
2. Data Search: Consider an inventory size of 10⁶ items in a store. If application needs to search a particular item, it must traverse 10⁶ items every time — results in slowing down the search process.
3. Multiple requests: If thousands of users search data simultaneously on a web server, there are chances that a very large server can fail during that process.

1.4 Advantages of Data Structures

• Efficiency: Efficiency of a program depends upon the choice of data structures. Example: if we organize data in an array, we must search sequentially element by element — not very efficient. Better data structures: ordered array, binary search tree, hash tables.
• Reusability: Data structures are reusable — once implemented, can be used at any other place. Implementation can be compiled into libraries used by different clients.
• Abstraction: Data structure is specified by the ADT which provides a level of abstraction. Client program uses data structure through interface only, without getting into implementation details.

2. Types of Data Structures

Syllabus types: Static, Dynamic, Primitive, Non-Primitive, Linear, Non-Linear — see diagram and distinguish tables below.

2.1 Linear Data Structures

If a data structure organizes data in sequential order, it is called a Linear Data Structure.

Examples: Arrays, List (Linked List), Stack, Queue

Arrays

• An array is a collection of similar type of data items; each data item is called an element of the array.
• Data type of element may be any valid type: char, int, float or double.
• Elements share the same variable name but each carries a different index number (subscript).
• Array can be one dimensional, two dimensional or multidimensional.
• Individual elements: age[0], age[1], age[2], ... age[98], age[99]

Linked List

• Linked list is a linear data structure used to maintain a list in memory.
• Collection of nodes stored at non-contiguous memory locations.
• Each node contains a pointer to its adjacent node.

Stack

• Stack is a linear list in which insertion and deletions are allowed only at one end called top.
• Stack is an Abstract Data Type (ADT); can be implemented in most programming languages.
• Named stack because it behaves like real-world stack — piles of plates, deck of cards, etc.

Queue

• Queue is a linear list — elements inserted only at one end called rear and deleted only at other end called front.
• Abstract data structure, similar to stack.
• Opened at both ends — follows FIFO (First-In-First-Out) methodology.

2.2 Non-Linear Data Structures

If data is organized in random order (not sequential), it is Non-Linear Data Structure.

Examples: Tree, Graph, Dictionaries, Heaps, Tries, etc.

Trees

• Trees are multilevel data structures with hierarchical relationship among elements known as nodes.
• Bottommost nodes = leaf nodes; topmost node = root node.
• Each node contains pointers to adjacent nodes.
• Based on parent-child relationship.
• Each node can have more than one child (except leaves); each node has at most one parent (except root).
• Many categories — binary tree, BST, AVL (discussed later in course).

Graphs

• Pictorial representation of set of elements (vertices) connected by links known as edges.
• Graph is different from tree: graph can have cycle while tree cannot have cycle.

A Difference between Primitive and Non-Primitive Data Structure

B Difference between Static and Dynamic Data Structure

C Difference between Linear and Non-Linear Data Structure

3. Stack — Definition, LIFO, Overflow & Underflow

A Stack is a linear data structure. A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of the stack.

Stack principle is LIFO (Last In, First Out). The element inserted last on to the stack is deleted first from the stack. As the items can be added or removed only from the top, the last item to be added to a stack is the first item to be removed.

Real-life Examples of Stack

• Piles of plates — top plate removed first
• Deck of cards
• Stack of books, bangles on a wrist
• Undo (Ctrl+Z) in text editor
• Browser Back button history
• Function call stack in recursion

Operations on Stack

The two basic operations associated with stacks are:

1. Push
2. Pop

While performing push and pop operations the following tests must be conducted on the stack:

1. Stack is empty or not
2. Stack is full or not

Push

Push operation is used to add new elements into the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".

Pop

Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

Overflow & Underflow

4. Stack Representation — Array vs Linked List

5. Stack Operations — Push, Pop, Peek, Display

Algorithm — push()

Step 1: START
Step 2: if top >= size-1 then
            write "Stack is Overflow"
Step 3: otherwise
        3.1: read data value 'x'
        3.2: top = top + 1
        3.3: stack[top] = x
Step 4: END

Algorithm — pop()

Step 1: START
Step 2: if top == -1 then
            write "Stack is Underflow"
Step 3: otherwise
        3.1: print "deleted element" stack[top]
        3.2: top = top - 1
Step 4: END

Algorithm — peek()

Step 1: START
Step 2: if top == -1 then write "Stack is Empty"
Step 3: otherwise print "Top element =" stack[top]  (do NOT change top)
Step 4: END

Algorithm — display()

Step 1: START
Step 2: if top == -1 then write "Stack is Empty"
Step 3: otherwise
        3.1: print "Elements are:"
        3.2: for i = top down to 0  →  print stack[i]
Step 4: END

Remember (array stack):
  push → top = top + 1; stack[top] = x;
  pop  → x = stack[top]; top = top - 1;
  empty when top == -1;  full when top == MAX-1;

Push Diagram — Insert 11, 22, 33 (array size = 5)

Initially top = −1 (stack empty). On each push: check overflow → top = top + 1 → stack[top] = value. Element is always added at the TOP end.

Pop Diagram — Delete 33, 22, 11

On pop: check underflow → remove element at stack[top] → top = top − 1. Last inserted element is removed first (LIFO).

Push / Pop with Example (Exam Write-up — Questions.txt style)

Array stack of size 5, initially top = −1.

6. Applications of Stack

As per syllabus, main stack applications for exam are:

1. Conversion of Polish notations — Infix to Postfix using stack
2. Evaluation of postfix expressions — scan expression and use stack to compute result

Other common applications (extra viva):

• Recursive function calls (function call stack — LIFO of return addresses)
• Balanced parentheses checking in compilers
• Reversing a string / number using stack
• Undo / Redo in text editors

7. Polish Notations — Infix, Postfix, Prefix

Difference between Infix, Postfix and Prefix Notation

Operator Precedence & Associativity (Must-Write Table)

8. Conversion of Polish Notations — Infix to Postfix

Scan infix left → right. Use a stack for operators / parentheses. Write postfix to output.

Complete Algorithm

1. Initialize empty stack and empty output string.
2. Scan the infix expression from left to right, one symbol at a time.
3. If symbol is an operand (A–Z / 0–9) → append it to output.
4. If symbol is ( → PUSH onto stack.
5. If symbol is ) → POP and append to output until ( is popped (discard ().
6. If symbol is an operator:
   • Case 1 — Left associative (+ − * /): while stack not empty and TOP is operator and precedence(TOP) ≥ precedence(scanned) → POP to output. Then PUSH scanned.
   • Case 2 — Right associative (^): while stack not empty and TOP is operator and precedence(TOP) > precedence(scanned) → POP to output. Then PUSH scanned. (Equal ^ does NOT pop.)
7. After whole expression is scanned → POP and append all remaining operators from stack.
8. Output string is the postfix expression.

Decision Tree (Quick Reference)

Is scanned operator precedence > stack top?
├── YES → PUSH directly
└── NO → Is precedence equal?
    ├── YES → Is operator right associative?
    │   ├── YES (^) → PUSH (Cases 7, 8)
    │   └── NO (Left) → POP then PUSH (Cases 5, 6)
    └── NO → POP then check again (Cases 2, 3, 4)
Memory: Higher wins | Left pops equal | Right stacks equal

8 Important Cases (Infix → Postfix)

Worked Example — ((A - (B + C)) * D) ^ (E + F)

Infix: ((A - (B + C)) * D) ^ (E + F)  |  Postfix: ABC+-D*EF+^

Worked Example — a + b * c + (d * e + f) * g

Postfix: abc*+de*f+g*+

Worked Example — A + B * C - D / E * H

Postfix: ABC*+DE/H*-

Worked Example — A+(B*C-(D/E^F)*G)*H

Postfix: ABC*DEF^/G*-H*+

9. Evaluation of Postfix Expressions

Postfix expression is evaluated easily by using a stack. Scan the expression from left to right. No operator precedence rules are needed in postfix.

Algorithm — Evaluation of Postfix Expression

Step 1: START
Step 2: Create an empty stack
Step 3: Scan the postfix expression from LEFT to RIGHT, one symbol at a time
Step 4: If scanned symbol is an OPERAND (number)
            PUSH it onto the stack
Step 5: If scanned symbol is an OPERATOR
            b = POP()          /* first pop  = RIGHT operand */
            a = POP()          /* second pop = LEFT operand  */
            result = a operator b
            PUSH result onto stack
Step 6: Repeat Step 3 until end of expression
Step 7: POP the stack — this is the FINAL ANSWER
Step 8: END

Example 1 — 2 3 4 * + → Answer: 14

Same as infix 2 + 3 * 4

Final Answer = 14

Example 2 — 8 2 / → Answer: 4

Final Answer = 4

Example 3 — 5 3 + 2 * → Answer: 16

Final Answer = 16

Worked Example — 6 5 2 3 + 8 * + 3 + *

Final Answer = 288

Worked Example — 6 2 3 + - 3 8 2 / + * 2 ^ 3 +

Final Answer = 52