Stack and it’s Implementation

5 min readJun 12, 2022

Implementation of stack using Arrays and Linked-list a in C++.

Stack is a linear data structure used to store data. It is very simple and very similar to Linked-list. Stack operates on the LIFO principle. A stack is also considered an Abstract Data Type(ADT) with two main principle operations,

Push
Pop

We know how arrays, linked-lists etc are implemented. But since we don’t know how stacks are implemented, they are called Abstract Data Type. However, stacks can be implemented using Arrays and Linked-list.

Chiefly, there are two common data structures, one which uses LIFO(Last-In-First-Out) and second that uses FIFO(First-In_First-Out).

LIFO — Stacks

FIFO — Queues

Stack examples…..,

A pile of Cafeteria Trays,

or a yummy Pancake stack

Last-In-First-Out

In a LIFO data structure, the newest element which was last inserted will also be removed first while the popping operation. Thus, the insertion and deletion operations are performed on just one end. In the below given example, the top of the stack is 5 when we push(5). If we pop(5), the top of stack will change to 4.

We can perform several operations like,

push() — Inserts an element on the top of the stack.
pop() — Removes the topmost element from the stack.
peek() — Returns the element at the give position without modifying the stack if the stack is non-empty.
size() — Returns the number of elements in the stack.
isEmpty() —Returns TRUE if stack is empty, otherwise FALSE.
isFull() — Returns TRUE if stack is full, otherwise it returns FALSE.

Implementation of Stack using Arrays

In this part, only the push() and pop() operations of the stack are discussed. We will see how to push and pop an element and also display the final stack that will we have.

#NOTE — Here, out top of stack will hold the index value of the element.

Code Walk-through

For our convenience, we will create a class named Stack with necessary variables like size, top and a pointer array named stackArray. Here I’ve implemented the whole concept using a class. The same can also be accomplished without the use of class. But believe me, just do it using either a class or a structure. This will help you understand OOP concept well and also it is easy to use and manage.

Now, create a Parameterized Constructor(a constructor is called on the creation of an object of the class). It will take in the size of an array as a parameter and create a new pointer array of the same size. Since, at the very start, our stack will be empty, thus, we will initialize top = -1.

Create push() and pop() function.

— push() function will take in val as an argument, value which we want to insert in the stack.

— pop() function will not take any arguments, it will simply decrement the top value if the stack is not EMPTY.

— display() function will display the final stack elements and the their indices. The output is shown later in this article.

Full Code —

#include<bits/stdc++.h>
using namespace std;class Stack
{
 int size; //max size of array
 int top;
 int *stackArr;
public:
 Stack(int n);
 void push(int val);
 void pop();
 void display();
};Stack :: Stack(int n)
{
 top = -1;
 stackArr = new int[n];
 size = n;
}
void Stack :: push(int val)
{
 cout<<endl;
 if(top > size)
  cout<<"Stack Overflow"<<endl;
 else{
  top++;
  stackArr[top] = val;
 }
}
void Stack :: pop()
{
 if(top<=-1)
  cout<<"\nStack Underflow"<<endl;
 else{
  top--;
 }
}
void Stack :: display()
{
 cout<<"Top : "<<top<<endl;
 if(top>=0)
 {
  cout<<"Displaying Stack___ "<<endl;
  for(int i=top;i>=0;i--){
   cout<<"\t\t "<<stackArr[i]<<" - Index -> "<<i<<endl;
  }
 }
 else
  cout<<"Stack is empty";
}int main()
{
 struct Stack t1(100);
 
 t1.push(10);
 t1.push(20);
 t1.push(30);
 t1.push(40);
 t1.display();
 
}Stack :: Stack(int n)
{
 top = -1;
 stackArr = new int[n];
 size = n;
}
void Stack :: push(int val)
{
 cout<<endl;
 if(top > size)
  cout<<"Stack Overflow"<<endl;
 else{
  top++;
  stackArr[top] = val;
 }
}
void Stack :: pop()
{
 if(top<=-1)
  cout<<"\nStack Underflow"<<endl;
 else{
  top--;
 }
}
void Stack :: display()
{
 cout<<"Top : "<<top<<endl;
 if(top>=0)
 {
  cout<<"Displaying Stack___ "<<endl;
  for(int i=top;i>=0;i--){
   cout<<"\t\t "<<stackArr[i]<<" - Index -> "<<i<<endl;
  }
 }
 else
  cout<<"Stack is empty";
}int main()
{
 struct Stack t1(100);
 
 t1.push(10);
 t1.push(20);
 t1.push(30);
 t1.push(40);
 t1.display();
 
}