Stack is a linear data structure which follows LIFO(Last In First Out) or FILO(First In Last Out) order to perform its functions. It can be implemented either by using arrays or linked lists.
Basic operations are performed in the stack are:
- Push: It adds an item in the stack. If the stack is full, then the stack is said to be in Overflow condition.
- Pop: It deletes an item from the stack. The items are popped out in the reverse order in which they were pushed in. If the stack is empty, then it is said to be in Underflow condition i.e no more items can be deleted.
- Peek or Top: It returns the top element of the stack.
- isEmpty: It returns true if stack is empty, otherwise false.
A linked list is a linear data structure, but unlike arrays the elements are not stored at contiguous memory locations, the elements in a linked list are linked to each other using pointers. It consists of nodes where, each node contains a data field and a link to the next node.
Flowchart for Implementing a Stack using Linked List:
1. Push Operation:
2. Pop Operation:
3. Peek Operation:
Algorithm for Implementing a Stack using Linked List:
1. PUSH() Operation:
Step 1: Start
Step 2: Create a node new and declare variable top
Step 3: Set new data part to be Null
// The first node is created, having null value and top pointing to it
Step 4: Read the node to be inserted.
Step 5: Check if the node is Null, then print "Insufficient Memory"
Step 6: If node is not Null, assign the item to data part of new and assign top to link part of new and also point stack head to new.
2. POP() Operation:
Step 1: Start
Step 2: Check if the top is Null, then print "Stack Underflow."
Step 3: If top is not Null, assign the top's link part to ptr and assign ptr to stack_head's link part.
Step 4: Stop
3. PEEK() Operation:
Step 1: Start
Step 2: Print or store the node pointed by top variable
Step 3: Stop
In the above algorithm,
- We first create a node with value Null.
- Then when we have to push an element new we check if new is not null otherwise insertion cannot be done. We then feed Item into data part of new and assign top to its link and top is updated to the new value. And thus, an element is inserted.
- For popping we check first if the item is not null, otherwise stack is empty i.e underflow condition. The pointer is then made to point the next element and st_head link is assigned to the pointer's value. This eliminates the element from the link list. Thus, popping the element
- Peek value is stored or printed by returning node at which top is pointing
Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once.