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 Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

Stack Using Array

Stack – A Stack is a linear abstract data type used to store elements. It is also called last in first out or first in last out data structure because the newly added element is removed first from the stack and the element added first is removed in last.

The basic operations performed on the stack data structure are push and pop, where push operation is used to add elements at the top of the stack, and pop operation is used to remove the top element of the stack.

In array implementation of stack, the top pointer stores the index value of the latest element added to the stack, known as the top of the stack. It is also known as the static implementation of the stack because here we fix the size of the stack. During the run time it can never be increased.

For Loop in C

The value of the top pointer determines the condition of stack overflow and underflow. When the top pointer stores the maximum possible index value, we can clearly say that the stack is overflowing, and if it is negative, we can say that the stack is underflowing.

The C++ program to implement stack using array as the primitive data type is given below:

// Array implementation of stack in C++
#include <iostream>
using namespace std;


// Defining the stack of size 10
int stack[10];
int n = 10;
int top = -1;


// Push function to push element at the top of the element
void push(int value)
{
    if (top == n - 1)
    {
        cout << "Stack overflow!" << endl;
    }
    else
    {
        top++;
        stack[top] = value;
    }
}


// Pop function to remove the top element from the stack
void pop()
{
    if (top == -1)
    {
        cout << "Stack underflow!";
    }
    else
    {
        cout << "The popped element is " << stack[top] << endl;
        top--;
    }
}


// Function to search element in the stack
void search_in_stack(int value)
{
    if (top == -1)
    {
        cout << "No element in stack" << endl;
    }
    for (int i = 0; i <= top; i++)
    {
        if (stack[i] == value)
        {
            cout << value << " is present in the stack!" << endl;
            return;
        }
    }
    cout << value << " is not present in the stack!" << endl;
}


// Function to display all the elements of the stack
void traverse()
{
    if (top == -1)
    {
        cout << "No element in stack" << endl;
        return;
    }
    cout << "Element of the stack are : ";
    for (int i = 0; i <= top; i++)
    {
        cout << stack[i] << " ";
    }
    cout << endl;
}


// Driver function
int main()
{


    cout << "Enter 1 to push element in the stack." << endl;
    cout << "Enter 2 to pop element from the stack." << endl;
    cout << "Enter 3 to search element in the stack." << endl;
    cout << "Enter 4 to print all the element 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 anelement in the stack.
Enter 2 to pop an element from the stack.
Enter 3 to search an element in the stack.
Enter 4 to print 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 : 12
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 : 5
Enter your choice : 1
Enter the value to push in the stack : 67
Enter your choice : 1
Enter the value to push in the stack : 23
Enter your choice : 2
The popped element is 23
Enter your choice : 3
Enter the value to search in the stack : 45
45 is not present in the stack!
Enter your choice : 3
Enter the value to search in the stack : 23
23 is not present in the stack!
Enter your choice : 4
Element of the stack are : 12 34 5 67 
Enter your choice : 5
Exited Successfully!

In the above program, the main function is programmed so that the program will be run according to the user’s choice. The stack operations or function calls will be done as per the user’s choice. Such types of programs are also known as menu-driven programs.

  • POP operation – The POP operation is used to pop the top element of the stack, and the code of the same is explained below:

Here, we first check whether the stack is already empty or not, and the condition for the same is top = -1. If the stack is empty, we throw a warning that the stack is underflowing and no elements if present in the stack to pop. If the stack is not empty, we pop the top element by printing its value, and we decrement the value of the top pointer by 1, and the top pointer will store the index value of the very previous element. Here, we actually don’t delete the value from the stack or array, we forget the top element and make the very previous element as the top element of the stack.

void pop()
{
    if (top == -1)
    {
        cout << "Stack underflow!";
    }
    else
    {
        cout << "The popped element is " << stack[top] << endl;
        top--;
    }
}
  • PUSH Operation – The PUSH operation is used to add elements at the top of the stack, and the code of the push operation is explained below:
void push(int value)
{
    if (top == n - 1)
    {
        cout << "Stack overflow!" << endl;
    }
    else
    {
        top++;
        stack[top] = value;
    }
}

To perform the push operation on a stack, we first check whether the stack is already full or not, and the condition for the same is top = n-1, where n is the size of the array. If the stack is already full, we can’t add an element to it, and we throw a warning of ‘stack overflow’. If the stack is not full, we first increment the value of the top pointer by 1 and add the new element at the top index. The newly added element becomes the new top element of the stack.

  • Searching is stack – One cannot easily search for an element in a stack. As the basic operations performed on a stack are push and pop. The code for the search element in a stack is explained below:
void search_in_stack(int value)
{
    if (top == -1)
    {
        cout << "No element in stack" << endl;
    }
    for (int i = 0; i <= top; i++)
    {
        if (stack[i] == value)
        {
            cout << value << " is present in the stack!" << endl;
            return;
        }
    }
    cout << value << " is not present in the stack!" << endl;
}

We are using the linear search here, as we have implemented our stack using an array. We are traversing the stack from the 0th index to the top index. We match the input value one by one, and if we find the element, we give the output as “the element is present in the stack”. If not, we give the output as “the element is not present”. Before searching for the element, we first check the stack underflow condition.

  • Stack Traversal – There are two methods to traverse a stack. In the first method, we pop all the stack elements. In the second method, we traverse the stack internally depending on which primitive data structure is used to implement that stack without popping any element from it. The code of stack traversal is explained below:
void traverse()
{
    if (top == -1)
    {
        cout << "No element in stack" << endl;
        return;
    }
    cout << "Element of the stack are : ";
    for (int i = 0; i <= top; i++)
    {
        cout << stack[i] << " ";
    }
    cout << endl;
}

Here, we are internally traversing all the elements starting from the 0th index to the top index and printing all the values as the program’s output without removing any element from the stack. Before traversing the stack, we have checked the condition of stack underflow.



ADVERTISEMENT
ADVERTISEMENT