Basic Operations of Linked List Stack in C
Following are the basic operation of the stack data structure that helps us to manipulate the data structure as needed:
Operation | Description | Time Complexity | Space Complexity |
---|---|---|---|
isEmpty | Returns true if the stack is empty, false otherwise. | O(1) | O(1) |
Push | This operation is used to add/insert/push data into the stack. | O(1) | O(1) |
Pop | This operation is used to delete/remove/pop data into the stack. | O(1) | O(1) |
Peek | This operation returns the top element in the stack. | O(1) | O(1) |
Let’s see how these operations are implemented in the stack.
Push Function
The push function will add a new element to the stack. As the pop function require the time and space complexity to be O(1), we will insert the new element in the beginning of the linked list. In multiple push operations, the element at the head will be the element that is most recently inserted.
We need to check for stack overflow (when we try to push into stack when it is already full).
Algorithm for Push Function
Following is the algorithm for the push function:
- Create a new node with the given data.
- Insert the node before the head of the linked list.
- Update the head of the linked list to the new node.
Here, the stack overflow will only occur if there is some error allocating the memory in the heap so the check will be done in the creation of the new node.
Pop Function
The pop function will remove the topmost element from the stack. As we know that for stack, we need to first remove the most recently inserted element. In this implementation, the most recently inserted element will be present at the head of the linked list.
We first need to check for the stack underflow (when we try to pop stack when it is already empty).
Algorithm for Pop Function
Following is the algorithm for the pop function:
- Check if the stack is empty.
- If not empty, store the top node in a temporary variable.
- Update the head pointer to the next node.
- Free the temporary node.
Peek Function
The peek function will return the topmost element of the stack if the stack is not empty. The topmost element means the element at the head.
Algorithm for Peek Function
The following is the algorithm for peek function:
- Check if the stack is empty.
- If its empty, return -1.
- Else return the head->data.
IsEmpty Function
The isEmpty function will check if the stack is empty or not. This function returns true if the stack is empty otherwise, it returns false.
Algorithm of isEmpty Function
The following is the algorithm for isEmpty function:
- Check if the top pointer of the stack is NULL.
- If NULL, return true, indicating the stack is empty.
- Otherwise return false indicating the stack is not empty.
Stack Using Linked List in C
Stack is a linear data structure that follows the Last-In-First-Out (LIFO) order of operations. This means the last element added to the stack will be the first one to be removed. There are different ways using which we can implement stack data structure in C.
In this article, we will learn how to implement a stack using a linked list in C, its basic operation along with their time and space complexity analysis.
Contact Us