Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

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.

Stack Using Linked List

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;
    }
}



ADVERTISEMENT
ADVERTISEMENT