C++ programs to implement stack data structure using array

by Aug 25, 2021C++, Coding0 comments

In this article, we will implement a stack using arrays as we know that all the elements in the stack are of the same data type. So, we can easily implement stack using arrays.

What is stack?

Stack always follows the LIFO (last in, first out) rule. So, the first element will be placed on the zero index of the array. And every new element will be placed after that. And the top of the stack is the index of the array where we put the last element. 

In the stack data structure, we can only push and pop the data through one end. It means that it is only accessed through the top, not through the middle or bottom. This is a very important feature of the stack, and we must understand it well before implementing stacks.

C++ stack working explanation

You can also see the functionality of the stack from the given example. Here all the new elements are pushed on the top, and if we want to read the data from the stack, we will only access the data from the top, not from the middle or bottom.


Since stack elements are only accessed from the top, we need to update the top in all the operations.
The base of the stack remains the same until the stack becomes empty.

Stack using arrays.

To implement a stack using arrays, we take the direction of the stack. This means the direction in which the elements are inserted towards the right.

stack using arrays image 1

Let’s take an example of an array of five elements to implement a stack. First of all, initialize the size of array five. Then we create the array of that size in different ways. For example, int *arr = new int[size]; or int arr[size];


Also, we need to initialize a variable named top with the value -1. This means that in the beginning, the top is -1 because we didn’t add any value to the stack.

stack using arrays image 2

Now consider that we want to push any value in the stack. First, we check that what is the value of the stack. If it is -1, it means the stack is empty. We are free to push any value in the stack. Then we push the value 6 in the stack.

stack using arrays image 3

After pushing 6 to stack, we modify the top value and assign zero “0”. Now again, consider we want to push another value in the stack. First of all, we again check that the stack is full or not. If the stack is not full means, we are free to push any value in the stack. This time we push 8 to stack.

stack using arrays image 4

After pushing 8 to stack, we again increase the value of the top by one. This process continues until the top value becomes equal to one less than the size of the stack. It means the stack is full. And we are unable to push any new value in the stack.


Now consider we want to pop eight from the stack. First, we check that the stack is empty or not by checking the value of the top. If the top variable has a value of more than -1 means that the stack is not empty. Then we will pop a value from the stack and decrease the value of the top by 1.

stack using arrays image 5

You have to keep in mind that whenever you push any value to the stack. You have to increase the value of the top by 1. And whenever you pop any value from the stack, you must decrease the top value by 1.

Stack operations:

The operations of the stack are as follows.

  • Stack::push();
  • Stack::pop();
  • Stack::top();
  • Stack::empty();
  • Stack::full();
  • Stack::size();
  • Stack::operator=();

Code of Implementation of stack using array using Templates:

Stack header file.

// Stack header file

#pragma once
#include<iostream>
using namespace std;
template<typename type>// template  class 
class Stack // class name
{
private:// private members
	type* ptr;// pointer
	int size;// this indicates the size of stack
	int position;// this indicates the current position of last element in stack
protected:// protected members
	void deepcopy(type* tobecopied, type*& incopy);// deep copy function
public:// public members
	Stack();// default constructor
	Stack(const Stack& obj);// copy constructor
	void push(type val);// push function in stack
	void pop();// function to pop value from stack
	type top();// function to see top value from stack
	bool empty();// function that returns true if stack is empty
	bool isFull();// this function returnss true if the stack is full
	int Size();// function to display size of stack
	void print()const;// function to print stack 
	void operator= (const Stack& obj);// equal to operator in stack
	~Stack();// destructor of stack
};

Stack.cpp

//Stack.cpp

