Past exam question: 2079 Ashwin (Back), Q4(b)
Open in the Padhaiko appWrite algorithms to implement all the basic operations of stack using singly linked list.
Solution
Stack Representation Using a Singly Linked List: In a stack, all insertions and deletions occur at the top of the stack according to the Last-In, First-Out (LIFO) policy.
In a singly linked list:
- Inserting or deleting at the head (
top) takes time since no traversal is needed. - Inserting or deleting at the tail would require traversal to update the pointer of the second-to-last node.
Therefore, the top of the stack is always maintained at the first node (head) of the singly linked list. When the stack is empty, top = NULL.
Node Structure Definition:
struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL;Algorithm for Initialization and Emptiness Check (isEmpty()):
Algorithm ISEMPTY(top):
1. If top == NULL:
Return TRUE
Else:
Return FALSE
This check runs in time.
Algorithm for Push Operation (push(val)): Inserts an element at the top of the stack (head of the linked list).
Algorithm PUSH(top, val):
1. [Allocate dynamic memory for new node]
Set newNode = Allocate_Memory(sizeof(struct Node))
2. [Check for Heap Overflow]
If newNode == NULL:
Print "Stack Overflow: Out of dynamic memory"
Return top
3. [Populate data and splice at head]
Set newNode->data = val
Set newNode->next = top
Set top = newNode
4. Print "Item successfully pushed"
5. Return top
Time Complexity: .
Algorithm for Pop Operation (pop()): Removes and returns the top element from the stack.
Algorithm POP(top):
1. [Check for Stack Underflow]
If ISEMPTY(top) == TRUE:
Print "Stack Underflow: Stack is empty"
Return NULL
2. [Preserve current top node]
Set temp = top
Set poppedItem = temp->data
3. [Advance top pointer and reclaim heap memory]
Set top = top->next
Deallocate_Memory(temp)
4. Return poppedItem
Time Complexity: .
Algorithm for Peek and Display Operations:
peek(top)(View top element without removing):
Algorithm PEEK(top):
1. If ISEMPTY(top) == TRUE:
Print "Stack is empty"
Return -1
2. Return top->data
display(top)(Traverse and print all stack elements):
Algorithm DISPLAY(top):
1. If ISEMPTY(top) == TRUE:
Print "Stack is empty"
Return
2. Set ptr = top
3. While ptr != NULL:
Print ptr->data
Set ptr = ptr->next
4. ReturnA stack using a singly linked list maps top to the head node:
isEmpty(): Returnstop == NULL.push(val): Allocates a new node, setsnewNode->next = top, and updatestop = newNode().pop(): Checks underflow; extractstop->data, advancestop = top->next, frees the old node, and returns the data ().peek(): Returnstop->datawithout modifying pointers ().