PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q4(b)

Data Structure and Algorithms · 7 marks

Open in the Padhaiko app

Topic: Linked List

Question

Write 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:

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:

Algorithm PEEK(top):
1. If ISEMPTY(top) == TRUE:
       Print "Stack is empty"
       Return -1
2. Return top->data
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. Return
Answer:

A stack using a singly linked list maps top to the head node:

All past exam questions for Data Structure and Algorithms