#include "Stack.h"
template<typename type>
void Stack<type>::deepcopy(type* tobecopied, type*& incopy)
{
	if (incopy != nullptr)
	{
		delete[] incopy;
		incopy = nullptr;
	}
	incopy = new type[strlen(tobecopied)];
	for (int i = 0; i < strlen(tobecopied); i++)
		incopy[i] = tobecopied[i];
}
template<typename type>// template  function
Stack<type>::Stack()// default constructor
{
	this->size = 10;
	this->position = -1;
	if (this->ptr != nullptr)
	{
		delete[] this->ptr;
		this->ptr = nullptr;
	}
	this->ptr = new type[size]();
}
template<typename type>// template  function
Stack<type>::Stack(const Stack& obj)// copy constructor
{
	this->size = obj.size();
	this->position = obj.position();
	deepcopy(obj.ptr, this->ptr);
}
template<typename type>// template  function
void Stack<type>::push(type val)// push function in stack
{
	if (isFull())
		cout << " Sorry you are not able to push data in stack : " << endl;
	else
	{
		this->position++;
		this->ptr[this->position] = val;
	}
}
template<typename type>// template  function
void Stack<type>::pop()// function to pop value from stack
{
	if (empty())
		cout << " Stack is already empty : " << endl;
	else
	{
		this->ptr[this->position] = 0;
		this->position--;
	}
}
template<typename type>
type Stack<type>::top()// function to see top value from stack
{
	if (empty())
	{
		cout << " stack is empty : " << endl;
		return -1;
	}
	else
		return this->ptr[this->position];
}
template<typename type>// template  function
bool Stack<type>::empty()// function that returns true if stack is empty
{
	if (this->position == -1)
		return true;
	else
		return false;
}
template<typename type>
bool Stack<type>::isFull()
{
	if (this->position == this->size-1)
		return true;
	else
		return false;
}
template<typename type>// template  function
int Stack<type>::Size()// function to display size of stack
{
	return this->size;
}
template<typename type>
void Stack<type>::print() const
{
	if (this->position == -1)
		cout << " Stack is already empty : " << endl;
	else
	{
		cout << " Required data is : " << endl;
		for (int i = this->position; i >= 0; i--)
			cout << " " << ptr[i];
		cout << endl;
	}
}
template<typename type>// template  function
void Stack<type>::operator= (const Stack& obj)// equal to operator in stack
{
	this->position = obj.position;
	this->size = obj.size;
	deepcopy(obj.ptr, this->ptr);
}
template<typename type>// template  function
Stack<type>::~Stack()// destructor of stack
{
	if (this->ptr != nullptr)
	{
		delete[] this->ptr;
		this->ptr = nullptr;
	}
}

Main source file.

// main source file or main file

#include<iostream>
#include"Stack.h"
#include"Stack.cpp"
using namespace std;
int main()
{
	Stack<int> obj;
	obj.push(10);
	obj.push(9);
	obj.push(8);
	obj.push(7);
	obj.push(6);
	obj.push(5);
	obj.push(4);
	obj.push(3);
	obj.push(2);
	obj.push(1);
	obj.push(0);
	obj.print();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.print();
	return 0;
}

Output.

Code of Implementation of stack using array without Templates:

Stack header file.

// stack header file

#pragma once
#include<iostream>
using namespace std;
class Stack // class name
{
private:// private members
	char* ptr;// pointer
	int size;// this indicates the size of stack
	int position;// this indicates the current position of last element in stack
protected:// protected members
	void deepcopy(char* tobecopied, char*& incopy);// deep copy function
public:// public members
	Stack();// default constructor
	Stack(const Stack& obj);// copy constructor
	void push(char val);// push function in stack
	void pop();// function to pop value from stack
	char top();// function to see top value from stack
	bool empty();// function that returns true if stack is empty
	bool isFull();// this function returnss true if the stack is full
	int Size();// function to display size of stack
	void print()const;// function to print stack 
	void operator= (const Stack& obj);// equal to operator in stack
	~Stack();// destructor of stack
};

Stack.cpp

// stack.cpp

