A stack can be created using a linked list to allow for storing of stack elements as long as sufficient memory is available to create a new node. This circumvents the limits set by the array structure on storing elements.
Creating the stack
Before implementing the operations
- Include all header files and declare the main function.
- Define a Node structure with two members
data
andnext
. - Define a Node pointer top and set it to
NULL
.
- struct Node
- {
- int data;
- struct Node *next;
- } *top = NULL;
Pushing to the stack
Steps
- Create a new Node with given value.
- First check if the stack is empty by checking the underflow condition.
- If it is Empty, then set
newNode → next = NULL
. - If it is Not Empty, then set
newNode → next = top
. - Finally, set the top pointer to the new Node (
top = newNode
).
- void push(int value)
- {
- struct Node *newNode;
- newNode = (struct Node*)malloc(sizeof(struct Node));
- newNode->data = value;
- if(top == NULL)
- newNode->next = NULL;
- else
- newNode->next = top;
- top = newNode;
- printf("\nInsertion is Successful\n");
- }
Popping from the stack
Steps
- Check whether stack is Empty (
top == NULL
). - If it is Empty, then display an error message and terminate the function.
- If it is Not Empty, then define a Node pointer
temp
and set it totop
. - Then set
top = top → next
. - Finally, delete
temp
usingfree(temp)
.
- void pop()
- {
- if(top == NULL)
- printf("\nUnderflow. Stack is empty\n");
- else{
- struct Node *temp = top;
- printf("\nDeleted element is: %d", temp->data);
- top = temp->next;
- free(temp);
- }
- }
Visualizations
- Data Structures: Linked List implementation of stacks | mycodeschool Good explanation from mycodeschool about the implementation using linked list.
- Data Structures: Stacks and Queues | HackerRank Popular book writer Gayle Laakmann McDowell explains about stacks and queues in this HackerRank video.
- Stacks and Queues | 0612 TV w/ NERDfirst <>