Stack using Linked List in C++
A data structure called a stack uses the Last-In-First-Out (LIFO) principle. The data or element at the top of the stack, which was saved last, will be accessed first. Additionally, the top is where both insertion and deletion happen. To use the linked list to prepare a stack we consider:-
- If there are additional members to add, the array's size cannot be increased once it is created.
- We will squander a lot of memory space if we design a really huge array.
- In order to address this, let's attempt to create a stack using a linked list, where we will dynamically grow the stack's size as necessary.
- Using this as the foundation of our Node's structure we will discuss the implementation
Implementation using Linked List
Given that we utilize a head pointer to keep track of the beginning of our linked list, we can simply refer to the head pointer as top when creating a stack using a linked list to make it more related to a stack.
- Push (insert element in stack)
- Similar to putting a node at the beginning of the linked list, the push operation would be.
Therefore, the top pointer will initially be NULL when the Stack (Linked List) is empty. Let's say we need to add the numbers 1, 2, and 3 to the stack.
- So, using the new operator, we will first build a new Node and return its address as a temporary pointer ptr.
- Then, we will make the link section of the node equal to the top by setting ptr->link=top and inserting the value 1 in the data part of the node using ptr->data = value.
- Finally, we will set top = ptr to refer to the newly generated node, which will serve as both the top of our stack and the beginning of the linked list.
5. Similarly, if we put the values 2 and 3 into the stack, a linked list of three nodes will result, with the top pointer referring to the node containing the value 3.
- Pop (delete element from stack)
- The pop operation is comparable to removing a beginning node from a linked list. Therefore, we shall compare a temporary pointer (ptr) to the top pointer.
- The top pointer will then be moved to the subsequent node, top = top->link.
- Using the delete operator and pointer ptr, or delete, we will finally delete the node (ptr)
- Our stack will appear something like this after we pop once:
- isEmpty (stack empty or no checker)
Simply checking whether top == NULL, which denotes that the stack is empty, will tell us whether the stack is empty or not.
Time Complexity - Each operation is O(1)
Subscribe to our Newsletter
Receive latest industry news and updates, exclusive offers directly in your inbox.