Stack Using Linked List
In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the stack because here, we do not fix the size of the stack, and it can be increased as much as we want during run time.
Here, the top pointer stores the address of the top element of the stack. As the stack size is not fixed, there is no such stack overflow condition. The stack underflow is determined if the top pointer points to the NULL value. The element is added to the top of the stack and removed from the top of the stack as it is done in the array implementation of the stack.
Here, we always need to care for the pointers during push and pop operations. We cannot unlink any node anyhow. If somehow, we unlink any node, we can never access that particular node or element, and it will be lost forever.
C++ program to implement the stack using linked list:
// Including header files
#include <iostream>
using namespace std;
// Defining the structure of the node
struct node
{
int data;
struct node *next;
};
// Creating the top pointer
struct node *top = NULL;
// Push function to add an element at the top of the stack
void push(int value)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = value;
newnode->next = top;
top = newnode;
}
// Pop operation to remove the top element of the stack
void pop()
{
if (top == NULL)
{
cout << "No elements in the stack 'Underflow!'" << endl;
}
else
{
Struct node *temp = top;
cout << "The popped element is " << temp->data << endl;
top = top->next;
free(temp);
}
}
// Function to traverse all the elements of the stack
void traverse()
{
struct node *temp;
if (top == NULL)
{
cout << "Stack is empty" << endl;
}
else
{
temp = top;
cout << "Elements in the stack are ";
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
}
// Function to search for an element in the stack
void search_in_stack(int value)
{
struct node *temp = top;
if (temp == NULL)
{
cout << "No element to search. Stack is empty!" << endl;
}
else
{
while (temp != NULL)
{
if (temp->data == value)
{
cout << value << " is present in the stack!" << endl;
return;
}
temp = temp->next;
}
cout << value << " is not present in the stack!" << endl;
}
}
// Driver function
int main()
{
cout << "Enter 1 to push an element in the stack." << endl;
cout << "Enter 2 to pop an element from the stack." << endl;
cout << "Enter 3 to search for an element in the stack." << endl;
cout << "Enter 4 to traverse all the elements of the stack." << endl;
cout << "Enter 5 to exit from the program." << endl;
int choice, x;
do
{
cout << "Enter your choice : ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Enter the value to push in the stack : ";
cin >> x;
push(x);
break;
case 2:
pop();
break;
case 3:
cout << "Enter the value to search in the stack : ";
cin >> x;
search_in_stack(x);
break;
case 4:
traverse();
break;
case 5:
cout << "Exited Successfully!";
break;
;
default:
cout << "Wrong choice!" << endl;
break;
}
} while (choice != 5);
return 0;
}
The sample output of the above program is given below:
Enter 1 to push an element in the stack :
Enter 2 to pop an element from the stack :
Enter 3 to search for an element in the stack :
Enter 4 to traverse all the elements of the stack :
Enter 5 to exit from the program :
Enter your choice : 1
Enter the value to push in the stack : 22
Enter your choice : 1
Enter the value to push in the stack : 34
Enter your choice : 1
Enter the value to push in the stack : 56
Enter your choice : 1
Enter the value to push in the stack : 23
Enter your choice : 1
Enter the value to push in the stack : 12
Enter your choice : 4
Elements in the stack are 12 23 56 34 22
Enter your choice : 2
The popped element is 12
Enter your choice : 4
Elements in the stack are 23 56 34 22
Enter your choice : 3
Enter the value to search in the stack : 34
34 is present in the stack!
Enter your choice : 3
Enter the value to search in the stack : 44
44 is not present in the stack!
Enter your choice : 5
Exited Successfully!
Let us understand the above code step by step:
- Structure of the node – Here, we have defined the structure of the node such that it can store an integer value and the address of the node of the type struct node. The struct node *next pointer is only capable of pointing to the node of the type struct node.
struct node
{
int data;
struct node *next;
};
- PUSH Operation – As we know, push operation is used to add elements at the top of the stack. In the first line of the PUSH function, we are allocating memory of the size struct node, and its address will be stored in the *newnode pointer. We have defined its type as struct node, which means it can store the node's address of the type struct node. In the second line, we are storing the value, and in the third line, we are linking our new node with the stack. It will also work if the stack is empty and newnode -> next will store a NULL value. In the last line, we are making our newly added node the top element of the stack by storing its address in the top pointer.
void push(int value)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->data = value;
newnode->next = top;
top = newnode;
}
- POP Operation – The POP operation is used to remove the top element of the stack. In the code of the POP function, we first check whether the stack is empty or not, and here, the if-block is doing the same job. If the top pointer is pointing to the NULL value, it means the stack is empty, and we can’t pop an element from it. In the else-block, we store the address of the top pointer in the temp pointer and print the value stored in it. After that, we make the very next node the top element of the stack. And in the last, we are freeing the memory allocated to the node pointed by the temp pointer.
void pop()
{
if (top == NULL)
{
cout << "No elements in the stack 'Underflow!'" << endl;
}
else
{
Struct node *temp = top;
cout << "The popped element is " << temp->data << endl;
top = top->next;
free(temp);
}
}
- Stack Traversal – In stack traversal, we traverse all nodes starting from the top node to the last node. In the code of the traverse function, we store the address of the top pointer in the temp pointer and start traversing. We first check whether the stack is empty or not. If not, we print the value stored in the node pointed by the temp pointer and update the address stored in the temp pointer. We traverse the nodes until the temp pointer starts pointing to the NULL value.
void traverse()
{
struct node *temp;
if (top == NULL)
{
cout << "Stack is empty" << endl;
}
else
{
temp = top;
cout << "Elements in the stack are ";
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
}
- Searching in Stack – To search for an element in the stack, we traverse all the nodes and match the value with all the stored values. In the if-block, we check whether the stack is empty or not. If yes, we return from the function and print “No element to search. Stack is empty!”. In the else part, the while condition will be true when the temp pointer will point to the NULL value. In the while loop, we first check the value with the value stored in the node pointed by the temp pointer. If the value matches, we will return from the function and print “The value is present in the stack”. If not, we update the temp pointer, and the temp pointer will start pointing to the next node. At the end of the while loop, we can say the value is not present in the stack and will complete the execution.
void search_in_stack(int value)
{
struct node *temp = top;
if (temp == NULL)
{
cout << "No element to search. Stack is empty!" << endl;
}
else
{
while (temp != NULL)
{
if (temp->data == value)
{
cout << value << " is present in the stack!" << endl;
return;
}
temp = temp->next;
}
cout << value << " is not present in the stack!" << endl;
}
}