Past exam question: 2075 Baisakh (Back), Q4
Open in the Padhaiko appQuestion
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:
- Linked Stack:
toppoints to the head node;PUSHprepends andPOPremoves attopin . - Linked Queue:
frontpoints to head andrearto tail;ENQUEUEappends atrearandDEQUEUEremoves fromfrontin , resettingrear = NULLwhen the last node is dequeued.