Linked representation of Stacks using Linked List

The linked representation of a stack, commonly termed linked stack is a stack that is implemented using a singly linked list. The INFO fields of the nodes hold the elements of the stack and the LINK fields hold pointers to the neighboring element in the stack. The START pointer of the linked list behaves as the TOP pointer variable of the stack and the null pointer of the last node in the list signals the bottom of the stack.

Linked representation of Stacks

1. Insertion- Using linked list in Stacks

Algorithm: PUSH_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM).

This algorithm pushes an ITEM into a linked stack.

Step I: [OVERFLOW?]
If AVAIL = NULL, then: Write: OVERFLOW, and Exit.
Step II: [Take node from AVAIL list.]
Set NEW := AVAIL, and
AVAIL := LINK[AVAIL].
Step III: [Copies ITEM into new node.]
Set INFO[NEW] := ITEM.
Step IV: [Add this node to the STACK.]
Set LINK[NEW] := TOP, and
TOP := NEW.
Step V: Exit.

You May Also Like: Mamaearth Onion Hair Mask

2. Deletion- Using linked list in Stacks

Algorithm: POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM).
This algorithm deletes the top element of a linked stack and assigns it to the variable ITEM.

Step I: [UNDERFLOW?]
If TOP = NULL, then: Write: UNDERFLOW and Exit.
Step II: Set ITEM := STACK[TOP].
[Copies the TOP element of STACK into ITEM.]
Step III: Set TEMP := TOP, and
TOP := LINK[TOP]. [Reset the position of TOP.]
Step IV: [Add node to the AVAIL list.]
Set LINK[TEMP] := AVAIL,
AVAIL := TEMP.
Step V: Exit.