1. Pseudocode to Create a Singly 4. Why Linked List is Better Than 3.

STACK
Linked List Array (A) Pseudocode to Implement
START [Link] Size:A linked list can Stack Using Linked List
SET head ← NULL grow and shrink at runtime, while an Operations: PUSH, POP, DISPLAY
INPUT n array has a fixed size. PUSH Operation
[Link] Insertion/Deletion: PUSH(x):
FOR i ← 1 to n Insertions and deletions are faster CREATE newNode
CREATE newNode because only pointers are changed; [Link] ← x
INPUT [Link] no shifting of elements is required [Link] ← top
[Link] ← NULL as in arrays. top ← newNode
[Link] Continuous Memory END
IF head = NULL THEN Required: Arrays require POP Operation
head ← newNode contiguous memory blocks, but POP():
ELSE linked lists can use memory IF top = NULL THEN
temp ← head anywhere, making them more PRINT "Stack Underflow"
WHILE [Link] ≠ NULL flexible. RETURN
temp ← [Link] [Link] Memory Utilization: END IF
END WHILE Linked lists use memory as needed. temp ← top
[Link] ← newNode Arrays may waste memory if not top ← [Link]
END IF fully used. FREE temp
END FOR [Link] Implementation of Data END
END Structures:
2. Pseudocode to Delete the Head Stacks, queues, and other dynamic DISPLAY Operation
Node of a Linked List structures can be implemented DISPLAY():
START more efficiently using linked lists. temp ← top
IF head = NULL THEN WHILE temp ≠ NULL
PRINT "List is empty" 2. ARRAY PRINT [Link]
STOP (A) Pseudocode to Insert an temp ← [Link]
END IF Element into an Array END WHILE
temp ← head Insert value X at position POS in an END
head ← [Link] array A with size N.
FREE temp START # Prefix, Infix, Postfix (Short Notes
END INPUT A, N, X, POS for Exam)
3. Pseudocode to Insert a Node at FOR i ← N down to POS Infix Expression
the Beginning of a Linked List A[i] ← A[i - 1] *Operator is between operands
START END FOR *Example: A + B
CREATE newNode A[POS] ← X Prefix Expression (Polish
INPUT [Link] N←N+1 Notation)
[Link] ← head END *Operator comes before operands
head ← newNode *Example: + A B
(B) Pseudocode to Delete an *Easy for computers because no
END Element from an Array parentheses needed.
Delete element from position POS in Postfix Expression (Reverse Polish
array A. Notation)
START *Operator comes after operands
INPUT A, N, POS *Example: A B +
FOR i ← POS to N - 1 *Used in stack-based evaluation.
A[i] ← A[i + 1]
END FOR
N←N-1
END
4. QUEUE (B) Pseudocode to Implement 7. Binary Tree
(A) Pseudocode to Implement Queue Using Array A binary tree is a hierarchical data
Queue Using Two Stacks (Costly Let: structure where each node has at
Enqueue) • front = index of first most two children:
In this approach, enqueue is costly element • Left child
and dequeue is cheap. • rear = index of last element • Right child
Idea • Array size = MAX Types of Binary Trees
• Use two stacks: S1 and S2 Initialization [Link] Binary Tree
• Enqueue: Move all front ← -1 Every node has either 0 or 2
elements from S1 to S2 → rear ← -1 children.
push new element → move [Link] Binary Tree
back ENQUEUE(x) All levels are completely filled
• Dequeue: Simply pop from ENQUEUE(x): except possibly the last, and nodes
S1 IF rear = MAX - 1 THEN are filled from left to right.
Pseudocode PRINT "Queue Overflow" [Link] Binary Tree
ENQUEUE(x) EXIT All internal nodes have 2 children
ENQUEUE(x): END IF and all leaves are at the same level.
WHILE S1 is not empty IF front = -1 THEN [Link] Binary Tree
PUSH( S2, POP(S1) ) front ← 0 Height difference between left and
END WHILE END IF right subtree is not more than 1.
PUSH( S1, x ) rear ← rear + 1
WHILE S2 is not empty Q[rear] ← x Tree Traversal Methods
PUSH( S1, POP(S2) ) END 1. Inorder (LNR)
END WHILE Inorder(node):
END DEQUEUE() if node != NULL:
DEQUEUE() DEQUEUE(): Inorder([Link])
DEQUEUE(): IF front = -1 OR front > rear THEN Visit node
IF S1 is empty THEN PRINT "Queue Underflow" Inorder([Link])
PRINT "Queue Underflow" EXIT • Gives sorted order for BST.
ELSE END IF 2. Preorder (NLR)
RETURN POP(S1) Preorder(node):
END IF x ← Q[front] if node != NULL:
END front ← front + 1 Visit node
When and Why Use Stack or RETURN x Preorder([Link])
Queue Instead of Array/Linked END Preorder([Link])
List? 3. Postorder (LRN)
Use Stack When: 6. Linear Search (Theory) Postorder(node):
*You need LIFO (Last In First Out) Linear search is the simplest search if node != NULL:
*Example: method. Postorder([Link])
*Function calls The algorithm scans each element Postorder([Link])
*Undo operations of the list one by one from the Visit node
*Expression evaluation beginning to the end. Linear Search Binary Search
Because stack ensures the most Characteristics
Scans each
recent element is accessed first. • Works on unsorted arrays. Divides list into
element one by
• Compares key with each halves
one
Use Queue When: element.
You need FIFO (First In First Out) • Stops when element is Works on Requires
Example: found or list ends. unsorted data sorted data
o Process scheduling • Time complexity: O(n). Time: O(n) Time: O(log n)
o Print queues When to use More efficient
BFS in graphs • Small datasets Simple algorithm
but complex
Queues maintain order of arrival. • Unsorted lists
Suitable for small Suitable for
• When simplicity is required
datasets large datasets