[go: up one dir, main page]
Scribd
Upload
15 views11 pages

Stack and LinkedList

The document explains stacks and their applications, including infix to postfix conversion and postfix evaluation. It details the operations of stacks and provides algorithms and examples for converting infix expressions to postfix and evaluating postfix expressions. Additionally, it introduces single linked lists, their structure, and basic operations such as traversal, insertion, deletion, and searching.

Uploaded by

SIVAVEDATHRI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
15 views11 pages

Stack and LinkedList

The document explains stacks and their applications, including infix to postfix conversion and postfix evaluation. It details the operations of stacks and provides algorithms and examples for converting infix expressions to postfix and evaluating postfix expressions. Additionally, it introduces single linked lists, their structure, and basic operations such as traversal, insertion, deletion, and searching.

Uploaded by

SIVAVEDATHRI
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

Stack Applications & Linked Lists

Infix to Postfix | Postfix Evaluation | Single


Linked List
What is a Stack?

• A linear data structure following LIFO (Last In First


Out) principle.
• Elements are added and removed from the top.
• Operations: push, pop, isEmpty,isNull.
Applications of Stack

• Expression conversion (Infix to Postfix)


• Expression evaluation (Postfix)
• Backtracking (e.g., maze, recursion)
• Undo functionality in editors
Infix to Postfix
Infix: Operators are between operands (e.g., A + B).
Postfix: Operators come after operands (e.g., A B +).

Algorithm:
1. Scan from left to right.
2. Use a stack for operators.
3. Output operands directly.
4. Pop operators from the stack based on precedence.
5. Pop all remaining operators at the end.
Example
Infix: (A + B) * C
Infix: A + B * C

Steps: Steps:
1. Push '(' 1. A → Output
2. A → Output 2. + → Stack
3. + → Stack 3. B → Output
4. B → Output 4. * → Stack (has higher precedence than +)
5. C → Output
5. ')' → Pop and output till '('
6. End → Pop *, then +
6. * → Stack
7. C → Output
8. End → Pop remaining Postfix: A B C * +

Postfix: A B + C *
Postfix Evaluation
1. Scan the postfix expression from left to right.
2. If operand, push to stack.
3. If operator, pop two operands, apply operator, push result.
4. Final result will be on top of the stack.
Postfix Evaluation Example
Postfix: 5 6 2 + *

Steps:
1. 5 → Stack
2. 6 → Stack
3. 2 → Stack
4. + → Pop 6, 2 → 8 → Push
5. * → Pop 5, 8 → 40 → Push

Result: 40
Single Linked List - Introduction

• A dynamic data structure made of nodes.


• Each node has: data and pointer to next node.
• Linear structure with variable size.
• No random access like arrays.
Basic Operations on Linked List

• Traversal: Visiting each node


• Insertion: At beginning, middle, or end
• Deletion: Remove a node from list
• Search: Find if a value exists
1. Traversal:
- Visiting each node from head to end.
- Example: 10 → 20 → 30
- Output: 10, 20, 30
2. Insertion:
- At Beginning: Insert 5 → 5 → 10 → 20 → 30
- At Middle (after 20): Insert 25 → 10 → 20 → 25 → 30
- At End: Insert 40 → 10 → 20 → 30 → 40
3. Deletion:
- Beginning: Remove 10 → 20 → 30
- Middle: Remove 20 → 10 → 30
- End: Remove 30 → 10 → 20
4. Search:
- Example: Search for 20
- Output: Found at position 2
Postfix Expression Evaluation Practice:

1. 53+
2. 62*3/
3. 23+5*
4. 10 2 8 * + 3 –
5. 100 20 + 5 /
6. 4572+-*
7. 632+*
8. 93/2*

You might also like