×

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.


Related Topics

Finding the Minimum and Maximum Value of a Binary Tree

Implementation // Writing a C++ program that will help us find out the maximum and the minimum in a binary tree.  #include <bits/stdc++.h> #include <iostream> using namespace std; // creating a new class tree node. class...

5 minutes read.

Introduction to Arrays

What exactly is an array? A group of related data pieces stored in contiguous memory regions is referred to as an array. It is the most basic data structure in which...

5 minutes read.

Advantages and Disadvantages of Linked List

Advantages of Linked List The linked list is a dynamic data structure.You can also decrease and increase the linked list at run-time. That is, you can allocate and deallocate memory at...

3 minutes read.

Treap data structure

In this article, we will discuss the treap data structure. The word treap is a combination of 'tree' and 'heap'. So, treap data structure is a combination of a heap...

8 minutes read.

Applications of trees in data structures

Data structures Storage used to organize and store data is known as the data structure. It is a method of managing computerized data to translate or retrieve it more efficiently. A...

7 minutes read.

Given Two Binary Trees, Check if it is Symmetric

Implementation // creating a C++ program that will help us check whether the two given trees are mirror images of each other.  #include<bits/stdc++.h> using namespace std; /* A given binary tree has a data...

5 minutes read.

Perfect Binary Tree

Complete binary trees are an important and general topic in the concept – of tree data structures. Before discussing a complete binary tree, we need to know the concept of...

4 minutes read.

Stack vs Heap Memory Allocation Data Structure

Difference Between Stack and Heap Memory Allocation Stack Memory Stack memory allocation is a way to use the system memory as a temporary storage of the data which is act like last-in-first-out...

3 minutes read.

All About Minimum Cost Spanning Trees in Data Structure

Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system that stores, manages, and optimizes...

7 minutes read.

Structure and Union Data Structure

The array is used for the same type of data, but if we want to store a mixed type of data in a group, then the array cannot be used. The Structure...

4 minutes read.

Binary tree insertion

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. Here the name of the tree itself portrays the mechanism...

4 minutes read.

Operations on 1D-Arrays

One Dimensional Array Operations Basic Methods The fundamental operations enabled by an array are listed below. Traverse prints each element of the array one by one.Insert a new element at the specified index.Delete...

8 minutes read.

Left View of Binary Tree

Implementation // creating a C++ program to print the Left view of the binary tree. #include <bits/stdc++.h> using namespace std; struct Nod { int record; struct Nod *Lft, *Rt; }; // creating a utility function that will eventually help...

4 minutes read.

Binary Search Tree vs AVL Tree: Data Structure

Difference Between Binary Search Tree and AVL Tree Binary Search Tree: The binary search tree is a kind of binary tree data structure and it follows the conditions of binary...

3 minutes read.

Horizontal and Vertical Scaling

Being a software engineer, you would have designed a website or application and deployed it on any server. Imagine that the developed application starts getting popular, and many users engage...

6 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.

Insertion Sort vs Selection Sort

In this article, we will discuss insertion sort, Selection sort and the basic differences between these two sorting techniques in detail: What is Insertion Sort? Insertion Sort – The insertion sort is...

5 minutes read.

Permutation Sort or Bogo Sort

In Permutation Sort or Bogo Sort, you have been given one array, which consists of different values. You have to sort the array using BOGO sort. Let’s take an example: Input-...

3 minutes read.

Compare Balanced Binary Tree and Complete Binary Tree

Complete and balanced binary trees are important and general topics in the concept – Tree data structure. Before discussing the complete and balanced binary tree, we need to have an...

8 minutes read.

Spanning Tree

Spanning Tree: The spanning tree is a subset of the graph. It is a non-cyclic graph. If any node in the spanning tree is truncated, the entire graph fails. There are...

10 minutes read.