#include "Stack.h"
void Stack::deepcopy(char* tobecopied, char*& incopy)
{
	if (incopy != nullptr)
	{
		delete[] incopy;
		incopy = nullptr;
	}
	incopy = new char[strlen(tobecopied)+1];
	for (int i = 0; i < strlen(tobecopied); i++)
		incopy[i] = tobecopied[i];
	incopy[strlen(tobecopied)] = '\0';
}
Stack::Stack()// default constructor
{
	this->size = 10;
	this->position = -1;
	if (this->ptr != nullptr)
	{
		delete[] this->ptr;
		this->ptr = nullptr;
	}
	this->ptr = new char[size]();
}
Stack::Stack(const Stack& obj)// copy constructor
{
	this->size = obj.size;
	this->position = obj.position;
	deepcopy(obj.ptr, this->ptr);
}
void Stack::push(char val)// push function in stack
{
	if (isFull())
		cout << " Sorry you are not able to push data in stack : " << endl;
	else
	{
		this->position++;
		this->ptr[this->position] = val;
	}
}
void Stack::pop()// function to pop value from stack
{
	if (empty())
		cout << " Stack is already empty : " << endl;
	else
	{
		this->ptr[this->position] = 0;
		this->position--;
	}
}
char Stack::top()// function to see top value from stack
{
	if (empty())
	{
		cout << " stack is empty : " << endl;
		return '-';
	}
	else
		return this->ptr[this->position];
}
bool Stack::empty()// function that returns true if stack is empty
{
	if (this->position == -1)
		return true;
	else
		return false;
}
bool Stack::isFull()
{
	if (this->position == this->size-1)
		return true;
	else
		return false;
}
int Stack::Size()// function to display size of stack
{
	return this->size;
}
void Stack::print() const
{
	if (this->position == -1)
		cout << " Stack is already empty : " << endl;
	else
	{
		cout << " Required data is : " << endl;
		for (int i = this->position; i >= 0; i--)
			cout << " " << ptr[i];
		cout << endl;
	}
}
void Stack::operator= (const Stack& obj)// equal to operator in stack
{
	this->position = obj.position;
	this->size = obj.size;
	deepcopy(obj.ptr, this->ptr);
}
Stack::~Stack()// destructor of stack
{
	if (this->ptr != nullptr)
	{
		delete[] this->ptr;
		this->ptr = nullptr;
	}
}

Main Source file.

// main source file

#include<iostream>
#include"Stack.h"
using namespace std;
int main()
{
	Stack obj;
	obj.push('j');
	obj.push('i');
	obj.push('h');
	obj.push('g');
	obj.push('f');
	obj.push('e');
	obj.push('d');
	obj.push('c');
	obj.push('b');
	obj.push('a');
	obj.push('a');// not able to push data because stack is full
	obj.print();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.pop();
	obj.print();
	cout << " Obj2 data is : " << endl;
	Stack obj2(obj);// call copy constructor
	obj2.print();
	cout << " obj3 data is : " << endl;
	Stack obj3;
	obj3 = obj2;// call operator=
	obj3.print();
	return 0;
}

Output.

output of stack using arrays

Push function in a stack in C++.

The stack::push(Val) function takes Val of character type as an argument in the above program. And first, it checks that if the stack is full or not by calling the isFull function. If the function returns true means, the stack is already full.

In that case, the message prints on the console that “ Sorry you are not able to push data in stack :.” and if the function returns false means that the stack is not full, then first, we make an increment in the current position and then place that Val in that index of the array.

The push function in the stack is of void type means it doesn’t return any value. The code snippet of the push function is as follows.

// code snippet of push function in stack in C++.

void Stack::push(char val)// push function in stack
{
	if (isFull())
		cout << " Sorry you are not able to push data in stack : " << endl;
	else
	{
		this->position++;
		this->ptr[this->position] = val;
	}
}

Pop function in the stack in C++.

In the above program, the stack::pop() function removes the topmost element from the stack. It first checks that the stack is empty or not by calling the empty() function.

If the function returns true, it displays the message that “Stack is already empty :.” if the function returns false, it places zero in the stack’s current index and reduces the current position by minus one.

The pop function in the stack is of void type means it doesn’t return any value. The code snippet of the pop function is as follows.

// code snippet of the pop function in C++.

void Stack::pop()// function to pop value from stack
{
	if (empty())
		cout << " Stack is already empty : " << endl;
	else
	{
		this->ptr[this->position] = 0;
		this->position--;
	}
}

The top function in the stack in C++.

In the above program, the stack::top() function is used to display the topmost element of the stack. It first checks that the stack is empty or not by calling the stack::empty() function.

If the function returns true, it displays the message that “Stack is empty :.” if the function returns false, it returns the element placed on the topmost position of the stack.

The code snippet of the top function is as follows.

