PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q4

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

Topic: Linked List

Question

Write algorithms of implementation of stock and queue using singly linked list.

Solution

Stack Using Singly Linked List (top at Head):

Algorithm PUSH(top, val):
1. Allocate newNode
2. If newNode == NULL: Print "Overflow"; Return top
3. newNode->data = val
4. newNode->next = top
5. top = newNode
6. Return top

Algorithm POP(top):
1. If top == NULL: Print "Underflow"; Return NULL
2. temp = top
3. val = temp->data
4. top = top->next
5. Free(temp)
6. Return val

Both PUSH and POP run in time.

Queue Using Singly Linked List (front at Head, rear at Tail):

Algorithm ENQUEUE(front, rear, val):
1. Allocate newNode
2. If newNode == NULL: Print "Overflow"; Return
3. newNode->data = val
4. newNode->next = NULL
5. If rear == NULL:
       front = rear = newNode
   Else:
       rear->next = newNode
       rear = newNode

Algorithm DEQUEUE(front, rear):
1. If front == NULL: Print "Underflow"; Return -1
2. temp = front
3. val = temp->data
4. front = front->next
5. If front == NULL:
       rear = NULL
6. Free(temp)
7. Return val

Both ENQUEUE and DEQUEUE run in time.

Answer:

All past exam questions for Data Structure and Algorithms