Scribd
Upload
3 views3 pages

Data Structures: Linked Lists & Stacks

The document outlines algorithms for insertion and deletion in circular linked lists, stack and queue operations using linked lists, and conversion of prefix expressions to postfix using stacks. It provides step-by-step procedures for each operation, including examples for better understanding. Additionally, it describes the evaluation of postfix expressions using stacks with a detailed example.

Uploaded by

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

Data Structures: Linked Lists & Stacks

The document outlines algorithms for insertion and deletion in circular linked lists, stack and queue operations using linked lists, and conversion of prefix expressions to postfix using stacks. It provides step-by-step procedures for each operation, including examples for better understanding. Additionally, it describes the evaluation of postfix expressions using stacks with a detailed example.

Uploaded by

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

Data Structures Assignment

Q1: Insertion and Deletion in Circular Linked List with Header


Node
A circular linked list is a special type of linked list where the last node points back to the first node. A
header node is used to simplify operations.

Algorithm for Insertion


[Step 1: Create Node] NEW ← GetNode() [Step 2: Set Data] INFO(NEW) ← ITEM [Step 3:
Traverse] Move PTR until correct position found [Step 4: Link Update] LINK(NEW) ← LINK(PTR)
LINK(PTR) ← NEW [Step 5: Return] Return (HEADER)

Algorithm for Deletion


[Step 1: Search] Traverse list until ITEM found [Step 2: Link Update] LINK(PREV) ← LINK(LOC)
[Step 3: Free Node] Dispose LOC [Step 4: Return] Return (HEADER)

HEADER 10 20
Q2: Stack and Queue using Linked List
Stacks use LIFO (Last In First Out), Queues use FIFO (First In First Out).

Algorithm for Stack Operations


Push(X): [Step 1: Create Node] NEW ← GetNode() [Step 2: Insert] INFO(NEW) ← X LINK(NEW) ←
TOP [Step 3: Update Top] TOP ← NEW [Step 4: Return] Return (TOP) Pop(): [Step 1: Check
Empty] If TOP = NULL → Underflow [Step 2: Remove] LOC ← TOP [Step 3: Update] TOP ←
LINK(TOP) [Step 4: Free Node] Dispose LOC [Step 5: Return] Return (TOP)

TOP

30

20

10

Algorithm for Queue Operations


Enqueue(X): [Step 1: Create Node] NEW ← GetNode() [Step 2: Insert] INFO(NEW) ← X
LINK(NEW) ← NULL [Step 3: Update Rear] If REAR = NULL → FRONT ← REAR ← NEW Else
[Link] ← NEW [Step 4: Return] Dequeue(): [Step 1: Check Empty] If FRONT = NULL →
Underflow [Step 2: Remove] LOC ← FRONT [Step 3: Update] FRONT ← LINK(FRONT) [Step 4:
Free Node] Dispose LOC [Step 5: Return]

FRONT REAR

10 20 30
Q3: Conversion of Prefix to Postfix using Stack

Algorithm:
[Step 1: Read Expression] Scan prefix from right to left [Step 2: Operand?] If symbol is operand →
Push to stack [Step 3: Operator?] If operator → Pop two operands → combine as (op1 op2
operator) → Push result [Step 4: Repeat] Continue until end [Step 5: Result] Top of stack = Postfix
Expression

Example:
Prefix: *+AB-CD Steps: 1. Read D, C → push 2. '-' → pop C, D → 'CD-' → push 3. Read B, A →
push 4. '+' → pop A, B → 'AB+' → push 5. '*' → pop 'AB+', 'CD-' → 'AB+CD-*' Final Postfix:
AB+CD-*

Q4: Evaluation of Postfix using Stack

Algorithm:
[Step 1: Read Expression] Scan postfix from left to right [Step 2: Operand?] If operand → Push to
stack [Step 3: Operator?] If operator → Pop two values → Apply operation → Push result [Step 4:
Repeat] Until end of expression [Step 5: Result] Final value on stack is the answer

Example:
Postfix: 23*54*+ Steps: 1. Push 2, Push 3 2. '*' → 2*3=6 → push 3. Push 5, Push 4 4. '*' → 5*4=20
→ push 5. '+' → 6+20=26 → push Final Result = 26

You might also like