// the code snippet of top function in C++

char Stack::top()// function to see top value from stack
{
	if (empty())
	{
		cout << " stack is empty : " << endl;
		return '-';
	}
	else
		return this->ptr[this->position];
}

IsFull function in the stack in C++.

In the above program, the stack::isFull() function returns true if the stack is full and false if the stack is not full. It compares that the current position is equal to one less than the max size of the stack. If this condition is true, then it returns true, and if this condition is false, it returns false.


The isFull function in the stack is of bool type means it return only Boolean values true or false based on the condition. The code snippet of the isFull function in the stack is as follows.

// the code snippet of isFull functio is as follow

bool Stack::isFull()
{
	if (this->position == this->size-1)
		return true;
	else
		return false;
}

Empty function in the stack in C++.

In the above program, the stack::empty() function returns true if the stack is empty and returns false if the stack is not empty. It compares that the current position is equal to minus one. If this condition is true, then it returns true, and if this condition is false, it returns false.


The empty function in the stack is of bool type means it return only Boolean values true or false based on the condition. The code snippet of the empty function in the stack is as follows.

// the code snippet of empty function in stack in C++ is as follow

bool Stack::empty()// function that returns true if stack is empty
{
	if (this->position == -1)
		return true;
	else
		return false;
}

Size function in the stack in C++.

In the above program, the stack::size() function is used to return the size of the stack. It returns an integer value. It returns the size of the stack. The code snippet of the size function in the stack is as follows.

// the code snippet of size function in the stack in C++ is as follow

int Stack::Size()// function to display size of stack
{
	return this->size;
}

The print function in Stack in C++.

In the above function, the stack::print() function is used to print the stack’s data. This is a non-returning function of the void type. It means it didn’t return any value. This function first checks the current position.

If it is minus one (-1) means that the stack is empty, then it returns the message that the “stack is empty.” If the current position does not equal minus one, which means the stack is not empty, it prints the stack’s data from the last index to the first.

As the stack follows the last in first out technique, that’s why we start displaying data from the last index of the array. The code snippet of print data in the stack is as follows.

//The code snippet of print data in the stack is as follows.

void Stack::print() const
{
	if (this->position == -1)
		cout << " Stack is already empty : " << endl;
	else
	{
		cout << " Required data is : " << endl;
		for (int i = this->position; i >= 0; i--)
			cout << " " << ptr[i];
		cout << endl;
	}
}

The application or implementation of a stack.

A stack is the most important data structure. Stack has a wide range of uses in both user programs and system programs. Let’s take an example that you have five different functions, function A, function B, function C, function D, and function E., and both of these functions are calling each other.

For example, function A calls function B, and function B calls function C, function C calls function D, function D calls function E. when any function terminates, it transfers control to the previous function.

For example, after terminating function E returns control to function D, function D returns control to function C, function C returns control to function B, function B returns control to function A. they form a stack.

Recursion.

Recursion is the most important example of a stack. Most of the time, we use recursion to solve many problems. Recursion works completely with the stack. Most of the problems are recursive in nature.

They must be solved recursively for better performance and results. It first pushes all the return values and variables in the stack. And after all the recursion calls, it pops the results from the stack to summarize the final result, and it then returns back the final result to the calling function.

Most of the time, stacks are also used to convert the recursive functions into non-recursive functions.

Postfix expression.

The stacks are used to evaluate the postfix expressions as expressions need to be executed correctly, so by using stack. We can change the general expressions into the postfix expressions.

Reversing a string.

We know that the stack follows the framework of last in, first out. The stack operates from top to bottom. This is the main reason that it is easy to reverse a string using a stack.

Implementation of the stack.

Stacks can also be implemented in two ways.

  • Static implementation of a stack.
  • Dynamic implementation of a stack.

Static implementation of a stack.

In the static implementation of the stack, the size of the stack is fixed in compile time. And the size of the stack cannot be changed during runtime.

Dynamic implementation of a stack.

In the dynamic implementation of the stack, the size of the stack is not fixed. We can grow and shrink the size of the stack during runtime.

If you find it helpful then don't forget to Share it :

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

Latest Posts

More From The Blog